인덱싱 (2)

B+ 트리 인덱스 파일

우리가 인덱싱 (1) - 순서 인덱스에서 다룬 순서 인덱스는 한계를 가지고 있다.

파일을 재구성하면 이 문제를 해결할 수 있으나, 이를 자주 수행하는 것은 바람직하지 않음

그래서 나온 대안 중 하나가 바로, B+ 트리 구조임.

B+ 트리는 다음과 같은 트리의 특징을 가지고 있음:

균형 트리 구조(balanced tree) 임.
root에서 leaf까지의 경로 길이가 모두 동일함 → 균형 트리 조건 만족.
루트 노드를 제외한 모든 비단말 노드(non-leaf node) 는 자식 노드를 $⌈n/2⌉$ 개 이상, $n$ 개 이하 가짐. 여기서 $n$ 은 트리의 차수로 고정된 값임.
루트 노드는 최소 2개에서 최대 $n$ 개까지 자식을 가질 수 있음.

📚 B+-트리는 다단계 인덱스 구조임

예시 : 전체 그림

B+ 트리 인덱스와 레코드

인덱스의 모양을 전체적으로 한번 보자. 왜 이것이 B+ 트리라고 하는지 알 수 있다.

B+ 트리의 대표적인 노드

그림 14.7은 기본적인 B+ 트리의 노드 (node)

노드는 포인터와 검색 키 값으로 이뤄져 있다.

1개의 노드당 포인터의 갯수와 검색 키 값의 갯수는 정해져 있음.

또한 검색 키 값은 항상 오름차순으로 정렬되어 있음 ( $K_{i} < K_{i+1}$ ).

B+ 트리의 리프노드

리프노드에서의 포인터

하나의 리프노드에서 포인터가 n개 있다고 할 때,

리프 노드 간에도 정렬 관계 유지됨:

내부 노드는 리프 노드들을 위한 다단계 인덱스 역할을 함.
포인터는 모두 다른 트리 노드(리프 or 내부)를 가리킴.
최대 n개의 포인터를 가질 수 있으며, 최소 ⌈n/2⌉개의 포인터를 가져야 함
- 이때 포인터 개수 m은 fanout(분기도) 라고 함.
내부 노드에 m개의 포인터가 있을 때
- $P_1$ 은 키 값 < K_1인 서브 트리를 가짐.
- $P_2 \sim P_{m−1}$ 는 $K_{i-1} \sim K_{i}$ 범위의 서브트리
- $P_m$ 은 $K_{m-1}$ 보다 큰 키가 있는 서브트리

내부 노드 중 가장 위에 위치한 루트 노드는 다음과 같은 특징이 있음.

다양한 차수의 B+-트리