[ALGORITHMS] B-Tree

OOSEDUS·2025년 3월 16일

목록 보기

1/6

1) B-Tree의 필요성과 동기

BST는 각 노드가 최대 두 개의 자식(왼쪽, 오른쪽)을 가지는 트리이다. 아래와 같은 규칙을 갖는다.

- 왼쪽 자식의 노드의 값 < 부모 노드의 값
- 오른쪽 자식 노드의 값 > 부모 노드의 값

그러나 BST를 사용할 경우 데이터가 많아질수록 트리의 깊이(Depth)가 깊어지는 문제가 발생한다.

BST에서 데이터가 많아질수록 트리 깊이가 깊어지는 이유

(1) 균형이 잘 맞는 경우 (Balanced BST)

데이터가 균형 있게 배치되면 트리의 깊이는 log(N) 정도가 된다.
예를 들어, 100만 개의 데이터가 있다면 트리 깊이는 약 log₂(1,000,000) ≈ 20 이므로 탐색 연산이 20번 정도면 원하는 데이터를 찾을 수 있다.

(2) 편향된 BST (Skewed BST)

삽입 순서에 따라 한쪽으로만 치우친 트리(편향 트리, Skewed Tree)가 발생할 수 있음
예를 들어, 숫자를 오름차순으로 삽입하면 다음과 같은 트리가 형성됨. 이 경우 트리 깊이가 N이 되어서 탐색 연산이 O(N)에 가까워진다.

BST의 문제 정리

BST를 인덱스 구조로 사용하면 데이터가 많아질수록 트리가 깊어지고, 탐색 시간이 길어진다.
트리가 깊어질수록 필요한 노드가 디스크에 저장되어 있는 경우가 많아지고, 디스크 접근이 증가해 성능이 저하된다. (이유 - 메모리(RAM)에는 한정된 데이터만 저장 가능하며, 대부분의 데이터는 디스크(SSD, HDD)에 저장되기 때문에, 트리의 깊이가 깊어질수록 디스크에서 데이터를 가져와야 하는 횟수(Disk I/O)가 증가한다. 데이터베이스에서는 디스크 접근이 가장 성능을 저하시키는 요소이다.)

해결 방법 : B-Tree

"As branching increases, depth decreases"

브랜칭 팩터(Branching Factor, 한 노드가 가질 수 있는 자식 노드 수)를 늘려 깊이를 줄이는 방식으로 문제를 해결한다.
B-Tree는 한 노드에 여러 개의 자식을 가질 수 있어, 높이를 낮춰 디스크 접근 횟수를 줄인다.

2) B-Tree 정의

B-Tree of order m (m-way tree) : m차 B-Tree의 의미

m차 B-Tree는 각 노드가 최대 m개의 자식(child)를 가질 수 있는 트리를 의미한다.

B-Tree 규칙

1. Non-leaf 노드의 Key 개수는 자식 개수보다 1개 적다.

노드에 있는 키(Key, 숫자 값)들은 자식들을 그룹으로 나누는 역할을 한다.
ex) 그림에서 6과 12가 있는 노드는 세개의 자식 (1-2-4 / 7-8 / 13-15-18-25)를 나누는 기준(Key)가 된다.

2. 모든 Leaf 노드들은 같은 레벨(높이)에 존재해야한다.

즉, B-Tree의 모든 리프 노드(마지막 레벨의 노드)는 같은 깊이에 있어야 한다.
이렇게 하면 트리가 균형(Balanced)하게 유지되므로 탐색 속도가 일정하게 유지된다.

3. leaf 노드가 아닌 모든 노드들은 최소한 (m-1)/2 - 1 개의 키를 가져야한다.

트리의 균형을 유지하기 위해 모든 비단말 노드(루트 제외)는 최소한 일정 개수의 키를 가져야 한다.
예를 들어, m=5인 경우 최소한 ⌈(5-1)/2⌉ = 2 개 이상의 키를 가져야 해.

4. 각 노드의 키들은 오름차순으로 정렬된다.
5. 각 노드는 최대 (m-1)개의 키를 가진다.

* 위와 같은 규칙이 필요한 이유

1. 트리의 균형(Balancing) 유지

노드가 너무 적으면 트리가 한쪽으로 쏠릴 가능성이 커진다.
최소 키 개수를 정해줘야 균형이 유지된다.

2. 빠른 탐색(Search) 보장

