B+ 트리 인덱스

DB에서 데이터에 대한 접근은 결국 디스크 I/O라는 뜻이다. 디스크를 헤드를 위치시키고, 디스크를 회전하고, 데이터를 전송하고... CPU만큼이나 빠르게 작동하지 않는다. 때문에 검색의 효율을 높이기 위해서 인덱스를 설정한다. 이 인덱스의 방식 중 가장 널리 사용되는 방식이 B+트리 인덱스이다.

P 1

Key 1

P 2

Key 2

P n-1

Key n-1

P n

차수가 N인 B+트리의 노드 구조는 위와 같이 N개의 포인터와 N-1개의 검색키의 집합으로 구성되어 있다.  

키는 Key i-1 < Key i < Key i+1 ... 의 관계를 가지고 있으며, Key i와 Key i+1 사이에 있는 포인터인 P i+1이 가리키는 하위 노드 집합에는 Key i보다는 크고 Key i+1보다는 작거나 같은 검색키들이 위치해 있다. 

레코드가 10만 개인 테이블에서 특정 레코드를 검색한다고 했을 때, 인덱스가 구성되어 있지 않다면 최악의 경우 10만 건을 전부 스캔해야 한다. 반면, 차수가 10인 B+트리로 구성했을 경우 아래와 같이 구조가 형성되기 때문에 최악의 경우에도 10개의 키를 4번 검색하는 것만으로 원하는 레코드를 찾을 수 있다. 

대략적으로 시간복잡도가, O(N)에서 O(logN)으로 향상되는 셈이다.