[Database] Indexing - B+-tree

B+-tree

 

B+ tree는 다음의 조건을 만족하는 tree를 말합니다(이때 n은 한 노드에서 가질 수 있는 pointer의 최대 개수입니다):

• All path from root to leaf are of the same length; balanced tree를 말합니다.
• Each node that is not a root or a leaf has between ceil(n/2) and n children; root노드가 아닌 노드들은 50%이상의 children을 가져야합니다.
• A leaf node has between ceil((n-1)/2) and n-1 values; leaf노드는 50%이상의 value들을 가져야합니다.
• Special case(root node):
  • If the root is not a leaf, it has at least 2 children; root가 leaf노드가 아니라면 2개의 children node를 가져야합니다. 이는 root는 적어도 하나의 value를 가져야함을 나타냅니다.
  • If the root is a leaf(that is, there are no other nodes in the tree), it can have between 0 and (n-1) values

B+-tree

 

B+-tree Node structure

 

일반적인 node는 다음과 같이 구성됩니다:

B+-tree node structure

 

• Ki are the search key values - K는 search key를 나타내며, 이를 기준으로 tree의 아래로 내려갈 pointer P를 선택합니다.
• Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of record (for leaf node) - P는 pointer로 leaf node가 아닌 node들의 경우 children에 대한 pointer이고, leaf node들의 경우 clustered index라면 record에 대한 pointer, secondary index라면 bucket에 대한 pointer입니다.
• The search-keys in a node are ordered like K1 < K2 < ... < Kn-1

 

Leaf Nodes in B+-tree

 

leaf node는 다음과 같은 특징들을 지닙니다:

• Pointer Pi points to a record with search-key value Ki - leaf node에서 pointer Pi는 search key Ki에 대한 record를 가지고 있습니다. *secondary index의 경우는 search key Ki에 대한 bucket pointer를 갖습니다.
• If Li, Lj are leaf nodes and i < l, Lj's search-key values are less than or equal to Lj's search-key values - 이는 leaf node에서도 search key가 정렬되어있음을 알려줍니다.

Leaf nodes in B+-tree

 

Non-Leaf Nodes in B+-tree

 

non-leaf nodes들은 leaf node에 대한 multilevel sparse index의 형태를 띕니다. non-leaf node는 다음과 같은 특징들을 지닙니다:

• All the keys in the subtree to which P1 points are less than K1 - P1이 가르키는 children의 search key들은 K1보다 작습니다. *like BST
• For 2 ≤ i ≤ n-1, all the keys in the subtree to which Pi points have values greater than or equal to Ki-1 and less than Ki - 위랑 비슷한 얘기
• general structure:

general structure of non-leaf nodes in b+-tree

 

Example of B+-tree

 

n=6일때의 B+-tree의 예시입니다:

Example of B+-tree (n=6)

 

leaf node들은 최소 3에서 최대 5개의 value들을 가져야합니다(A leaf node has between ceil((n-1)/2) and n-1 values). 또한 non-leaf nodes들은 최소 3개에서 6개의 childre을 가져야합니다(Each node that is not a root or a leaf has between ceil(n/2) and n children). 마지막으로 root node는 최소 2개의 children을 가져야합니다(If the root is not a leaf, it has at least 2 children).

 

Observation about B+-tree

 

각각의 node들은 물리적으로 연결된것이 아닌 pointer를 통해 논리적으로 연결된 것입니다. non-leaf level의 노드들은 sparse indices의 구조를 띄고, B+-tree는 상대적으로 작은 수의 level을 사용합니다. K개의 search key values들이 존재한다면,

height of tree

 

정도의 level로 b+-tree를 구성할 수 있으며, search cost가 매우 줄어듭니다.

 

Queries on B+-tree

 

search key v를 이용해서 값을 찾는 경우 다음과 같은 알고리즘을 따릅니다:

find(v)

 

range queries의 경우 search key value를 range로 줘서 해당 record를 찾는 질의문입니다. 이는 findRange(lb, ub)를 통해 찾을 수 있으며, leaf node에서의 수평 탐색(interator interface)을 이용하여 수행할 수 있습니다.

findRange(c,g)

 

