[WEEK03] B-Tree

B-Tree란?

[출처] https://dzone.com/articles/database-btree-indexing-in-sqlite

B-Tree는 균형 잡힌 다진 트리(multi-way balanced tree)로, 데이터베이스 및 파일 시스템에서 효율적인 검색, 삽입, 삭제 연산을 지원하는 트리 구조다.

• 일반적인 이진 탐색 트리(BST)와 달리, 하나의 노드가 여러 개의 키와 자식을 가질 수 있음
• 높이가 낮아져 탐색, 삽입, 삭제 등의 연산이 빠르게 수행됨
• 데이터가 정렬된 상태로 유지되므로 범위 검색(range query)이 효율적

B-Tree의 구조

B-Tree는 다음과 같은 규칙을 따른다.

1. 각 노드는 최소 ⌈m/2⌉개 이상, 최대 m개의 자식을 가질 수 있다 (m은 트리의 차수).
2. 루트 노드는 최소 2개 이상의 자식을 가질 수 있지만, 예외적으로 1개의 자식도 허용된다.
3. 각 노드는 ⌈m/2⌉ - 1개 이상의 키를 가지고, 최대 m - 1개의 키를 가질 수 있다.
4. 모든 리프 노드는 같은 레벨에 위치하여 균형을 유지한다.
5. 키들은 오름차순으로 정렬되어 있으며, 특정 키보다 작은 값은 왼쪽 자식, 큰 값은 오른쪽 자식으로 분기된다.

B-Tree 연산

탐색 (Search)

• 루트에서 시작하여 키 값을 비교하면서 적절한 자식 방향으로 이동한다.
• O(log n)의 시간 복잡도를 가진다.

B-tree 인덱스를 사용할 때의 데이터 검색 시간 복잡도는 O(log n)이다. B-tree 구조는 균형 이진 트리와 유사하므로 데이터를 효율적으로 검색할 수 있다. 반면, B-tree 인덱스를 사용하지 않을 경우 선형 검색을 수행해야 하므로 검색 시간 복잡도는 O(n)이 된다. 따라서, 데이터 양이 많을수록 B-tree 인덱스를 사용하는 것이 성능 면에서 훨씬 유리하다.

삽입 (Insertion)

1. 적절한 리프 노드까지 이동하여 키를 삽입한다.
2. 삽입 후, 노드에 키 개수가 초과되면 중간 키를 부모로 올려 노드를 분할(split)한다.
3. 필요하면 재귀적으로 분할이 진행될 수 있다.

삭제 (Deletion)

1. 리프 노드에서 키를 삭제한다.
2. 삭제 후, 키 개수가 최소 개수보다 적어지면 형제 노드에서 빌려오거나(rotate) 병합(merge)한다.
3. 필요하면 부모까지 조정이 이어질 수 있다.

B-Tree vs. B+Tree

B-Tree와 비슷한 구조를 가진 B+Tree도 많이 사용된다. 차이점은 다음과 같다.

구분	B-Tree	B+Tree
데이터 저장	내부 노드와 리프 노드	리프 노드에만 저장
탐색 성능	내부 노드에서 데이터 찾기 가능	리프 노드까지 이동해야 함
범위 검색	중간 과정에서 끝날 수도 있음	리프 노드가 연결 리스트로 되어 있어 빠름

B+Tree는 범위 검색이 많은 데이터베이스와 파일 시스템에서 더 선호된다.

B-Tree의 활용

B-Tree는 다음과 같은 분야에서 널리 사용된다.

• 데이터베이스 인덱스: MySQL의 InnoDB에서 B+Tree 기반 인덱스를 사용한다.
• 파일 시스템: NTFS, HFS+, ext4와 같은 파일 시스템에서 디렉터리 구조나 메타데이터 저장에 활용된다.
• 키-값 저장소: LevelDB, RocksDB 등도 B-Tree 계열 구조를 사용하여 데이터를 효율적으로 저장한다.

코드 구현

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # 최소 차수 (최소 자식 수)
        self.leaf = leaf  # 리프 노드 여부
        self.keys = []  # 키 리스트
        self.children = []  # 자식 노드 리스트

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

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(t, True)
        self.t = t

    def traverse(self):
        if self.root is not None:
            self.root.traverse()
        print()

    def search(self, key, node=None):
        if node is None:
            node = self.root
        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(key, node.children[i])

정리

B-Tree는 이진 탐색 트리보다 더 효율적인 검색, 삽입, 삭제 연산을 제공하며, 특히 대량의 데이터를 다룰 때 강력한 성능을 발휘한다. 데이터베이스 및 파일 시스템에서 중요한 역할을 하므로, B-Tree의 구조와 동작 원리를 이해하는 것이 중요하다.