B+ 트리
더 많은 작업
B+ 트리(B+ Tree)는 B 트리(B-Tree)의 확장된 버전으로, 데이터베이스 및 파일 시스템에서 효율적인 검색 및 범위 쿼리를 수행하는 데 사용된다. B+ 트리는 모든 키를 리프 노드(Leaf Nodes)에 저장하며, 리프 노드끼리는 연결 리스트(Linked List)로 연결되어 있다.
B+ 트리는 B 트리와 유사하지만 몇 가지 중요한 차이점이 있다.
- 리프 노드에만 키와 데이터 저장
- 내부 노드(Internal Nodes)는 탐색을 위한 인덱스 역할만 수행하고, 실제 데이터는 리프 노드에 저장된다.
- 리프 노드 연결 리스트
- 리프 노드끼리 연결 리스트(Linked List) 형태로 연결되어 있어 범위 검색(Range Query)이 매우 빠르다.
- 균형 유지
- 모든 리프 노드는 동일한 깊이를 가지며, 항상 균형을 유지한다.
1. 내부 노드는 키만 저장하며, 실제 데이터는 리프 노드에만 저장된다. 2. 리프 노드는 이중 연결 리스트(Double Linked List) 형태로 연결되어 있다. 3. 각 노드는 최소 ⌈m/2⌉개의 자식과 최대 m개의 자식을 가질 수 있다. 4. 모든 리프 노드는 동일한 깊이에 존재한다. 5. 검색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)이다.
| 속성 | 설명 |
|---|---|
| 키 저장 위치 | 리프 노드에만 저장 |
| 내부 노드 | 인덱스 역할만 수행 |
| 리프 노드 연결 | 연결 리스트로 연결되어 있음 |
| 탐색 성능 | 빠름 (리프 노드에서만 탐색) |
| 범위 검색 | 매우 빠름 (리프 노드 간 연결 이용) |
B+ 트리와 B 트리는 유사하지만 몇 가지 중요한 차이점이 있다.
| 기준 | B 트리 | B+ 트리 |
|---|---|---|
| 키 저장 위치 | 내부 노드와 리프 노드 | 모든 키가 리프 노드에 저장 |
| 탐색 속도 | 느림 (내부 노드에서도 탐색) | 빠름 (리프 노드에서만 탐색) |
| 범위 검색 | 상대적으로 비효율적 | 빠름 (리프 노드 연결 리스트 사용) |
| 리프 노드 연결 | X | O (이중 연결 리스트) |
| 키 중복 | 한 키는 트리에 한 번만 나온다 | 내부 노드의 키 값이 리프(단말) 노드에 다시 나타난다(내부 노드의 키는 리프 키의 복사본) |
- 두 트리 모두 루트를 뺀 노드가 절반 이상 채워지도록 보장한다. 루트는 자식 2개(키 1개)만 있어도 되므로, '루트를 포함한 모든 노드가 절반 이상의 사용률을 보장한다' 는 B 트리와 B+ 트리 어느 쪽에도 맞지 않는다 → B 트리
1. 적절한 리프 노드를 찾아 삽입한다.
2. 노드가 초과(m개의 키)되면 중앙 키를 상위 노드로 올리고, 노드를 분할한다.
리프가 넘치면 리프를 둘로 나누고 가운데 키를 부모에 복사한다. 키는 리프에도 그대로 남는다(모든 키가 리프에 있어야 하므로). 내부 노드가 넘치면 내부 노드를 나누고 가운데 키를 부모로 올린다. 이때 키는 내부 노드에서 빠진다. 루트가 넘쳐 나뉘면 새 루트가 생겨 높이가 1 늘어난다.
리프는 키 2~3개, 내부 노드와 루트는 키 1~2개를 담고, 키 a 의 왼쪽 서브트리에는 a 이하의 키가 온다고 하자(키 수가 짝수 m 이면 m/2 번째를 가운데로 본다). 69, 15, 110, 90, 20, 120, 40, 125 를 차례로 넣으면 다음과 같다.
- 69, 15, 110 → 리프 하나 [15 69 110]
- 90 → [15 69 90 110] 이 넘침. 가운데(2번째) 69 를 복사해 올림 → 루트 [69], 리프 [15 69] [90 110]
- 20 → [15 20 69], 120 → [90 110 120]
- 40 → [15 20 40 69] 넘침. 20 을 복사해 올림 → 루트 [20 69], 리프 [15 20] [40 69] [90 110 120]
- 125 → [90 110 120 125] 넘침. 110 을 올림 → 루트 [20 69 110] 이 넘침(최대 2개). 가운데 69 를 새 루트로 올림
결과는 루트 [69], 내부 노드 [20] [110], 리프 [15 20] [40 69] [90 110] [120 125] 로 노드 7개, 높이 3(루트를 레벨 1 로 볼 때)이다. 가장 왼쪽 리프는 [15 20] 이고, 69 는 루트와 리프에 함께 있다.
1. 삭제 후 노드에 남아 있는 키 개수를 확인한다.
2. 최소 키 개수보다 적으면 형제 노드에서 빌리거나, 병합을 수행한다.
1. 루트에서 시작하여 적절한 자식 노드를 따라가며 키를 찾는다.
2. O(log n)의 시간 복잡도로 검색 가능하다.
class BPlusTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.children = []
self.next = None # 리프 노드 연결 리스트
class BPlusTree:
def __init__(self, t):
self.root = BPlusTreeNode(True)
self.t = t # 최소 차수
def search(self, node, key):
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if node.leaf:
if i < len(node.keys) and key == node.keys[i]:
return node
return None
return self.search(node.children[i], key)
def insert(self, key):
root = self.root
if len(root.keys) == (2 * self.t) - 1:
new_root = BPlusTreeNode(False)
new_root.children.append(self.root)
self.split_child(new_root, 0)
self.root = new_root
self.insert_non_full(new_root, key)
else:
self.insert_non_full(root, key)
def insert_non_full(self, node, key):
i = len(node.keys) - 1
if node.leaf:
node.keys.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = key
else:
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == (2 * self.t) - 1:
self.split_child(node, i)
if key > node.keys[i]:
i += 1
self.insert_non_full(node.children[i], key)
def split_child(self, node, i):
t = self.t
y = node.children[i]
z = BPlusTreeNode(y.leaf)
node.keys.insert(i, y.keys[t - 1])
node.children.insert(i + 1, z)
z.keys = y.keys[t:(2 * t - 1)]
y.keys = y.keys[0:(t - 1)]
if not y.leaf:
z.children = y.children[t:(2 * t)]
y.children = y.children[0:t]
if y.leaf:
z.next = y.next
y.next = z
def traverse(self, node):
if node.leaf:
while node:
print(node.keys, end=" → ")
node = node.next
print("None")
else:
for i in range(len(node.keys)):
self.traverse(node.children[i])
self.traverse(node.children[len(node.keys)])
# B+ 트리 테스트
bplustree = BPlusTree(3) # 최소 차수 t = 3
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
bplustree.insert(key)
print("B+ 트리 리프 노드 순회 결과:")
bplustree.traverse(bplustree.root)
print("\n")
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
- GeeksforGeeks - B+ Tree Introduction