일반적으로 하나의 노드는 4KB정도의 크기를 갖습니다(page의 크기와 동일하게 해서 효율성을 높이기 위해). 하나의 index entry당 40bytes정도의 크기를 갖기 때문에, n=100정도라고 볼 수 있습니다. 그렇다면 백만개의 search key value가 있을 때, b+-tree의 높이는 log50(1,000,000) = 4 정도입니다. 즉, 어떤 query를 통해 record를 찾는 경우 오직 4개의 노드만 탐색하면 찾을 수 있다는 것이고, 이는 매우 효율적입니다(I/O가 오직 4번).

 

반면에 이를 balanced BST로 구성했다면, tree의 높이는 20정도입니다(log2(1,000,000) = 20). 따라서 20번의 I/O가 발생하고 이는 B+-tree보다 낮을 성능을 기록할 것입니다.

 

Non-Unique Keys

 

만약 index file에서 search key가 unique하지 않다면 search key 대신 새로운 key를 만들어야합니다. 일반적으로 기존의 search key a와 file의 primary key A를 이용해 (a, A) composite key를 이용합니다. 이 경우 a = v인 record를 찾고 싶은 경우 (v, -∞) 부터 (v, ∞)까지의 범위에 해당하는 key들을 search해야하는 단점이 있어서, I/O 작업의 수가 늘어날 수 있습니다.

 

Updates on B+-tree: insertion

 

leaf node에 (k, ptr) pair가 들어갈 자리가 존재하며, 만약 존재하지 않을시 node를 split하고 필요하면 parent node에 대해서도 propagate합니다.

 

Splitting a leaf node는 다음과 같은 과정을 거칩니다:

• Take the n(search key, pointer) pairs in sorted order - 우선 insertion하는 node n을 leaf node value들과 함께 정렬합니다.
• Place the first ceil(n/2) in the original node, and the rest in a new node - 그렇게 정렬한 value들 중에서 앞에 절반은 기존 노드에 두고, 뒤에 절반은 새로운 노드를 만들어 거기에 넣어줍니다.
• Let the new node be p, and let k be the least key value in p. Insert (k,p) in the parent of the node being split - 뒤에 절반의 노드에서 가장 작은 key value k를 parent node에 insert합니다.
• If the parent is full, split it and propagate the split further up - 만약 부모도 가득 찼다면 이를 부모노드에 대해 수행합니다.
• Splitting of nodes proceeds upwards till a node that is not full is found. In the worst case the root node may be split increasing the height of the tree by 1.

Insertion (splitting)

 

insert 'Adams'

insert 'Adams'

insert 'Lamport'

insert 'Lamport'

insert 'Lamport'

 

Updates on B+-trees: Deletion

 

tree가 다 완성되어있는 상황에서 search key K를 삭제하고 싶을 때, 다음과 같은 과정을 거칩니다:

• Remove (K, Ptr) from the leaf node
• If the node has too few entries that fit into a sibling, then merge siblings:
  • Insert all the key values in the two nodes into a single node (the one on the left), and delete the ohter node.
  • Delete the pair (Ki-1, Pi), where Pi is the pointer to the deleted node, from its parent, recusively using the above procedure.
• If a node has too few entries due to the removal, but the entries do not fit in a sibling, then redistributed pointers:
  • Redistributed the entries from a sibling such that both have more than minimum number of entries
  • Update the corresponding key in the parent node
• The node deletions may cascade upwards till a node which has n/2 or more pointers is found
• If the root node has only one pointer after deletion, it is deleted and the sole child becomes the root

https://www.programiz.com/dsa/deletion-from-a-b-plus-tree

Deletion from a B+ Tree

 

Complexity of Updates

 

buffer에 의한 비용 감소는 고려하지 않을때, insertion이나 deletion의 비용은 tree의 높이와 같습니다. 만약 insertion이나 deletion을 수행할때, 최악의 경우 O(height)만큼의 시간복잡도가 소모됩니다(splitting와 merge의 cascading이 root까지 이어졌을 경우).

 

하지만, 실제 I/O operation의 수는 적습니다. Splitting과 Merge가 일어나는 빈도 수가 적고, buffer에 의해 효율도 올라가기 때문입니다. node의 채움률(node occupancy)는 inserting order에 의존합니다. 예를 들어, 랜덤한 순서로 insertion을 하게된다면, 평균적으로 2/3의 노드들이 채워지며, 순서대로 들어오면 1/2의 노드들이 통계적으로 채워지게 됩니다:

B-트리(특히 B⁺-트리) 노드 occupancy(채움률)란?

