[DB] 인덱스

공부하게 된 배경

최근에 기술 면접에서 DB의 인덱스에 대한 질문을 받았는데 DB 조회 성능을 개선할 당시에 나는 현업에서 사용하지 않았었다. 면접관 분은 당연히 인덱스를 이용해보았을 거라고 생각하셨지만 인덱스에 대해 깊이 알고 있지 못했고 이미 100만 건 이상의 데이터가 있어서 인덱스를 새로 설정하는 데에 시간이 오래 걸릴 것이라 생각했다. 하지만 인덱스 설정을 해줬다면 조회 성능이 빨라졌을까 후회가 되어 공부를 해보고자 한다. 인덱스의 기본 개념 및 자료구조를 다루고, 이후에 MySQL의 인덱스와 인덱스의 종류(Cluster Index, Non-Cluster Index)에 대해 알아볼 것이다.

인덱스란?

인덱스를 책을 기준으로 설명을 해보면 나는 국내 명소 관련 도서에서 ‘팔각정’에 대한 정보를 찾고 싶다.
도서 내에서 원하는 정보를 보려면 처음부터 책을 한 장씩 넘기며 끝까지 찾는 방법이 있고, 아래와 같이 책 맨 뒤의 색인 페이지를 통해 사전 순서로 정렬된 명소 이름을 기준으로 페이지를 보며 빠르게 찾는 방법이 있다.

데이터베이스 내 인덱스도 의미가 비슷하다.
추가적인 쓰기 작업, 저장 공간을 이용해서 테이블의 데이터 검색 속도를 향상시키기 위한 자료구조이다.

인덱스는 데이터베이스 테이블의 특정 컬럼이나 여러 컬럼에 대한 값과 그 열의 묶음 형태로 저장되며, DB 조회 쿼리의 성능 최적화에 중요한 역할을 한다.

데이터베이스에서 인덱스를 사용하면, 데이터를 검색할 때 full-scan하는 것이 아니라, 인덱스를 사용하여 검색 대상 레코드의 범위를 줄일 수 있다.
이는 대량의 데이터를 다루는 경우 데이터 검색 속도를 크게 향상시킨다.

인덱스의 장단점

장점

1. 검색 대상 레코드의 범위를 줄여 조회 성능을 최적화할 수 있다.
2. 인덱스의 컬럼에 대해 중복 데이터를 방지하고 유일성(unique)을 보장할 수 있다.
3. ORDER BY(정렬), GROUP BY, WHERE 절이 사용되는 컬럼에 대해 쿼리가 효율적으로 처리된다.

단점

1. 인덱스 생성에 따른 추가적인 저장 공간이 필요하다. (MySQL에서는 인덱스 생성 시 인덱스에 대한 데이터를 저장하는 MYI 파일 생성)
2. 레코드의 INSERT, UPDATE, DELETE 시에도 인덱스를 갱신하기 때문에 대량의 데이터가 빈번하게 수정되는 테이블에서는 성능이 저하될 수 있다.
3. 이미 많은 데이터가 저장된 테이블에 인덱스를 적용하면 인덱스 적용 소요 시간이 오래 걸릴 수 있다.
4. 한 레코드를 동시에 수정할 수 있는 병행성이 줄어든다.
5. 불필요한 인덱스가 많아지면 쿼리 최적화에 혼란을 줄 수 있고, 성능이 나빠진다.

인덱스는 데이터를 조회하는 데에 최적화된 성능을 제공해서 소요 시간을 단축시킨다. 하지만 인덱스를 설정할 때에 해당 테이블의 레코드가 빈번하게 수정되지 않는 지, 저장 공간이 불필요하게 차지되지 않는 지 등 적절히 선택하고 설정해야 효율적으로 사용할 수 있다.

인덱스 생성 시에 고려할 점

1. WHERE 절이나, GROUP BY, ORDER BY에 자주 이용되는 컬럼이면 좋다.
2. 유니크한 컬럼이어야한다.
3. 카디널리티가 높아야 한다.
   • 카디널리티가 낮다는 것은 컬럼에 대한 값의 종류가 적다는 것이다.
   • 남,여 성별과 같이 카디널리티가 낮다면 비효율적이다.
   • 주민등록번호같이 유니크하다면 인덱스의 컬럼으로 이용하기 적당하다.
