크래프톤 정글 8기 - 22일차 TIL (B-Tree)

TIL - 2025.04.01 (화요일)

📝 오늘 배운 것 (B-Tree)

B-Tree?

자가 균형 트리로 이진트리를 확장하여 하나의 노드가 두 개 이상의 자식을 가질 수 있도록 설계되었다.

B-Tree는 AVL 트리로 레드-블랙 트리와 더불어 skewed tree(한쪽으로 치우친 트리)를 해결할 수 있는 자료구조 중 하나이다. AVL 트리나 레드-블랙 트리를 모든 데이터가 메모리에 적재할 수 있는 경우에 적용함과 달리 B-Tree는 대용량 데이터를 다뤄야 하는 DB나 디스트에 주로 적용된다.

대부분 트리에서의 연산이 높이에 따라 결정됨을 볼 때 B-Tree는 h를 줄이기 위해 B-Tree의 노드에 가능한 많은 값을 집어넣어 높이를 낮춤으로써 fat tree의 형태를 보인다. 이렇게 하나의 노드에 여러 정보를 담게 되고, 여러 자식을 가지게 되며 이진트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담을 수 있게 된다.

일반적으로 B-Tree 노드의 크기는 디스크 블록의 크기에 따라 결정되며 높이를 낮춤으로써 디스크로의 접근지연 시간을 최소화한다.

B-Tree 시간복잡도

Action	Average	Worst
Search	O(log N)	O(log N)
Insert	O(log N)	O(log N)
Delete	O(log N)	O(log N)

B-Tree 주요 특징

1. 다중키: 각 노드는 여러 개의 키(데이터)를 포함할 수 있으며, 이들은 항상 정렬된 상태로 유지된다.
2. 균형 구조: 모든 리프 노드는 같은 레벨에 위치하여 트리의 균형을 유지한다.
3. 가변적인 자식 수: 내부 노드는 M/2에서 M개 사이의 자식을 가질 수 있다. 여기서 M은 B-Tree의 차수를 나타낸다.
4. 효율적인 검색: 대량의 데이터에서도 O(log N)의 시간 복잡도로 검색이 가능하다.
5. 자동 균형 조정: 삽입과 삭제 시 트리의 균형을 자동으로 조정한다.

B-Tree의 구조

• 루트 노드: 트리의 최상위 노드로, 최소 2개의 자식을 가져야 한다.
• 내부 노드: 키와 자식 노드에 대한 포인터를 포함한다.
• 리프 노드: 실제 데이터 또는 데이터에 대한 참조를 저장한다.

B-Tree의 작동원리

1. 검색: 루트에서 시작하여 키를 비교하여 적절한 자식 노드로 이동
2. 삽입: 적절한 리프 노드를 찾아 삽입하고, 필요시 노드를 분할
3. 삭제: 키를 제거하고, 필요시 노드를 재구성하거나 병합

B*Tree

B*Tree는 B-Tree의 변형으로, 노드 분할을 최대한 지연시키기 위해 설계되었다.

주요 특징

• 비-루트 노드를 최소 2/3 이상 태우도록 한다.
• 노드가 가득 찼을 때 즉시 분할하지 않고, 이웃 노드와 키를 재 분재한다.
• 분할 연산을 줄여 삽입 비용을 낮춘다.

B+Tree

B+Tree는 B-Tree를 개선한 버전으로 데이터 베이스 시스템에서 널리 사용된다.

주요 특징

• 모든 데이터는 리프 노드에만 저장된다.
• 내부 노드는 키만 저장하고, 실제 데이터에 대한 포인터는 없다.
• 리프 노드들은 연결 리스트로 연결되어 있어 순차적 접근이 용이하다.
• 범위 검색에 매우 효과적이다.

B-Tree와의 차이점

1. 데이터 저장 : B+Tree는 리프 노드에만 데이터를 저장한다.
2. 검색 경로 : B+Tree는 항상 리프 노드까지 이동해야 한다.
3. 노드 구조 : B+Tree의 내부 노드는 키만 저장하여 더 많은 키를 수용할 수 있다.
4. 순차 접근 : B+Tree는 리프 노드 간 연결로 인해 순차 접근이 빠르다.
5. 메모리 효율 : B+Tree는 내부 노드에 키만 저장하여 메모리 사용이 효율적이다.

B-Tree 코드 예시 (파이썬)