• fanout n(차수 n) 를 가진 노드에 들어갈 수 있는 레코드(키)나 포인터의 최대 개수는 n 입니다.
• 트리는 균형을 유지하기 위해 “절반 이상 채워져 있어야 한다” 같은 하한 규칙을 둡니다.
  • 보통 리프와 내부 노드 모두 ⌈n ⁄ 2⌉ ≤ 채워진 개수 ≤ n을 만족해야 합니다.
  • 언더플로우(절반 미만) --► merge 혹은 redistribution
  • 오버플로우(초과) --► split

Node occupancy(평균 채움률) 은

실제 채워진 슬롯 수최대 슬롯 수(n)\frac{\text{실제 채워진 슬롯 수}}{\text{최대 슬롯 수}(n)}최대 슬롯 수(n)실제 채워진 슬롯 수​

의 평균을 말합니다. 예를 들어 차수 100 노드에 67개의 레코드가 있으면 occupancy = 0.67(= 67 ⁄ 100).

---

왜 “랜덤 삽입 시 2/3, 정렬된 삽입 시 1/2 정도”가 나오나?

삽입 패턴평균 채움률이 높아지는/낮아지는 이유귀결

무작위(랜덤) 입력	• 삽입 위치가 트리 전체에 균일하게 분포
• 오버플로우가 일어날 때마다 split된 두 노드에 키가 거의 반반 섞여 들어가지만, 이미 다른 노드들도 부분적으로 채워져 있음 → merge·split이 일어나도 빈 공간이 비교적 빨리 다시 채워짐	통계적으로 약 2/3 ≈ 66 % 수준에서 수렴
정렬된(모노톤) 입력	• 항상 가장 오른쪽(또는 왼쪽) 리프에서만 삽입 발생 → 트리의 “꼬리”에서만 split이 계속 일어남
• 기존 노드는 건드리지 않으므로 이미 split된 노드 한쪽은 거의 절반만 찬 상태로 남아 있을 가능성이 큼	평균적으로 1/2 = 50 % 부근으로 떨어짐

 

핵심 아이디어
split은 키를 대략 n/2 : n/2 로 잘라 두 노드를 만듭니다.
랜덤 삽입이면 split된 “반쯤 찬” 두 노드 모두 다음에 곧 다른 삽입을 받아 채워지므로 전체 평균이 2/3 정도까지 다시 올라갑니다.
정렬 삽입이면 새로 생긴 왼쪽 노드는 그대로 방치되고, 오른쪽 끝 노드만 계속 split-→반쯤 찬 노드가 체인처럼 누적 → 평균이 1/2 근처로 유지됩니다.

---

직관적인 예시 (차수 n = 4 인 리프만 생각)

1. 랜덤 입력
   1. [7 | ] (첫 삽입)
   2. [7 9]
   3. [3 7 9] …
   4. [3 7 9 12] (오버플로우) → split ⇒ [3 7], [9 12]
   5. 다음 삽입은 랜덤하게 두 노드 중 한 곳에 들어가므로 둘 다 금세 3/4, 4/4 … 평균이 0.67쯤으로 회복
2. 오름차순 입력
   1. [3 ]
   2. [3 7]
   3. [3 7 9]
   4. [3 7 9 12] split ⇒ [3 7], [9 12]
   5. 다음 삽입은 항상 오른쪽 노드로 가서 [9 12 15], [9 12 15 18] …
      split될 때마다 새로운 “왼쪽” 노드는 [9 12]처럼 정확히 절반만 찬 상태로 남음 → 평균 ≈ 0.5

---

실무에서 기억해야 할 점

• 트리 설계·인덱스 로딩
  • 대량 로딩 시 bulk-load 기법으로 처음부터 ~90 %까지 채워두면 디스크 페이지 낭비를 크게 줄일 수 있음.
• 운영 중 성능 예상
  • 랜덤 업데이트가 많은 OLTP 워크로드라면 “평균 2/3”를 사용해 페이지·버퍼 캐시 요구량을 대략 추정.
  • 순차 키(예: 타임스탬프)만 계속 들어오는 경우엔 split hot-spot 완화(예: right-padding, GUID, key-reversal) 같은 기법을 검토.

---

요약

• 노드 평균 채움률은 min (≈ 1/2) 과 max (= 1) 사이에서 움직이며,
• 입력 순서가 랜덤이면 ≈ 2/3, 정렬 입력이면 ≈ 1/2 근처에 머무는 것이 일반적인 경험칙입니다.
• 이 차이는 split/merge가 트리 전체에 고르게 일어나느냐, 특정 경로 끝에 집중되느냐로 설명할 수 있습니다.

 