키 개수가 너무 적으면 불필요하게 깊은 탐색이 필요해진다.
일정 개수 이상의 키를 유지하면 검색 성능이 일정하게 유지된다.

2) Searching 탐색

탐색은 루트 노드에서 시작한다.
찾고자 하는 Key(숫자 값)이 어느 노드에 속하는지 확인한다.
다시 Key 범위를 확인하고, 자식 노드로 이동한다.

한번에 여러 개의 Key를 비교하면서 내려가기 때문에 효율적이다. (즉, 한 번 탐색할 때 더 많은 정보를 얻을 수 있기 때문에 디스크 접근 횟수가 줄어들어 효율적)

✅ 탐색 시간은 O(log N)

3) Constructing a B-tree

: order(차수)가 5인 B-tree 구성 예시

차수가 5라는 것은 각 노드가 최대 4개의 키(키 개수 = m-1)를 가질 수 있으며, 최대 5개의 자식 노드를 가질 수 있음을 의미한다.

1. 초기 상태 (빈 B-Tree에 키 삽입)

주어진 키들이 다음 순서로 들어온다.
1, 12, 8, 2, 25, 6, 14, 28, 17, 7, 52, 16, 48, 68, 3, 26, 29, 53, 55, 45
처음에는 1, 2, 8, 12를 삽입한다.

2. 루트 노드에 4개까지 저장 가능

차수(order) 5이므로, 한 노드에는 최대 4개의 키를 저장할 수 있다.
따라서, 초기 삽입 시 {1, 2, 8, 12}가 루트에 들어간다.

3. 5번째 키(25) 삽입 시 규칙 위반 발생

다섯 번째 키 25를 추가하면 한 노드가 가질 수 있는 키 개수(4개 제한)를 초과하게 된다.
따라서 중앙값(Median)을 찾아 루트 노드를 분할(Split)해야 한다.

4. 루트 노드 분할 (Splitting the Root)

{1, 2, 8, 12, 25}가 되면 중앙값 8을 새로운 루트로 설정한다.
나머지 값들은 8보다 작은 값(1, 2)과 8보다 큰 값(12, 25)으로 나뉘어 서브트리를 형성한다. 결과적으로, B-Tree의 구조는 다음과 같이 변경된다.

     [ 8 ]
    /     \
 [1, 2]   [12, 25]

5. 리프(leaf) 노드에 키들 추가
~~1, 12, 8, 2, 25, 6, 14, 28~~, 17, 7, 52, 16, 48, 68, 3, 26, 29, 53, 55, 45

각 노드가 4개 이하의 키를 가지고 있어 아직 균형 유지된다.

       [ 8 ]
      /     \
[1, 2, 6]   [12, 14, 25, 28]

6. 새로운 키 17 삽입 -> 노드 분할 및 프로모션

17은 루트(8)보다 크므로 오른쪽 서브트리로 가야 한다.
현재 오른쪽 노드에는 [12, 14, 25, 28]이 저장되어 있다.
차수 5이기에 최대 4개의 키까지만 저장 가능하므로, 새로운 키 17을 추가하면 [12, 14, 17, 25, 28]이 되는데, 이는 한 노드에 허용된 키 개수를 초과한다.
따라서 중앙값 17을 선택하여 루트로 승격(Promotion)하고, 기존 노드를 두 개로 분할(Split)한다.

       [ 8  17 ]
      /    |    \
[1,2,6] [12,14] [25,28]

7. 새로운 키 7, 52, 16, 48이 추가
~~1, 12, 8, 2, 25, 6, 14, 28, 17, 7, 52, 16, 48~~, 68, 3, 26, 29, 53, 55, 45

     [      8         17    ]
      /         |         \
[1, 2, 6, 7] [12, 14, 16] [25, 28, 48, 52]

이 과정에서 아직 분할(Split) 필요 없음, 왜냐하면 각 노드가 최대 4개의 키를 가질 수 있기 때문이다.

8. 새로운 키 68 삽입 -> 노드 분할 및 프로모션

이제 새로운 키 68을 추가하면 [25, 28, 48, 52, 68]이 되면서 최대 키 개수(4개 제한)를 초과하게 된다.
따라서 중앙값 48을 새로운 부모 노드로 승격(Promotion)하고, 노드를 두 개로 분할(Split)해야 한다.

    [     8      17     48    ]
      /      |      |      \
[1,2,6,7] [12,14,16] [25,28] [52,68]

9. 새로운 키 3 삽입 -> 노드 분할 및 프로모션