B-Tree 예시

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

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

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.child.insert(0, root)
            self._split_child(temp, 0)
            self._insert_non_full(temp, k)
        else:
            self._insert_non_full(root, k)

    def _insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append(None)
            while i >= 0 and k < x.keys[i]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self._split_child(x, i)
                if k > x.keys[i]:
                    i += 1
            self._insert_non_full(x.child[i], k)

    def _split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t: (2 * t) - 1]
        y.keys = y.keys[0: t - 1]
        if not y.leaf:
            z.child = y.child[t: 2 * t]
            y.child = y.child[0: t]

    def print_tree(self, x, l=0):
        print(f"Level {l}", end=": ")
        for i in x.keys:
            print(i, end=" ")
        print()
        l += 1
        if len(x.child) > 0:
            for i in x.child:
                self.print_tree(i, l)

# 사용 예시
b = BTree(3)  # 최소 차수가 3인 B-Tree 생성

# 키 삽입
for i in range(10):
    b.insert(i)

# B-Tree 출력
b.print_tree(b.root)

1. BTreeNode 클래스: B-Tree의 노드를 표현한다.
2. BTree 클래스: B-Tree 자체를 표현하며, 삽입 및 출력 메서드를 포함한다..
3. insert 메서드: 새로운 키를 B-Tree에 삽입한다.
4. _insert_non_full 메서드: 가득 차지 않은 노드에 키를 삽입한다.
5. _split_child 메서드: 가득 찬 노드를 분할한다.
6. print_tree 메서드: B-Tree의 구조를 출력한다.

위 코드는 B-Tree의 기본적인 작동 원리를 보여준다. 그래서 삭제 기능은 포함되어 있지 않다. 물론 실제 데이터 베이스 시스템에서 사용되는 B-Tree는 더 복잡하고 최적화되어 있다.

B+Tree 구현 예시 (파이썬)

B+ Tree 예시

class BPlusTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []
        self.next = None  # 리프 노드 연결을 위한 포인터