B+-tree File Organization

 

B+-tree를 index file이 아닌 진짜 file로서 사용할 수 있습니다. 이는 index file로 사용하는 B+-tree와 달리 leaf node가 pointer대신 실제 record들이 저장되어있습니다. 이때 Insertion과 Deletion은 index file B+-tree와 동일하게 진행합니다.

B+-tree file organization

 

leaf node가 가지고 다니는 데이터의 크기가 index file일 때보다 크기 때문에 space utilization이 매우 중요합니다. 이를 위해 index file과 달리 각각의 node에는 최소 2/3의 entries들이 있어야합니다. 즉, 한 노드에 들어가는 entries의 수를 늘려, 높이를 낮추는 것입니다. 또한 redistribution(splitting or merge)에 사용하는 sibling node들의 참여를 늘립니다. 기존에는 왼쪽 노드만 참여했지만, file organization에서는 양쪽 노드 모두를 사용합니다. 

 

redistribution에 사용하는 sibling node를 양쪽 노드로 하면, 최소 각 entries에 수가 2n/3으로 유지할 수 있습니다:

왜 “형제 노드를 둘(혹은 셋) 이상 참여시켜 재분배하면 공간 효율이 좋아질까?

— B*-트리 아이디어가 숨어 있다!

---

1. 기본 B⁺-트리의 한계

• 차수 n(= 한 노드에 최대 n 개의 키 또는 레코드)
• 규칙: ⌈n/ 2⌉ ≤ 키 수 ≤ n
  • 언더플로우(⌊n/ 2⌋ 개 미만) → borrow(형제에게 1 개 받아오기) 실패 시 merge
  • 오버플로우(n + 1 개) → split → 두 노드가 대략 n/2 : n/2 로 채워짐
• ⇒ 최악·병합 직후 노드들이 50 % 정도(= n/2)만 차 있을 수 있다.
  • 디스크 페이지·버퍼 캐시에 절반이 공백 → 트리 높이 증가, I/O 낭비

---

2. 형제 “한 쪽”만 보지 말고 양쪽(또는 2 개 모두)까지 같이 보자

(바로 이 슬라이드가 말하는 전략)

상황전통 B⁺-트리두 형제까지 고려

오버플로우 (삽입)	곧바로 split → 2 노드가 n/2 씩	① 오른쪽(또는 왼쪽) 형제가 여유 있으면 재분배만 하고 끝 ⇒ split X
		② 양 형제 모두 가득 차면 두 노드 + 새 노드 ⇒ 3-way split → 각 노드 ≈ 2n/3 개
언더플로우 (삭제)	형제에게서 1 개 빌려오기 ⇢ 실패 시 두 노드 merge → 새 노드 ≈ n/2	왼·오른쪽을 함께 관찰해 총 키 수를 셋에 재분배할 여지가 있으면 3-way redistribute → 각 노드 ≥ 2n/3

 

• 이렇게 하면 “절반만 찬 페이지” 를 거의 만들지 않는다.
• 3-way split/redistribution 방법은 전통적으로 B*-트리(B-star tree)가 쓰는 기법이며,
  • 보장된 최소 occupancy가 ⌈2n/ 3⌉(≈ 66 %)로 올라간다.

---

3. 수식으로 보는 효과

• 노드 두 개가 모두 가득(n) + 삽입 1 개 ⇒ 총 2n + 1 개.
• 3 노드로 나누면 평균 = (2n + 1)/3 ≈ 2n/ 3.
  • 즉 새로 생긴 세 노드 모두 ≥ 2n/3 개 키를 갖는다.
• 삭제-언더플로우도 마찬가지 논리로 최소 개수를 2n/3 까지 올릴 수 있다.

---

4. 공간(utilization) 면에서의 이득

• 최소 채움률 50 % → 66 % 로 상승
  • 같은 데이터 양을 저장하는 데 필요한 페이지 수 ≈ 25 % 감소
    (가령 n = 100, 페이지당 50 개 → 66 개로 올라가면 100 만 레코드 보관 시
    20 000 페이지 → 15 152 페이지 수준으로 감소)
  • 트리 높이가 줄어 들거나 변하지 않더라도 디스크·버퍼 캐시 절약
