B+ 트리

B+-트리의 장점 및 단점

장점:

• 자동 재조직화: B+-트리는 삽입 및 삭제 작업이 발생할 때마다 작은 지역적 변경으로 자동으로 재조직화된다. 이는 데이터베이스가 계속해서 효율적으로 작동하도록 도와준다.

단점:

• 오버헤드: 삽입 및 삭제 시 추가적인 오버헤드가 발생하며, 트리 구조를 유지하기 위해 공간적인 오버헤드도 존재한다.

B+-트리의 구조 및 특성

• 균형 트리: 루트에서 리프 노드까지의 모든 경로의 길이가 동일
• 자식 수 제한: 루트나 리프가 아닌 각 노드는 최소 ⌈n/2⌉에서 최대 n개의 자식을 가짐
• 리프 노드의 값 수 제한: 리프 노드는 최소 ⌈(n–1)/2⌉에서 최대 (n–1)개의 값을 가짐
• 루트의 특수 경우: 루트가 리프가 아닌 경우 최소 2개의 자식을 가져야하고 루트가 리프인 경우 최소 0개에서 최대 (n–1)개의 값 가짐

B+-트리 노드의 구조

• 일반적인 노드: [P1, K1, P2, K2, ..., Pn-1, Kn-1, Pn]의 형태로 구성
  • K1, K2, ..., Kn-1: 탐색 키 값들
  • P1, P2, ..., Pn: 자식 노드로의 포인터 (비리프 노드의 경우) 또는 레코드나 레코드 버킷으로의 포인터 (리프 노드의 경우)
• 노드 내 키 값의 순서: 각 노드 내의 탐색 키 값들은 K1 < K2 < ... < Kn–1의 순서로 정렬되어 있음
  • 중복된 키 값이 없다고 가정

B+-트리의 리프 노드

• 리프 노드의 특성:
  • Pi는 탐색 키 값 Ki를 가진 레코드로의 포인터이다.
  • Li와 Lj가 리프 노드이고 i < j라면, Li의 탐색 키 값들은 Lj의 탐색 키 값들보다 작거나 같다.
  • Pn은 다음 리프 노드(형제 노드)로의 포인터이다.

B+-트리의 비리프 노드

• 비리프 노드들은 리프 노드에 대한 다단계 희소 인덱스를 형성한다.
  • 비리프 노드의 형태: [P1, K1, P2, K2, ..., Pn-1, Kn-1, Pn]
  • P1이 가리키는 서브트리의 모든 탐색 키 값은 K1보다 작다.
  • 2 ≤ i ≤ n – 1인 경우, Pi가 가리키는 서브트리의 모든 탐색 키 값은 Ki–1보다 크거나 같고 Ki보다 작다.
  • Pn이 가리키는 서브트리의 모든 탐색 키 값은 Kn–1보다 크거나 같다.

B+-트리의 예 (n=6)

• 리프 노드는 최소 3개에서 최대 5개의 값을 가진다. (⌈(n–1)/2⌉ ~ (n–1))
• 비리프 노드(루트 제외)는 최소 3개에서 최대 6개의 자식을 가진다. (⌈n/2⌉ ~ n)
• 루트는 최소 2개의 자식을 가진다.

B+-트리의 삽입 및 삭제 효율성

• 희소 인덱스: 비리프 노드는 희소 인덱스를 형성하고, 리프 노드는 밀집 인덱스를 형성한다.
• 삽입 및 삭제 효율성: 삽입 및 삭제 작업은 인덱스를 재구성함으로써 효율적으로 처리된다. 트리 구조의 조정은 로그 시간 내에 수행된다.

B+-트리의 높이

• B+-트리는 상대적으로 적은 수의 레벨을 가진다.
  • 루트 아래 레벨에는 최소 2*⌈(n-1)/2⌉ 개의 값이 있다. => 루트는 최소 2개의 자식을 가지고 리프 노드는 최소 ⌈(n–1)/2⌉값을 가지기 때문.
  • 그 다음 레벨에는 최소 2*⌈n/2⌉ * ⌈(n-1)/2⌉ 개의 값이 있다. => 비리프 노드(루트 제외)는 최소 ⌈n/2⌉개의 자식을 가지기 때문
• 파일에 K개의 탐색 키 값이 있는 경우, 트리의 높이는 최대 ⌈log⌈n/2⌉(K)⌉이다.
• 노드는 일반적으로 디스크 블록과 동일한 크기(4K 또는 8K)이다.
  • n은 일반적으로 약 100이다 (인덱스 항목 당 40바이트)
  • 100만 개의 탐색 키 값과 n=100일 경우, 최대 ⌈log50(1,000,000)⌉=4개의 노드를 조회한다.
  • 반면, 균형 이진 트리에서는 100만 개의 탐색 키 값에 대해 약 20개의 노드를 조회해야 한다.

B+-트리에서의 질의

• 특정 탐색 키 값 V를 가진 레코드를 찾는 방법:
  1. C를 루트로 설정
  2. C가 리프 노드가 될 때까지 반복 : 
     • i를 V ≤ Ki를 만족하는 최소 값으로 설정
     • 만약 그런 i가 존재하지 않으면, C를 C의 마지막 non-null pointer로 설정
     • V=Ki이면, C를 Pi+1로 설정
     • 그렇지 않으면, C를 Pi로 설정
  3. 이제 C는 리프 노드이다. i를 Ki = V를 만족하는 최소 값으로 설정
  4. 만약 그런 값 i가 존재하면, Pi 포인터를 따라가 레코드를 얻는다. 그렇지 않으면, 해당 탐색 키 값을 가진 레코드는 존재하지 않는다.