3은 루트(8)보다 작으므로 왼쪽 서브트리 [1, 2, 6, 7]으로 이동해야 한다.
3을 추가하면 [1, 2, 3, 6, 7]이 된다.
차수(order) 5의 B-Tree에서 한 노드에 4개의 키만 저장 가능하므로, 3을 추가하면 최대 개수를 초과한다.
따라서 중앙값 3을 루트로 올리고, 기존 노드를 두 개로 분할해야 한다.

   [    3     8      17        48    ]
    /    /      /          \       \
[1,2]  [6,7] [12,14,16] [25,28] [52,68]

10. 리프(leaf) 노드에 키들 추가

26 추가 → 25, 28이 있는 리프 노드로 이동 → [25, 26, 28]이 됨.
29 추가 → 28이 있는 노드의 오른쪽에 삽입 → [25, 26, 28, 29]가 새로운 리프 노드가 됨.
53 추가 → 52, 68이 있는 리프 노드로 이동 → [52, 53, 68]이 됨.
55 추가 → [52, 53, 68] 노드로 이동 → [52, 53, 55,68]이 됨.

   [   3      8         17         48   ] 
    /   \         /          \        \
[1,2] [6,7] [12,14,16] [25,26,28,29] [52,53,55,68]

11. 새로운 키 45 삽입 -> 노드 분할 및 프로모션

45는 루트(48)보다 작으므로 왼쪽으로 이동.
45는 [25,26,28,29]가 있는 리프 노드로 들어가야 함.
[25,26,28,29]는 이미 최대 키 개수(4개)를 가지고 있어 45를 추가하면 오버플로우 발생.
따라서 중앙값 28을 부모 노드로 올리고, 기존 노드를 두 개로 분할(Split)해야 함.

📌 중앙값 28을 부모 노드로 올림.

기존 [25,26,28,29]를 [25,26]과 [29, 45]로 나눔.
부모 노드 [3, 8, 17, 48]에 28이 추가됨.
부모 노드가 키 개수 제한(4개 초과)을 넘어서므로 다시 분할이 필요함.
부모 노드들의 중앙값 17이 최상위 루트로 승격되면서 트리가 분할됨.

              [    17     ]
            /           \
  [   3   8  ]         [      28      48    ]
   /    |    \             /      |       \
[1,2] [6,7] [12,14,16] [25,26] [29,45] [52,53,55,68]

4) B-Tree에서 키 삽입 (Inserting into a B-Tree)

1. 새로운 키를 리프(Leaf) 노드에 삽입하려고 시도한다.

B-Tree에서는 항상 리프 노드에 키가 추가된다.

2. 리프 노드가 가득 차면(Split 발생)

리프 노드의 키 개수가 제한을 초과하면 노드를 두 개로 분할(Split) 해야 한다.
가운데 키(Middle Key)를 부모 노드로 올리고, 나머지 키들을 두 개의 새로운 노드로 나눈다.

3. 부모 노드도 가득 차면 추가 분할

만약 부모 노드가 가득 차면 부모 노드도 분할해야 한다.
가운데 키를 더 상위 부모로 올리고, 나머지를 두 개의 노드로 나눈다.

4. 이 과정이 루트까지 반복될 수 있다.

분할 과정이 계속 위로 올라가면서 최종적으로 루트까지 분할이 발생할 수 있다.

5. 루트가 분할되면 트리의 높이가 증가한다.

루트까지 분할이 진행되면 중앙 키가 새로운 루트가 되면서 트리의 높이가 1 증가한다.
이 과정을 통해 B-Tree는 항상 균형을 유지하면서도 크기가 확장될 수 있다.

5) B-Tree에서의 삭제 (Removal in B-Tree)

: B-Tree에서 키를 삭제하는 과정은 트리의 균형을 유지하는 것이 핵심이다.

📌 Case 1: 단순 리프(Leaf) 노드 삭제

삭제할 키가 리프 노드에 있고, 최소 개수를 유지할 수 있는 경우이다.
이 경우 단순히 해당 키를 삭제하면 끝난다.

        [12  29  52]
       /    |    |    \
[2 7 9]  [15 22]  [31 43]  [56 69 72]

키 2를 삭제하면 [7,9]가 남아서 최소 개수를 만족한다.
결과: 2를 그냥 삭제하면 끝.
트리는 그대로 유지됨.

📌 Case 2: 내부(Non-Leaf) 노드 삭제