• 레코드(데이터) 페이지는 포인터 페이지보다 훨씬 크다 → 빈 공간이 곧 디스크 낭비 & I/O 증가

---

5. 실제 DBMS가 쓰는 방법

트리 변형보장 최소 occupancy핵심 아이디어

B⁺-트리	⌈n/ 2⌉ (50 %)	오버플로우 시 즉시 split
B*-트리	⌈2n/ 3⌉ (≈ 66 %)	먼저 형제에 redistribute, 둘 다 full이면 3-way split
UB-트리 등	70 ~ 90 %	bulk-load, node packing, prefix truncation 등 추가 기법

 

즉, 형제 노드 참여 범위를 넓히면
“split/merge를 조금 더 똑똑하게 해서 페이지를 2/3 이상 차게 유지”
→ 공간 활용이 좋아지고, 트리 자체가 작아진다 는 것이 슬라이드의 메시지입니다.

 

Other Issues in Indexing

 

record가 splitting이나 merge로 인해 위치를 옮겨야하는 경우, 해당 record pointer를 저장하고 있는 secondary indices(bucket)까지 모두 update해야합니다. 이는 B+-tree를 secondary indices로 사용할때 node split이 매우 비싼 연산이 되게 만듭니다. 이를 해결하기 위해 non-unique한 search key를 갖는 B+-tree file organization구조로 사용합니다. 이는 record를 search하는데 비용이 더 들긴 하지만, redistribution에 사용하는 비용이 싸집니다. *search key를 file이 정렬된 기준으로 하고싶지 않아서 secondary indices 구조를 선택했을 것이니 해당 search key를 사용해서 composite search key를 사용한 것입니다.

 

Indexing Strings

 

String을 search key로서 사용하면 여러가지 문제가 생길 수 있습니다. string은 variable length를 가지기 때문에 저장하는 과정에서도 문제가 발생할 수 있으며(고정되지 않은 node크기), search key끼리 비교하는데 string length만큼의 선형 시간이 소모됩니다. 이는 string의 길이가 길어질수록 overhead가 발생함을 나타냅니다.

 

따라서 String을 key로 사용하는 경우 Prefix compression을 사용합니다. string의 전부를 key로 사용하지 않고, string의 앞 부분 일부만을 key로 사용하는 것입니다. 만약 같은 prefix를 갖는 key의 경우 같은 leaf node를 가질 수 있습니다.

 

Bulk loading and bottom-up build

 

만약 여러개의 insert를 해야하는 entry가 있을 때 하나의 entry를 하나 하나씩 insert한다면, 하나의 entry당 적어도 한 번의 I/O operation을 해야하는데, 이는 매우 비효율적입니다. 따라서 한 번에 여러개의 데이터를 insert하는 경우(bulk loading) 다음의 두 가지 효율적인 방법이 존재합니다:

 

(1) Efficient alternative 1:

• sort entries first (using efficient external-memory sort algorithms discussed later in Section 15.4)
• insert in sorted order
  • Insertion will go to exisiting page (or cause a split); buffer에 존재하는 page를 계속 사용할 수 있다. # I/O operation이 줄어든다.
  •  much improved I/O performance
  • but most leaf nodes half full; 오른쪽 노드만 차니까 왼쪽 노드는 최소 개수(절반)만 남는다.

 

(2) Efficient alternative 2:

• Bottom-up B+-tree construction
  
  • As before sort entries
  • and then create tree layer-by-layer, starting with leaf level; leaf node에서부터 정렬된 데이터들을 이용하여 leaf layer를 채워넣습니다. 위 layer들도 redistribution합니다.
  • Implemented by most database systems; 하지만 leaf layer의 node occupancy가 80%-90%이기 때문에 새로운 insert에 취약합니다(거의 무조건 split).

 

 

B-tree Index File Example

 

B-tree는 internal node에도 record로 향하는 pointer가 존재합니다. 이를 통해 B+-tree와 달리 반드시 leaf node까지 가서 record로 향하는 것이 아닌 운이 좋으면 internal node에서 record로 바로 갈 수 있다는 장점이 있습니다. 또한 높이도 더 낮습니다. 하지만 B+-tree는 leaf에서 횡방향으로 leaf node들을 scan할 수 있어 range queries에 유연한 반면, B-tree는 scan을 할 수 없다는 단점이 있습니다.

B-tree and B+-tree