B+ 트리 편집하기

'''B+ 트리'''(B+ Tree)는 B 트리(B-Tree)의 확장된 버전으로, 데이터베이스 및 파일 시스템에서 효율적인 검색 및 범위 쿼리를 수행하는 데 사용된다.  B+ 트리는 모든 키를 리프 노드(Leaf Nodes)에 저장하며, 리프 노드끼리는 연결 리스트(Linked List)로 연결되어 있다.
==개요==
B+ 트리는 B 트리와 유사하지만 몇 가지 중요한 차이점이 있다.
*'''리프 노드에만 키와 데이터 저장'''
**내부 노드(Internal Nodes)는 탐색을 위한 인덱스 역할만 수행하고, 실제 데이터는 리프 노드에 저장된다.

*'''리프 노드 연결 리스트'''
**리프 노드끼리 연결 리스트(Linked List) 형태로 연결되어 있어 범위 검색(Range Query)이 매우 빠르다.

*'''균형 유지'''
**모든 리프 노드는 동일한 깊이를 가지며, 항상 균형을 유지한다.
==B+ 트리의 속성==
1. 내부 노드는 키만 저장하며, 실제 데이터는 리프 노드에만 저장된다.  2. 리프 노드는 이중 연결 리스트(Double Linked List) 형태로 연결되어 있다.  3. 각 노드는 최소 ⌈m/2⌉개의 자식과 최대 m개의 자식을 가질 수 있다.  4. 모든 리프 노드는 동일한 깊이에 존재한다.  5. 검색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)이다.
{| class="wikitable"
|+B+ 트리의 특징
!속성!!설명
|-
|키 저장 위치||리프 노드에만 저장
|-
|내부 노드
```mediawiki
||인덱스 역할만 수행
|-
|리프 노드 연결||연결 리스트로 연결되어 있음
|-
|탐색 성능||빠름 (리프 노드에서만 탐색)
|-
|범위 검색||매우 빠름 (리프 노드 간 연결 이용)
|}
==B+ 트리 vs B 트리==
B+ 트리와 B 트리는 유사하지만 몇 가지 중요한 차이점이 있다.
{| class="wikitable"
|+B+ 트리와 B 트리 비교
!기준!!B 트리!!B+ 트리
|-
|키 저장 위치||내부 노드와 리프 노드||모든 키가 리프 노드에 저장
|-
|탐색 속도||느림 (내부 노드에서도 탐색)||빠름 (리프 노드에서만 탐색)
|-
|범위 검색||상대적으로 비효율적||빠름 (리프 노드 연결 리스트 사용)
|-
|리프 노드 연결||X||O (이중 연결 리스트)
|}
==B+ 트리 연산==
===1. 삽입 (Insertion)===
1. 적절한 리프 노드를 찾아 삽입한다.  

2. 노드가 초과(m개의 키)되면 중앙 키를 상위 노드로 올리고, 노드를 분할한다.
===2. 삭제 (Deletion)===
1. 삭제 후 노드에 남아 있는 키 개수를 확인한다.  

2. 최소 키 개수보다 적으면 형제 노드에서 빌리거나, 병합을 수행한다.
===3. 검색 (Search)===
1. 루트에서 시작하여 적절한 자식 노드를 따라가며 키를 찾는다.  

2. O(log n)의 시간 복잡도로 검색 가능하다.
==B+ 트리 구현 (Python)==
<syntaxhighlight lang="python">
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")
</syntaxhighlight>
==같이 보기==
*[[B 트리]]
*[[이진 검색 트리]]
*[[AVL 트리]]
*[[트리 (자료 구조)]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms''. MIT Press.
*[https://www.geeksforgeeks.org/b-plus-tree-set-1-introduction/ GeeksforGeeks - B+ Tree Introduction]
[[분류:알고리즘]]
[[분류:트리]]