삭제할 키가 내부 노드에 있는 경우, 트리의 구조를 유지해야 하므로 대체할 키가 필요하다.
B-Tree의 성질에 따라 전임자(predecessor) 또는 후임자(successor) 중 하나를 대체하여 삭제한다.
전임자(predecessor): 삭제할 키보다 바로 작은 값
후임자(successor): 삭제할 키보다 바로 큰 값

        [12  29  52]
       /    |    |    \
[7 9]  [15 22]  [31 43]  [56 69 72]

52를 삭제하려고 하면, 후임자 56을 선택하여 52를 대체한다.
56이 원래 있던 위치에서 삭제된다.

변경된 트리:

        [12  29  56]
       /    |    |    \
[7 9]  [15 22]  [31 43]  [69 72]

균형을 유지하면서 삭제 성공.

📌 Case 3: 형제(Sibling)에서 키를 빌릴 수 있는 경우

삭제 후 리프 노드의 키 개수가 최소 개수보다 적어지면, 형제 노드에서 키를 빌릴 수 있는지 확인한다.
형제 노드가 충분한 키를 가지고 있다면, 부모 노드에서 키를 내려주고 형제에서 하나 가져온다.

        [12  29]
       /    |    \
[7 9]  [15 22]  [31 43 56 69]

키 22를 삭제하면 [15]만 남아 최소 개수를 만족하지 못함.
형제 [31, 43, 56, 69]가 충분한 키를 가지고 있으므로, 부모 노드에서 29를 내려주고 형제에서 31을 올린다.

변경된 트리:

        [12  31]
       /    |    \
[7 9]  [15 29]  [43 56 69]

트리는 균형을 유지하면서 수정됨.

📌 Case 4: 형제와 병합(Merge)해야 하는 경우

삭제 후 리프 노드의 키 개수가 최소 개수보다 적어지는데, 형제도 여유 키가 없다면 병합(Merge) 해야 한다.
이 과정에서 부모 노드의 키도 함께 내려오게 된다.

        [12  29  56]
       /    |    |    \
[7 9]  [15 22]  [31 43]  [69 72]

72를 삭제하면 [69]만 남아 최소 개수보다 부족해진다.
형제 노드도 최소 키 개수만 가지고 있어, 키를 빌려올 수 없다.
따라서 69와 31, 43을 병합하고, 부모 노드에서 56을 내려보낸다.
부모 노드에서 56이 사라졌으므로, [12 29]만 남아 트리의 균형이 유지된다.

변경된 트리:
        [12  29]
       /    |    \
[7 9]  [15 22]  [31 43 56 69]

트리가 한 단계 줄어들며 병합 완료.

최소 자식 개수 : [m/2]
최소 키 개수 : 최소 자식 개수 - 1

6) B-Tree 분석 (Analysis of B-Trees)

: B-Tree의 최대 아이템(키) 개수를 분석하는 과정, 차수(order) m과 높이(height) h를 기준으로 트리에 포함될 수 있는 최대 아이템 개수를 구하기

📌 1. 각 레벨의 키 개수 계산

B-Tree에서 각 레벨에 존재할 수 있는 최대 키 개수를 계산

루트 노드(root):

루트는 최소한 1개의 키를 가져야 하지만, 최대 (m-1)개의 키를 가질 수 있다.
따라서 루트 노드의 최대 키 개수는 m - 1이다.

레벨 1 (첫 번째 자식 레벨):

루트 노드가 m개의 자식을 가질 수 있으므로, 레벨 1의 최대 노드 개수는 m이다.
각 노드는 최대 (m-1)개의 키를 가질 수 있다.
따라서 레벨 1의 최대 키 개수는 m * (m-1)이다.

레벨 2 (두 번째 자식 레벨):

레벨 1의 m개 노드는 각각 최대 m개의 자식을 가질 수 있다.
따라서 레벨 2의 노드 개수는 m²개이다.
각 노드는 최대 (m-1)개의 키를 가지므로, 레벨 2의 최대 키 개수는 m² * (m-1)이다.

레벨 h (높이가 h인 레벨):

레벨 h의 노드 개수는 m^h개이다.
각 노드는 (m-1)개의 키를 가지므로, 레벨 h의 최대 키 개수는 m^h * (m-이다.

📌 2. 전체 B-Tree의 최대 키 개수
: B-Tree 전체에서 가질 수 있는 총 키 개수를 구하는 공식은 다음과 같다.
총 키 개수 = (1+𝑚+𝑚^2+𝑚^3+⋯+𝑚^ℎ)×(𝑚−1)

이것은 등비수열의 합 공식을 이용해 다음과 같이 정리할 수 있다.
총 키 개수=𝑚^(ℎ+1)−1

7) B-Tree를 사용하는 이유 (Reasons for using B-Trees)