4. 갱신이 빈번하지 않은 테이블의 컬럼을 대상으로 해야한다.
   • 인덱스는 테이블과 별도로 저장되는 데이터 구조이다. 테이블의 데이터가 변경될 때 마다 인덱스도 함께 갱신되어야한다.
   • INSERT : 새로운 레코드가 삽입되는 경우 인덱스 엔트리에도 해당 레코드의 인덱스 엔트리를 추가해야한다.
   • UPDATE : 기존의 인덱스 엔트리를 사용하지 않음 flag처리 하고, 새로운 데이터에 대한 인덱스 엔트리를 반영해야한다.
   • DELETE : 삭제될 엔트리를 사용하지 않음 flag처리 한다.
5. 복합 인덱스를 고려한다.

인덱스의 자료구조

해시 테이블(HashTable)

해시 테이블은 Key와 Value를 쌍으로 이룬 자료구조이다.
해시를 이용해서 O(1)의 시간 복잡도로 데이터를 검색할 수 있어 빠른 검색을 할 수 있다는 것이 특징이다.

해시 테이블의 내부 로직은 키를 해시 함수를 통해 해시로 변환하고, 해당 해시에 해당하는 값을 검색한다. 해시 테이블은 검색 속도가 매우 빠르지만 해시 충돌이 발생할 수 있으므로 해시 충돌을 해결하기 위한 방법이 필요하다.

하지만 DB에서 컬럼에 대해 = 보다는 >, < 부등호에 대한 조건 탐색이 많기 때문에 해시 테이블은 인덱스의 자료구조로 적당하지 않다.

B Tree

B Tree의 특징은 가장 왼쪽 노드부터, 높이에 상관없이 오른쪽으로 갈 수록 오름차순으로 정렬되어있음을 볼 수 있다.

그리고 일반적인 트리와 유사하지만, 자식 노드에 여러 개의 노드가 들어갈 수 있다는 점이 다르다.

B Tree의 장점으로는 ‘어떤 값에 대해 조회하는 데에 소요되는 시간이 동일하다.’이다.
이를 균일성이라고 하는데 위의 이미지 중 15에 대한 값과 650에 대한 값을 찾는 시간은 O(logN)의 시간복잡도로 동일하다.

그리고 B Tree는 균형적인 트리이기 때문에 데이터의 INSERT, DELETE, UPDATE를 수행하면서 균형이 깨지게 되는 것을 방지하기 위해 균형을 맞춰주는 작업이 필요하고, 이로 인해 데이터의 갱신 시 성능이 악화된다.

B+ Tree

B Tree에서 확장된 개념의 트리이다.
B Tree의 경우, 루트 노드 또는 중간에 위치한 노드에 key와 data를 담을 수 있다.
하지만, B+ Tree의 경우 브랜치 노드에 key만 담아두고, data는 담지 않는다. 오직 리프 노드에만 key와 data를 저장하고, 리프 노드끼리 LinkedList로 연결되어 있다.

B+ Tree의 장점으로는 리프 노드에만 data를 저장하고 있기 때문에 저장 공간에 대해 이점이 있다.
그리고 하나의 노드에 더 많은 key들을 담을 수 있기에 트리의 높이는 더 낮아진다.(cache hit를 높일 수 있음)

또한, B+ Tree에서 풀스캔을 할 때 리프 노드 LinkedList를 선형 탐색하면 되기 때문에 B Tree의 풀스캔보다 빠르다.

B Tree vs B+ Tree

구분	B Tree	B+ Tree
데이터 저장	리프 노드와 중간 노드 둘 다 데이터 저장 가능	리프 노드에만 데이터 저장 가능
트리의 높이	높다	낮다(한 노드에 key를 많이 담을 수 있다.)
풀스캔 시 검색 속도	모든 데이터를 조회해야한다.	리프 노드의 LinkedList를 선형탐색한다.
키 중복	없음	있음(리프 노드에 모든 key에 대한 데이터가 있다.)
검색 방식	자주 access 되는 노드를 루트 노드 가까이 배치할 수 있고, 루트 노드에서 가까울 경우, 브랜치 노드에도 데이터가 존재하기 때문에 빠름	리프 노드까지 가야 데이터 존재
LinkedList 유무	없음	리프 노드끼리 LinkedList로 연결

출처

• 요기요 기술블로그 이미지
• 데이터베이스 인덱스(index) 개념 정리
• B-tree와 B+tree란?