B 트리

Balanced Tree, B-Tree, B Tree

개요

• 자가 균형 트리(Self Balancing Tree)의 일종.

구성

• 키(key): 검색을 하기 위한 키
  • 포인터의 개수보다 하나가 더 많음
  • 양쪽에 포인트를 두고 있는 구조 (위 그림 참고)
• 포인터(pointer): 자식 노드의 주소를 가리킴
• 노드: 두 종류로 크게 나뉜다.
  • 내부 노드(internal nodes): 리프 노드를 제외한 노드들은 결국 리프 노드를 검색하기 위한 용도로 쓰인다.
  • 리프 노드(leaf node): 실제 데이터를 담고 있는 노드

조건

차수가 m인 B 트리는 아래의 조건을 만족해야 한다.

• 모든 노드는 최대 m개의 자식들을 가진다.
• 루트노드와 리프노드가 아닌 모든 노드는 최소 m/2개의 자식을 가진다.
• 루트노드는 2개 이상의 자식을 가진다.
• k개의 자식을 가진 노드는 k-1개의 키를 가진다.
• 즉, 자식을 가진 노드는 최소 m/2-1개에서 최대 m-1개의 키를 가진다.
• 모든 리프노드들은 같은 높이에 있어야 한다.
• 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다.

특징

• 탐색 시간 복잡도 : O(logN)
• 노드의 삽입 또는 삭제 연산 후에도 정렬된 자료구조를 보장한다.

비트리의 장단점

장점	단점
노드의 삽입/삭제 후에도 균등한 응답 속도를 보장	삽입/삭제 시 균형 유지를 위해 복잡한 연산 필요

B 트리 연산

1. 삽입 (Insertion)

1. 적절한 리프 노드를 찾아 삽입한다.
2. 노드가 초과(m개의 키)되면 중앙 키를 상위 노드로 올리고, 노드를 분할한다.

2. 삭제 (Deletion)

1. 삭제 후 노드에 남아 있는 키 개수를 확인한다.
2. 최소 키 개수보다 적으면 형제 노드에서 빌리거나, 병합을 수행한다.

3. 검색 (Search)

1. 루트에서 시작하여 적절한 자식 노드를 따라가며 키를 찾는다.
2. O(log n)의 시간 복잡도로 검색 가능하다.

삽입 예: 차수 3

차수(m)가 3인 B 트리는 노드마다 자식이 최대 3개, 키가 최대 2개다(2-3 트리). 키가 3개가 되면 넘친 것이므로 가운데 키를 부모로 올리고 나머지를 두 노드로 나눈다. 루트가 넘치면 새 루트가 생겨 높이가 1 늘어난다. 17, 20, 5, 15, 7, 18, 16, 19 를 차례로 넣는다.

1. 17, 20 → [17 20]
2. 5 → [5 17 20] 넘침. 17 을 올린다 → 루트 [17], 잎 [5] [20]
3. 15 → 잎 [5 15]
4. 7 → [5 7 15] 넘침. 7 을 올린다 → 루트 [7 17], 잎 [5] [15] [20]
5. 18 → 잎 [18 20], 16 → 잎 [15 16]
6. 19 → [18 19 20] 넘침. 19 를 올리면 루트가 [7 17 19] 로 넘친다. 17 을 다시 올려 새 루트를 만든다

            [17]
          /      \
       [7]        [19]
      /   \      /    \
    [5] [15 16] [18]  [20]

• 루트의 키는 17 하나다
• 리프 노드는 [5], [15 16], [18], [20] 의 4개, 전체 노드는 1 + 2 + 4 = 7개다
• 루트를 레벨 1 로 보면 높이는 3이다
• 분할 때 올라가는 것은 넘친 노드의 가운데 키다. 마지막에 넣은 키(19)나 새로 생긴 최솟값이 루트가 되는 것이 아니다

삽입과 삭제에서 일어나는 일

• 삽입은 분할만 일으킨다. 넘친 노드를 둘로 나누고 가운데 키를 부모로 올리며, 부모도 넘치면 분할이 위로 이어진다. 루트까지 분할되면 새 루트가 생겨 높이가 1 늘어난다
• 루트가 분할되어 생긴 새 루트는 키가 하나뿐이다. 루트는 최소 점유 규칙(절반 이상 채움)의 예외라 자식 2개만 있으면 되므로, 이때 루트의 공간 사용률은 1/2 미만이 된다. 예를 들어 m = 5(키 최대 4개)인 B 트리에서 새 루트의 키 1개는 4칸 중 1칸이다
• 병합(합치기)은 삭제에서만 일어난다. 삭제로 키가 최소 개수보다 적어지면 형제에게서 빌리거나 형제와 합치고, 루트에 자식이 하나만 남으면 루트를 없애 높이가 줄어든다
• 예: m = 5 인 B 트리에서 루트가 [9 19 26 35] 로 꽉 차 있고 잎 [27 29 33 34] 에 30 을 넣으면, 잎이 [27 29 30 33 34] 로 넘쳐 가운데 30 이 올라간다. 루트가 [9 19 26 30 35] 로 다시 넘쳐 가운데 26 이 새 루트로 올라가 높이가 1 늘고, 새 루트 [26] 은 4칸 중 1칸만 쓴다. 이 과정에 병합은 없다

B 트리 구현 (Python)

class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.children = []

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t  # 최소 차수

    def search(self, node, key):
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1

        if i < len(node.keys) and key == node.keys[i]:
            return node

        if node.leaf:
            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 = BTreeNode(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 = BTreeNode(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]

    def traverse(self, node):
        for i in range(len(node.keys)):
            if not node.leaf:
                self.traverse(node.children[i])
            print(node.keys[i], end=" ")
        if not node.leaf:
            self.traverse(node.children[len(node.keys)])

# B 트리 테스트
btree = BTree(3)  # 최소 차수 t = 3
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
    btree.insert(key)

print("B 트리 순회 결과:")
btree.traverse(btree.root)
print("\n")

같이 보기

• B+ 트리: 순차검색 향상을 위해 Index Set과 Data Set을 구분
• B* 트리: 삽입 시 빈번한 노드 분할에 따른 연산 감소