B+ Tree의 특징

• B Tree의 변형 구조

• Index Set(인덱스 세트) + Sequence Set(순차 세트)로 구성됨.

  ⇒ 순차 탐색 성능 향상 목적

• Index Set

  • 리프 이외의 노드
  • 키 값만 존재함.

• Sequence Set

  • 리프 노드
  • 모든 값들이 존재함. (키 값, Data Record 주소 등)

차수가 m인 B+ Tree의 특성

• 노드 구조 : $<n,P_0,K_1,P_1,K_2, ... ,P_{n-1},K_n,P_n>$
  • $n$ = 키 값의 수 $(1≤n<m)$
  • $P_0, P_1, ... , P_n$ = 서브 트리에 대한 포인터
  • $K_1, K_2, ... , K_n$ = 키 값
• 루트 노드 : 0이나 2 ~ m 개의 서브 트리를 가짐.
• 모든 내부 노드(루트 & 리프 노드 제외) : 최소 $m/2$ 개, 최대 $m$개의 서브 트리를 가짐.
• 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브 트리 수보다 하나 작음.
• 모든 리프 노드는 같은 레벨!
• 한 노드에 있는 키 값들은 오름차순 정렬
• $P_i (0≤i≤n-1)$가 지시하는 서브 트리에 있는 노드들의 모든 키 값들은 키 값 $K_{i+1}$보다 작거나 같음.
• $P_n$이 지시하는 서브 트리에 있는 노드들의 모든 키 값은 키 값 $K_n$보다 큼.
• 리프 노드는 파일 레코드들의 Sequence Set을 나타냄 & 모두 링크로 연결됨.
• 리프 노드 구조 : $<q, <K_1,A_1>, <K_2,A_2>, ... , <K_q,A_q>,P_{next}>$
  • $A_i$ = 키 값 $K_i$를 가지고 있는 레코드에 대한 포인터
  • $m/2 ≤ q$
  • $P_{next}$ = 다음 리프 노드에 대한 링크

B+ Tree의 장점

• Exact Value(키 검색)와 Range Query(범위 검색)을 모두 필요로 하는 응용에 효과적임

  Ex) DBMS, File System