: B-Tree는 디스크 기반 데이터 구조에서 효율적인 검색과 저장을 위해 사용된다.

📌 1. 디스크 읽기 비용 감소

디스크에서 데이터를 검색할 때, 한 번의 디스크 접근 비용이 크다. 하지만 한 번의 디스크 읽기에서 많은 데이터를 가져올 수 있으므로, 연속된 데이터를 함께 읽는 것이 효율적이다.
B-Tree의 차수(order)가 클수록 한 노드에서 더 많은 키를 저장할 수 있어, 디스크 접근 횟수를 줄일 수 있다. (예를 들어, 차수 m=101인 B-Tree는 한 번의 디스크 읽기로 하나의 노드를 가져올 수 있다. 높이(h)가 3인 경우, 최대 101^4 - 1개(약 100억 개)의 아이템을 저장할 수 있으며, 최악의 경우에도 3번의 디스크 접근으로 원하는 데이터를 찾을 수 있다. (단, 루트 노드는 메모리에 있다고 가정))

📌 2. 균형 잡힌 트리 구조

m = 3인 경우, 2-3 트리(2-3 tree)가 된다.
- 2-3 트리에서는 각 내부 노드가 2개 또는 3개의 자식을 가질 수 있다.
- 즉, 하나의 노드가 1개 또는 2개의 키를 가질 수 있다.
B-Tree는 항상 균형을 유지한다.
- 모든 리프 노드(leaf node)는 같은 깊이에 위치한다.
- 따라서 트리의 높이가 낮아지고, 탐색 속도가 일정하게 유지된다.

8) 트리 구조 비교 (Comparing Trees)

1️⃣ 이진 트리 (Binary Trees)

균형을 유지하지 않으면 성능이 저하될 수 있다.
일반적인 이진 탐색 트리(BST)는 삽입/삭제 시 균형이 깨질 가능성이 있다.
균형이 깨지면 탐색 시간이 최악의 경우 O(n)까지 증가할 수 있다.
AVL 트리
엄격한 균형 조건을 유지하는 이진 탐색 트리이다.
삽입/삭제 시 균형을 맞추기 위한 추가적인 회전 연산(Rotation)이 필요하다.
균형 문제를 해결하여 항상 O(log n)의 탐색 성능을 유지한다.
힙(Heap)
균형을 유지하지만, 키를 정렬하지 않는다.
우선순위 큐(Priority Queue)에서 최댓값/최솟값을 빠르게 찾는 용도로 사용된다.
이진 힙(Binary Heap)의 경우 트리 높이가 O(log n)으로 유지되며, 삽입과 삭제가 효율적이다.

2️⃣ 다항 트리 (Multi-way Trees)

B-Tree는 다항 트리(m-way tree)의 한 종류이다.
각 노드는 여러 개의 키와 자식 노드를 가질 수 있다.
차수(m)에 따라 노드당 자식의 개수가 결정된다.
일반적인 이진 탐색 트리보다 트리의 높이가 낮아져 디스크 접근 횟수가 줄어든다.
데이터베이스, 파일 시스템 등 디스크 기반 저장 장치에서 널리 사용된다.
2-3 트리(혹은 3-way B-Tree)
항상 균형을 유지하는 이진 탐색 트리와 유사하다.
AVL 트리처럼 균형을 맞추지만, 삽입과 삭제 연산이 더 간단하다.
AVL 트리는 균형을 맞추기 위해 회전(Rotation)이 필요하지만,
2-3 트리는 키 이동(Key Promotion)과 분할(Split)로 균형을 유지한다.

✅ 결론

이진 트리(BST)는 불균형해질 수 있지만, AVL 트리와 같은 균형 트리로 해결 가능하다.
힙(Heap)은 정렬이 아닌 우선순위 처리를 위해 사용된다.
B-Tree는 높은 차수를 가지는 다항 트리로, AVL 트리보다 효율적이며, 디스크 접근이 많은 시스템에서 유리하다.
2-3 트리는 AVL 트리의 복잡한 균형 조정 없이도 균형을 유지하는 대표적인 B-Tree 구조이다.

OOSEDUS

성장 가능성 만땅 개발블로그

다음 포스트