B-트리와 B+트리의 개념 및 구현

데이터베이스와 파일 시스템 같은 대규모 데이터 관리에서 B-트리와 B+트리는 중요한 역할을 합니다. 이 자료구조들은 균형 잡힌 다진 트리로 설계되어 데이터 검색, 삽입, 삭제 작업에서 일정한 성능을 보장합니다. 이번 포스팅에서는 B-트리와 B+트리의 개념과 차이점, 그리고 C#으로 구현하는 방법을 소개합니다.

---

1. B-트리(B-Tree)란?

1.1. B-트리의 개념

B-트리는 다진 균형 이진 탐색 트리입니다. 각 노드가 여러 개의 키와 자식을 가질 수 있어, 높이를 낮게 유지하고 검색 및 수정 연산의 효율성을 높입니다.

B-트리의 특징

1. 모든 리프 노드는 같은 높이를 가진다.
   균형을 유지하기 때문에 데이터의 탐색 시간이 일정하다.
2. 각 노드는 최대 M개의 자식을 가질 수 있다.
   M은 트리의 차수(order)로, 노드에 저장할 수 있는 키의 수는 최대 M−1M - 1M−1이다.
3. 키는 오름차순으로 정렬되어 있다.
4. 트리의 높이는 log⁡MN\log_M NlogM​N에 비례한다.

1.2. B-트리의 동작

• 삽입: 데이터를 추가하면서 노드의 키 개수가 M−1M - 1M−1을 초과하면 분할(split)이 발생한다.
• 삭제: 데이터를 제거한 뒤, 키 개수가 최소 개수 이하가 되면 병합(merge)이 발생한다.

---

2. B+트리(B+Tree)란?

2.1. B+트리의 개념

B+트리는 B-트리를 확장한 자료구조로, 검색 속도를 더욱 개선한 구조입니다. 리프 노드가 모든 데이터를 저장하며, 리프 노드들이 연결 리스트 형태로 연결되어 있습니다.

B+트리의 특징

1. 리프 노드에만 데이터를 저장한다.
   내부 노드는 경로를 나타내는 색인 역할만 한다.
2. 리프 노드는 정렬된 순서로 연결된다.
   이 연결 리스트 구조는 범위 검색(range query)을 효율적으로 수행할 수 있도록 돕는다.
3. 높이가 낮다.
   B-트리와 마찬가지로 균형을 유지하여 검색 성능을 보장한다.

---

3. B-트리와 B+트리의 차이점

특징	B-트리	B+트리
데이터 저장 위치	모든 노드에 저장 가능	리프 노드에만 저장
리프 노드 연결	연결되지 않음	연결 리스트로 연결
범위 검색	상대적으로 비효율적	리프 노드 연결로 매우 효율적
높이	더 높을 수 있음	상대적으로 낮음
용도	일반적인 데이터 저장 및 검색	데이터베이스, 파일 시스템 등에서 선호됨

---

4. B-트리와 B+트리 구현 (C#)

4.1. B-트리 노드 클래스

public class BTreeNode<T> where T : IComparable
{
    public List<T> Keys { get; private set; }
    public List<BTreeNode<T>> Children { get; private set; }
    public bool IsLeaf => Children.Count == 0;

    public BTreeNode()
    {
        Keys = new List<T>();
        Children = new List<BTreeNode<T>>();
    }
}

4.2. B-트리 클래스

public class BTree<T> where T : IComparable
{
    private int _minDegree; // 최소 차수
    private BTreeNode<T> _root;

    public BTree(int minDegree)
    {
        _minDegree = minDegree;
        _root = new BTreeNode<T>();
    }

    public void Insert(T value)
    {
        if (_root.Keys.Count == 2 * _minDegree - 1)
        {
            // Root가 가득 찬 경우, 새로운 루트 생성 및 분할
            var newRoot = new BTreeNode<T>();
            newRoot.Children.Add(_root);
            SplitChild(newRoot, 0);
            _root = newRoot;
        }

        InsertNonFull(_root, value);
    }

    private void InsertNonFull(BTreeNode<T> node, T value)
    {
        int i = node.Keys.Count - 1;

        if (node.IsLeaf)
        {
            // Leaf 노드에 삽입
            node.Keys.Add(value);
            node.Keys.Sort();
        }
        else
        {
            // Internal 노드에 삽입
            while (i >= 0 && value.CompareTo(node.Keys[i]) < 0) i--;
            i++;
            if (node.Children[i].Keys.Count == 2 * _minDegree - 1)
            {
                SplitChild(node, i);
                if (value.CompareTo(node.Keys[i]) > 0) i++;
            }
            InsertNonFull(node.Children[i], value);
        }
    }

    private void SplitChild(BTreeNode<T> parent, int index)
    {
        var fullNode = parent.Children[index];
        var newNode = new BTreeNode<T>();

        // 분할된 노드의 키와 자식 이동
        newNode.Keys.AddRange(fullNode.Keys.GetRange(_minDegree, _minDegree - 1));
        if (!fullNode.IsLeaf)
            newNode.Children.AddRange(fullNode.Children.GetRange(_minDegree, _minDegree));

        fullNode.Keys.RemoveRange(_minDegree - 1, _minDegree);
        if (!fullNode.IsLeaf)
            fullNode.Children.RemoveRange(_minDegree, _minDegree);

        parent.Keys.Insert(index, fullNode.Keys[_minDegree - 1]);
        parent.Children.Insert(index + 1, newNode);
    }

    public void Traverse()
    {
        Traverse(_root);
        Console.WriteLine();
    }

    private void Traverse(BTreeNode<T> node)
    {
        int i;
        for (i = 0; i < node.Keys.Count; i++)
        {
            if (!node.IsLeaf)
                Traverse(node.Children[i]);
            Console.Write(node.Keys[i] + " ");
        }

        if (!node.IsLeaf)
            Traverse(node.Children[i]);
    }
}

4.3. 실행 예제

public class Program
{
    public static void Main()
    {
        var bTree = new BTree<int>(3); // 차수 3의 B-트리 생성

        bTree.Insert(10);
        bTree.Insert(20);
        bTree.Insert(5);
        bTree.Insert(6);
        bTree.Insert(12);
        bTree.Insert(30);
        bTree.Insert(7);
        bTree.Insert(17);

        Console.WriteLine("B-트리 순회 결과:");
        bTree.Traverse();
    }
}

4.4. 실행 결과

B-트리 순회 결과:
5 6 7 10 12 17 20 30

 

---

B-트리와 B+트리는 대규모 데이터를 효율적으로 관리하기 위한 핵심 자료구조입니다.
특히, 데이터베이스 인덱스와 파일 시스템에서 B+트리가 더 선호되며, 범위 검색과 정렬 작업에서 강력한 성능을 제공합니다.