인덱스(index)의 종류와 활용

인덱스는 데이터베이스 테이블에 대한 검색 성능의 속도를 높여주는 자료구조다. 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬해 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장된다.

 

인덱스는 크게 B-tree와 B+tree 등 2가지 구현방식으로 나뉜다.

 

 

[B-tree]

 

우선 B-tree는 데이터를 정렬된 상태로 유지하면서 빠른 탐색이 가능한 트리다

출처: http://www.btechsmartclass.com/data_structures/b-trees.html

 

그림에 표시된 사각형 한 개 한 개의 데이터를 노드라고 한다. 한 노드가 여러 개의 자식을 가질 수 있고, 가장 하단의 리프 노드는 항상 같은 깊이에 있다. 특히 키를 정렬된 상태로 저장하기 때문에 어떤 데이터를 탐색하는 동일한 시간이 걸린다.

 

그러나 B-tree는 처음 생성 당시 균형 트리로 형성되지만, 테이블 갱신(Insert, Update, Delete 등)이 빈번해질 수록 균형이 깨지게 된다. 따라서 갱신 빈도가 높은 테이블에서 B-tree 구조로 인덱스가 형성될 경우 인덱스 재구성이 필요해 효율이 낮아진다.

 

 

[B+tree]

 

B+tree는 B-tree의 확장 개념이다. 

 

기본적인 구조는 B-tree와 유사하지만, 데이터의 실제 값은 가장 하단인 리프 노드에만 저장되며, 내부 노드에는 키 값만 존재한다. 이로 인해 모든 탐색은 리프 노드까지 내려가야 한다.

 

또 B+tree는 리프 노드들이 Linked List 형태로 연결되어 있어, 범위 검색(Range Scan)에 매우 효율적이다. 예를 들어 WHERE 절에서 BETWEEN 5 AND 7 같은 쿼리에서 연속된 데이터를 빠르게 순회할 수 있다.

 

B+tree의 주요 특징은 다음과 같다.

• 모든 실제 데이터는 리프 노드에만 존재
• 리프 노드끼리 연결돼 있어 범위 검색에 유리
• 내부 노드는 오직 탐색 목적으로만 존재하며 키만 가짐
• 균형 트리 유지가 더 안정적이고 특히 삽입·삭제 시 구조 유지가 쉬움

 

MySQL의 InnoDB 스토리지 엔진 역식 B+tree 구조를 기반으로 동작한다.