class BPlusTree:
    def __init__(self, t):
        self.root = BPlusTreeNode(True)
        self.t = t  # 최소 차수 (minimum degree)

    def search(self, k):
        """키 k를 검색하여 해당 값을 반환합니다."""
        return self._search(self.root, k)

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

        # 리프 노드인 경우
        if node.leaf:
            if i < len(node.keys) and node.keys[i] == k:
                return (node, i)  # 키를 찾았을 때 노드와 인덱스 반환
            return None  # 키를 찾지 못함

        # 내부 노드인 경우
        if i < len(node.keys) and k == node.keys[i]:
            i += 1  # B+Tree에서는 같은 키가 있어도 다음 자식으로 이동

        return self._search(node.child[i], k)

    def insert(self, k, v):
        """키 k와 값 v를 B+Tree에 삽입합니다."""
        root = self.root
        # 루트 노드가 가득 찬 경우
        if len(root.keys) == (2 * self.t) - 1:
            temp = BPlusTreeNode()
            self.root = temp
            temp.child.insert(0, root)
            self._split_child(temp, 0)
            self._insert_non_full(temp, k, v)
        else:
            self._insert_non_full(root, k, v)

    def _insert_non_full(self, node, k, v):
        i = len(node.keys) - 1

        # 리프 노드인 경우
        if node.leaf:
            # 적절한 위치를 찾아 키와 값을 삽입
            while i >= 0 and k < node.keys[i]:
                i -= 1
            i += 1
            node.keys.insert(i, k)
            node.child.insert(i, v)  # 리프 노드의 child에는 실제 값을 저장
        else:
            # 내부 노드인 경우, 적절한 자식을 찾음
            while i >= 0 and k < node.keys[i]:
                i -= 1
            i += 1

            # 자식 노드가 가득 찬 경우
            if len(node.child[i].keys) == (2 * self.t) - 1:
                self._split_child(node, i)
                if k > node.keys[i]:
                    i += 1

            self._insert_non_full(node.child[i], k, v)

    def _split_child(self, parent, index):
        t = self.t
        child = parent.child[index]
        new_node = BPlusTreeNode(child.leaf)

        # 새 노드에 키 분배
        new_node.keys = child.keys[t:]
        child.keys = child.keys[:t]

        # 리프 노드인 경우
        if child.leaf:
            # 값도 분배
            new_node.child = child.child[t:]
            child.child = child.child[:t]

            # 리프 노드 연결 리스트 업데이트
            new_node.next = child.next
            child.next = new_node

            # 부모 노드에 중간 키 복사 (B+Tree에서는 복사)
            parent.keys.insert(index, new_node.keys[0])
        else:
            # 내부 노드인 경우
            new_node.child = child.child[t:]
            child.child = child.child[:t]

            # 부모 노드에 중간 키 이동 (B+Tree에서는 이동)
            parent.keys.insert(index, child.keys[t-1])
            child.keys.pop(t-1)

        # 부모 노드에 새 자식 추가
        parent.child.insert(index + 1, new_node)

    def print_tree(self):
        """B+Tree 구조를 출력합니다."""
        self._print_tree(self.root, 0)

    def _print_tree(self, node, level):
        print(f"Level {level}:", end=" ")
        print(node.keys)

        if not node.leaf:
            level += 1
            for child in node.child:
                self._print_tree(child, level)

    def print_leaves(self):
        """모든 리프 노드를 순서대로 출력합니다."""
        node = self._find_leftmost_leaf(self.root)
        print("Leaf nodes (linked list):", end=" ")
        while node:
            for i in range(len(node.keys)):
                print(f"({node.keys[i]}: {node.child[i]})", end=" ")
            node = node.next
        print()

    def _find_leftmost_leaf(self, node):
        """가장 왼쪽 리프 노드를 찾습니다."""
        if node.leaf:
            return node
        return self._find_leftmost_leaf(node.child[0])

    def range_search(self, start_key, end_key):
        """주어진 범위 내의 모든 키-값 쌍을 반환합니다."""
        result = []

        # 시작 키가 있는 리프 노드 찾기
        start_node_info = self._search_leaf_node(self.root, start_key)
        if not start_node_info:
            return result

        node, index = start_node_info

        # 범위 내의 모든 키-값 쌍 수집
        while node:
            i = index if node == start_node_info[0] else 0
            while i < len(node.keys) and node.keys[i] <= end_key:
                result.append((node.keys[i], node.child[i]))
                i += 1

            if i < len(node.keys) and node.keys[i] > end_key:
                break

            node = node.next
            index = 0

        return result

    def _search_leaf_node(self, node, k):
        """키 k가 위치할 리프 노드와 인덱스를 찾습니다."""
        if node.leaf:
            i = 0
            while i < len(node.keys) and k > node.keys[i]:
                i += 1
            return (node, i)

        i = 0
        while i < len(node.keys) and k >= node.keys[i]:
            i += 1

        return self._search_leaf_node(node.child[i-1], k)

# 사용 예시
b_plus_tree = BPlusTree(2)  # 최소 차수가 2인 B+Tree 생성

# 키-값 쌍 삽입
for i in range(1, 11):
    b_plus_tree.insert(i, f"value_{i}")

# B+Tree 구조 출력
print("B+Tree 구조:")
b_plus_tree.print_tree()

# 리프 노드 출력
print("\n리프 노드 연결 리스트:")
b_plus_tree.print_leaves()

# 키 검색
key = 5
result = b_plus_tree.search(key)
if result:
    node, index = result
    print(f"\n키 {key} 검색 결과: {node.child[index]}")
else:
    print(f"\n키 {key}를 찾을 수 없습니다.")

# 범위 검색
start_key = 3
end_key = 7
range_result = b_plus_tree.range_search(start_key, end_key)
print(f"\n범위 검색 ({start_key}-{end_key}) 결과:")
for k, v in range_result:
    print(f"({k}: {v})", end=" ")
print()

주요 특징

1. 리프 노드 연결: 모든 리프 노드는 next 포인터로 연결되어 있어 순차적 접근이 가능.
2. 데이터 저장 위치: 모든 실제 데이터(값)는 리프 노드에만 저장된다.
3. 내부 노드: 내부 노드는 키만 저장하고, 자식 노드에 대한 포인터를 가진다.
4. 범위 검색: 리프 노드 연결을 활용한 효율적인 범위 검색이 가능.
5. 분할 방식: B+Tree의 특성에 맞게 노드 분할 시 중간 키가 내부 노드에 복사된다.

🔍 더 알아볼 것

• AVL 트리
• 레드-블랙 트리

🧐 느낀 점

그래프와 트리의 세계는 무궁무진하구나...

📚 참고 자료

• [자료구조] B tree & B+ tree
• [자료구조] 간단히 알아보는 B-Tree, B+Tree, B*Tree
• B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정