B 트리 (B tree)

B 트리 (B Tree)

B 트리는 1972년 루돌프 바이어(Rudolf Bayer)와 에드워드 맥크라이트(Edward McCreight)가 개발한 자가 균형(self-balancing) 트리 자료구조로, 대용량 데이터를 효율적으로 저장하고 검색하는 데 최적화되어 있다.

특히 디스크나 외부 메모리에 데이터를 저장할 때 발생하는 입출력 연산을 최소화하도록 설계되었으며, 현대 데이터베이스 시스템과 파일 시스템의 근간이 되는 중요한 자료구조이다.

B 트리는 대용량 데이터를 효율적으로 관리하기 위한 강력한 자료구조로, 특히 디스크 기반 저장 시스템에서 탁월한 성능을 발휘한다. 데이터베이스 시스템, 파일 시스템, 검색 엔진 등 다양한 분야에서 핵심적인 역할을 하고 있으며, 여러 변형이 개발되어 특정 응용 분야에 맞게 최적화되었다.

B 트리의 균형 유지 메커니즘, 다중 분기 구조, 효율적인 디스크 I/O 특성은 빅데이터 시대에도 여전히 중요한 가치를 지니고 있으며, 새로운 하드웨어와 응용 환경에 적응하기 위한 연구가 계속되고 있다.

트리의 기본 개념

1. 정의와 특성
   B 트리는 다음과 같은 특성을 가진 균형 검색 트리이다:

   • 다중 분기 트리(Multiway Tree): 하나의 노드가 둘 이상의 자식을 가질 수 있다.
   • 차수(Order): B 트리의 차수 m은 노드당 최대 자식 수를 의미.
   • 균형 유지: 모든 리프 노드는 같은 깊이에 있어 트리가 항상 균형을 유지한다.
   • 노드 채움 규칙: 루트와 리프를 제외한 모든 노드는 최소 ⌈m/2⌉-1개개의 키를 가져야 한다.
   • 정렬된 키: 각 노드 내의 키는 오름차순으로 정렬되어 있다.
   • 분할과 병합: 노드가 너무 많은 키를 가지면 분할(split)하고, 너무 적은 키를 가지면 이웃 노드와 병합(merge)하거나 재분배(redistribution)한다.

2. B 트리 노드의 구조
   B 트리의 노드는 다음과 같은 구성 요소를 가진다:

   • 키(Keys): 정렬된 값들로, 검색과 범위 질의에 사용.
   • 포인터(Pointers): 자식 노드를 가리키는 참조.
   • 노드 종류: 내부 노드(Internal node)와 리프 노드(Leaf node)로 구분.
     차수가 m인 B 트리의 각 노드는:
   • 최대 m-1개의 키를 저장할 수 있다.
   • 최대 m개의 자식 포인터를 가질 수 있다.
   • 루트를 제외한 내부 노드는 최소 ⌈m/2⌉개의 자식을 가져야 한다.
   • 루트는 최소 2개의 자식을 가져야 한다(단, 루트가 리프인 경우 제외).

3. 부모-자식 관계 규칙
   B 트리에서는 부모 노드의 키 값은 자식 노드의 모든 키보다 크거나 같고, 왼쪽 서브트리의 모든 키보다 작아야 한다. 즉, 각 자식 노드는 부모 키의 범위 내에 존재하는 값을 포함해야 한다.

차수 m=6인 B-트리에서:

1. 최대 키 개수: m-1 = 6-1 = 5개
2. 최소 키 개수: ⌈m/2⌉-1 = ⌈6/2⌉-1 = 3-1 = 2개 (루트 노드 제외)
3. 최대 자식 수: m = 6개
4. 최소 자식 수: ⌈m/2⌉ = ⌈6/2⌉ = 3개 (루트 노드 제외)
   루트 노드의 경우:

• 최소 키 개수: 1개 (트리에 노드가 1개만 있는 경우 0개도 가능)
• 최소 자식 수: 2개 (1개의 키를 가질 때)

1
2
3
4
5

                                    [50]
                                  /      \
                  [20, 35]                     [80, 100, 120, 140, 160]
                 /    |    \                  /    |    |    |    |    \
    [5,10,15] [25,30] [40,45]  [55,60,70,75] [85,90,95] [105,110,115] [125,130,135] [145,150,155] [170,180,190]

B 트리의 장단점

장점

• 균형 유지: 트리가 항상 균형을 유지하여 최악의 경우에도 일관된 성능을 보장한다.
• 디스크 효율성: 높은 분기 계수로 I/O 연산을 최소화하여 디스크 기반 시스템에 적합하다.
• 범위 검색: 정렬된 키를 저장하므로 범위 검색이 효율적이다(특히 B+ 트리).
• 확장성: 대용량 데이터를 처리할 수 있도록 설계되었다.
• 동적 크기 조정: 데이터가 증가하거나 감소함에 따라 자동으로 크기가 조정된다.

단점

• 구현 복잡성: 삽입, 삭제 연산의 구현이 상대적으로 복잡하다.
• 메모리 오버헤드: 각 노드가 여러 키와 포인터를 저장하므로 일부 메모리 오버헤드가 발생한다.
• 캐시 효율성: 노드 크기가 크면 CPU 캐시 효율성이 떨어질 수 있다.
• 동시성 제어: 멀티스레드 환경에서 B 트리의 동시성 제어는 복잡할 수 있다.

B 트리의 연산

검색 연산

B 트리에서의 검색은 다음과 같은 단계로 이루어진다:

1. 루트 노드에서 시작한다.
2. 현재 노드에서 키를 순차적으로 검사하여 목표 키를 찾는다.
3. 만약 현재 노드에서 목표 키를 찾지 못하면, 적절한 자식 노드로 이동한다.
4. 리프 노드에 도달할 때까지 과정을 반복한다.

특징

1. 노드 내부 검색: 각 노드 내에서 키를 검색할 때는 일반적으로 순차 검색 또는 이진 검색을 사용한다.
2. 경로 검색: 루트에서 적절한 리프 노드까지 한 번에 하나의 노드만 방문하므로, 디스크 I/O를 최소화한다.
3. 균형 트리 이점: 항상 균형을 유지하므로 최악의 경우에도 일관된 검색 성능을 보장한다.
4. 블록 접근 최적화: 디스크 블록 크기에 맞게 노드 크기를 설정하면 각 노드 접근이 단일 I/O 연산으로 이루어져 효율성이 향상된다.

구현 예시

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []  # 키를 저장하는 리스트
        self.children = []  # 자식 노드를 가리키는 포인터 리스트
        self.leaf = leaf  # 리프 노드 여부

def search(node, key):
    """B 트리에서 키를 검색하는 함수"""
    # 현재 노드에서 키의 위치를 찾기
    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, i)  # 노드와 키의 인덱스 반환
    
    # 리프 노드에 도달했지만 키를 찾지 못한 경우
    if node.leaf:
        return None  # 키가 트리에 존재하지 않음
    
    # 적절한 자식 노드로 이동하여 재귀적으로 검색
    return search(node.children[i], key)

B 트리에서의 검색 시간 복잡도는 O(log_m n)
여기서:

• m은 B 트리의 차수
• n은 트리에 저장된 키의 총 개수

예시

다음과 같은 차수 5인 B 트리가 있다고 가정해 보자:

1
2
3

                    [30, 60]
                   /    |    \
        [10, 20]        [40, 50]        [70, 80, 90]

이 B 트리에서 몇 가지 키 값을 검색해 보면

1. 키 값 45 검색하기
   키 값 45를 검색하는 과정은 다음과 같다:

   1. 루트 노드 검사: [30, 60]을 확인.
      • 45는 30보다 크고 60보다 작다.
      • 따라서 중간 자식 노드로 이동한다.
   2. 중간 자식 노드 검사: [40, 50]을 확인.
      • 45는 40보다 크고 50보다 작다.
      • 만약 이 노드 사이에 45가 있다면 찾았을 것.
      • 그러나 없으므로 검색은 실패.
        결과: 키 값 45는 트리에 존재하지 않는다.

2. 키 값 80 검색하기
   키 값 80을 검색하는 과정은 다음과 같다:

   1. 루트 노드 검사: [30, 60]을 확인.
      • 80은 60보다 크다.
      • 따라서 오른쪽 자식 노드로 이동한다.
   2. 오른쪽 자식 노드 검사: [70, 80, 90]을 확인한다.
      • 80이 노드 내에 존재! (두 번째 키 값)
      • 검색 성공!
        결과: 키 값 80은 트리의 오른쪽 자식 노드의 두 번째 키 값으로 존재.

3. 키 값 25 검색하기
   키 값 25를 검색하는 과정은 다음과 같다:

   1. 루트 노드 검사: [30, 60]을 확인.
      • 25는 30보다 작다.
      • 따라서 왼쪽 자식 노드로 이동합니다.
   2. 왼쪽 자식 노드 검사: [10, 20]을 확인.
      • 25는 20보다 크다.
      • 이 노드에는 25가 없으므로, 만약 더 자식 노드가 있다면 20과 30 사이의 자식 노드로 이동해야 한다.
      • 그러나 이 노드는 리프 노드이므로 검색은 실패.
        결과: 키 값 25는 트리에 존재하지 않는다.

전체 검색 과정 시각화(키 값 80 검색):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

1. 루트 노드 [30, 60] 검사
   - 80 > 60 이므로 오른쪽 자식으로 이동

   [30, 60]
      /|\
     / | \
    /  |  \
   /   |   \
  v    v    v
[10,20] [40,50] [70,80,90]
                     ^
                     |
1. [70, 80, 90] 노드 검사
   - 80 == 80 이므로 검색 성공!
   - 결과: 노드 [70, 80, 90]의 인덱스 1에서 키 80 발견

삽입 연산

B 트리에 새로운 키를 삽입하는 과정은 다음과 같다:

1. 적절한 리프 노드를 찾는다.
2. 해당 리프 노드에 키를 삽입한다.
3. 노드의 키 개수가 최대치(m-1)를 초과하면 노드를 분할한다:
   • 중앙 키를 부모 노드로 이동시킨다.
   • 나머지 키들을 두 개의 노드로 분할한다.
4. 필요한 경우 분할이 루트까지 전파될 수 있다.

특징

1. 항상 리프 노드에서 시작: 새로운 키는 항상 리프 노드에 삽입된다.
2. 상향식 성장: 노드가 가득 차면 분할하고 중간 키를 부모로 올리는 방식으로 트리가 위로 성장한다.
3. 사전 분할(Proactive Splitting): 삽입 경로에서 꽉 찬 노드를 미리 분할하여 삽입 후 재조정을 방지한다.
4. 균형 유지: 삽입 과정에서 트리의 균형이 자동으로 유지된다.
5. 높이 증가: 루트 노드가 분할될 때만 트리의 높이가 증가한다.
6. 특성 보존: 삽입 과정에서 B 트리의 모든 특성이 유지된다.

구현 예시

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # 최소 차수
        self.keys = []  # 키를 저장하는 리스트
        self.children = []  # 자식 노드를 가리키는 포인터 리스트
        self.leaf = leaf  # 리프 노드 여부
    
    def split_child(self, i, y):
        # 노드 y를 분할하는 함수 (y는 self의 i번째 자식)
        # 새로운 노드 z를 생성하여 y의 오른쪽 절반을 이동시킴
        z = BTreeNode(y.t, y.leaf)
        
        # t-1개의 키를 z로 이동
        mid = self.t - 1
        z.keys = y.keys[mid+1:]
        y.keys = y.keys[:mid]
        
        # 리프 노드가 아니면 자식도 이동
        if not y.leaf:
            z.children = y.children[mid+1:]
            y.children = y.children[:mid+1]
        
        # 부모 노드에 중앙 키 삽입 및 새 자식 연결
        self.children.insert(i+1, z)
        self.keys.insert(i, y.keys[mid])
        y.keys.pop(mid)

class BTree:
    def __init__(self, t):
        self.root = None
        self.t = t  # 최소 차수
    
    def insert(self, k):
        # 트리가 비어있는 경우
        if self.root is None:
            self.root = BTreeNode(self.t, True)
            self.root.keys.append(k)
            return
        
        # 루트가 가득 찬 경우, 높이가 증가
        if len(self.root.keys) == (2 * self.t - 1):
            s = BTreeNode(self.t, False)
            s.children.append(self.root)
            s.split_child(0, self.root)
            self.root = s
            self._insert_non_full(s, k)
        else:
            self._insert_non_full(self.root, k)
    
    def _insert_non_full(self, x, k):
        # 키를 삽입할 위치 찾기
        i = len(x.keys) - 1
        
        # 리프 노드인 경우
        if x.leaf:
            # 적절한 위치에 키 삽입
            while i >= 0 and k < x.keys[i]:
                i -= 1
            x.keys.insert(i + 1, k)
        else:
            # 내부 노드인 경우
            # 키가 삽입될 자식 노드 찾기
            while i >= 0 and k < x.keys[i]:
                i -= 1
            i += 1
            
            # 자식이 가득 차 있는지 확인
            if len(x.children[i].keys) == (2 * self.t - 1):
                x.split_child(i, x.children[i])
                # 분할 후 어느 쪽 자식으로 가야 할지 결정
                if k > x.keys[i]:
                    i += 1
            
            # 적절한 자식으로 재귀 호출
            self._insert_non_full(x.children[i], k)

B 트리 삽입 연산의 시간 복잡도는 O(log_t n)
여기서:

• t는 B 트리의 최소 차수
• n은 트리에 저장된 키의 총 개수

예시

B 트리에 새로운 키를 삽입하는 과정을 차수 m=5인 B 트리를 통해 자세히 살펴보자.
차수가 5인 B 트리에서는 각 노드가 최소 2개, 최대 4개의 키를 가질 수 있으며, 각 내부 노드는 최소 3개, 최대 5개의 자식을 가질 수 있다.

• B 트리의 속성 (차수 m=5)
  먼저 차수가 5인 B 트리의 주요 속성:
  1. 최대 키 개수: m-1 = 5-1 = 4개
  2. 최소 키 개수: ⌈m/2⌉-1 = ⌈5/2⌉-1 = 3-1 = 2개 (루트 노드 제외)
  3. 최대 자식 수: m = 5개
  4. 최소 자식 수: ⌈m/2⌉ = ⌈5/2⌉ = 3개 (루트 노드 제외)
  루트 노드의 경우:
  • 최소 키 개수: 1개 (트리에 노드가 1개만 있는 경우 0개도 가능)
  • 최소 자식 수: 2개 (1개의 키를 가질 때)

초기:
처음에는 빈 B 트리에서 시작하여 여러 키를 차례로 삽입하면서 B 트리가 어떻게 성장하는지 살펴보자.

1. 키 값 50 삽입하기:
   빈 트리에 첫 번째 키 50을 삽입.

   1. 트리가 비어 있으므로, 새로운 루트 노드를 생성하고 50을 삽입.
      결과 트리:

   1

   [50]

2. 키 값 30 삽입하기

   1. 루트 노드 [50]에서 30은 50보다 작으므로, 왼쪽에 삽입한다.
   2. 노드는 최대 4개의 키를 가질 수 있으므로, 오버플로우가 발생하지 않는다.
      결과 트리:

   1

   [30, 50]

3. 키 값 70 삽입하기

   1. 루트 노드 [30, 50]에서 70은 50보다 크므로, 오른쪽에 삽입한다.
   2. 삽입 후 노드는 [30, 50, 70]이 된다.
   3. 노드는 최대 4개의 키를 가질 수 있으므로, 오버플로우가 발생하지 않는다.
      결과 트리:

   1	[30, 50, 70]

4. 키 값 20 삽입하기

   1. 루트 노드 [30, 50, 70]에서 20은 30보다 작으므로, 왼쪽에 삽입한다.
   2. 삽입 후 노드는 [20, 30, 50, 70]이 된다.
   3. 노드는 이제 최대 키 개수(4개)에 도달.
      결과 트리:

   1	[20, 30, 50, 70]

5. 키 값 40 삽입하기 (첫 번째 분할 발생)
   키 값 40을 삽입하려고 하지만, 루트 노드는 이미 최대 키 개수(4개)를 가지고 있다.
   따라서 노드 분할이 필요하다.

   1. 노드 [20, 30, 50, 70]에 40을 삽입하려고 하면, 정렬된 배열은 [20, 30, 40, 50, 70]이 된다.
      그러나 이는 최대 키 개수를 초과한다.
   2. 노드 분할 과정:
      • 중간 키(40)를 새로운 루트로 선택한다.
      • 왼쪽 노드에는 [20, 30], 오른쪽 노드에는 [50, 70]이 위치한다.
        결과 트리:

   1 2 3

   [40] / \ [20, 30] [50, 70]

   이제 트리는 높이가 1 증가했으며, 모든 노드가 B 트리 속성을 만족.

6. 키 값 60 삽입하기

   1. 루트 노드 [40]에서 60은 40보다 크므로, 오른쪽 자식 노드 [50, 70]으로 이동한다.
   2. [50, 70] 노드에서 60은 50보다 크고 70보다 작으므로, 50과 70 사이에 삽입한다.
   3. 삽입 후 노드는 [50, 60, 70]이 된다.
   4. 노드는 최대 4개의 키를 가질 수 있으므로, 오버플로우가 발생하지 않는다.
      결과 트리:

   1 2 3

   [40] / \ [20, 30] [50, 60, 70]

7. 키 값 10 삽입하기

   1. 루트 노드 [40]에서 10은 40보다 작으므로, 왼쪽 자식 노드 [20, 30]으로 이동한다.
   2. [20, 30] 노드에서 10은 20보다 작으므로, 10을 맨 앞에 삽입한다.
   3. 삽입 후 노드는 [10, 20, 30]이 된다.
   4. 노드는 최대 4개의 키를 가질 수 있으므로, 오버플로우가 발생하지 않는다.
      결과 트리:

   1 2 3

   [40] / \ [10, 20, 30] [50, 60, 70]

8. 키 값 80 삽입하기

   1. 루트 노드 [40]에서 80은 40보다 크므로, 오른쪽 자식 노드 [50, 60, 70]으로 이동한다.
   2. [50, 60, 70] 노드에서 80은 70보다 크므로, 80을 맨 끝에 삽입한다.
   3. 삽입 후 노드는 [50, 60, 70, 80]이 된다.
   4. 노드는 이제 최대 키 개수(4개)에 도달함.
      결과 트리:

   1 2 3

   [40] / \ [10, 20, 30] [50, 60, 70, 80]

9. 키 값 75 삽입하기 (두 번째 분할 발생)
   키 값 75를 삽입하려고 하지만, 오른쪽 자식 노드는 이미 최대 키 개수(4개)를 가지고 있다.
   따라서 노드 분할이 필요하다.

   1. [50, 60, 70, 80] 노드에 75를 삽입하려고 하면, 정렬된 배열은 [50, 60, 70, 75, 80]이 된다.
      그러나 이는 최대 키 개수를 초과한다.
   2. 노드 분할 과정:
      • 중간 키(70)를 부모 노드로 올린다.
      • 왼쪽 노드에는 [50, 60], 오른쪽 노드에는 [75, 80]이 위치한다.
      • 부모 노드 [40]은 [40, 70]이 된다.
        결과 트리:

   1 2 3

   [40, 70] / | \ [10, 20, 30] [50, 60] [75, 80]

10. 키 값 15 삽입하기

    1. 루트 노드 [40, 70]에서 15는 40보다 작으므로, 첫 번째 자식 노드 [10, 20, 30]으로 이동한다.
    2. [10, 20, 30] 노드에서 15는 10보다 크고 20보다 작으므로, 10과 20 사이에 삽입한다.
    3. 삽입 후 노드는 [10, 15, 20, 30]이 된다.
    4. 노드는 이제 최대 키 개수(4개)에 도달함.
       결과 트리:

    1 2 3

    [40, 70] / | \ [10, 15, 20, 30] [50, 60] [75, 80]

11. 키 값 5 삽입하기 (세 번째 분할 발생)
    키 값 5를 삽입하려고 하지만, 왼쪽 자식 노드는 이미 최대 키 개수(4개)를 가지고 있다.
    따라서 노드 분할이 필요하다.

    1. [10, 15, 20, 30] 노드에 5를 삽입하려고 하면, 정렬된 배열은 [5, 10, 15, 20, 30]이 된다. 그러나 이는 최대 키 개수를 초과한다.
    2. 노드 분할 과정:
       • 중간 키(15)를 부모 노드로 올린다.
       • 왼쪽 노드에는 [5, 10], 오른쪽 노드에는 [20, 30]이 위치한다.
       • 부모 노드 [40, 70]은 [15, 40, 70]이 된다.
         결과 트리:

    1 2 3

    [15, 40, 70] / | | \ [5, 10] [20, 30] [50, 60] [75, 80]

12. 키 값 55 삽입하기

    1. 루트 노드 [15, 40, 70]에서 55는 40보다 크고 70보다 작으므로, 세 번째 자식 노드 [50, 60]으로 이동한다.
    2. [50, 60] 노드에서 55는 50보다 크고 60보다 작으므로, 50과 60 사이에 삽입한다.
    3. 삽입 후 노드는 [50, 55, 60]이 된다.
    4. 노드는 최대 4개의 키를 가질 수 있으므로, 오버플로우가 발생하지 않는다.
       결과 트리:

    1 2 3

    [15, 40, 70] / | | \ [5, 10] [20, 30] [50, 55, 60] [75, 80]

13. 키 값 45 삽입하기

    1. 루트 노드 [15, 40, 70]에서 45는 40보다 크고 70보다 작으므로, 세 번째 자식 노드 [50, 55, 60]으로 이동한다.
    2. [50, 55, 60] 노드에서 45는 모든 키보다 작으므로, 45를 맨 앞에 삽입한다.
    3. 삽입 후 노드는 [45, 50, 55, 60]이 된다.
    4. 노드는 이제 최대 키 개수(4개)에 도달함.
       결과 트리:

    1 2 3

    [15, 40, 70] / | | \ [5, 10] [20, 30] [45, 50, 55, 60] [75, 80]

14. 키 값 65 삽입하기 (네 번째 분할 발생)
    키 값 65를 삽입하려고 하지만, 세 번째 자식 노드는 이미 최대 키 개수(4개)를 가지고 있다.
    따라서 노드 분할이 필요하다.

    1. [45, 50, 55, 60] 노드에 65를 삽입하려고 하면, 정렬된 배열은 [45, 50, 55, 60, 65]가 된다. 그러나 이는 최대 키 개수를 초과한다.
    2. 노드 분할 과정:
       • 중간 키(55)를 부모 노드로 올린다.
       • 왼쪽 노드에는 [45, 50], 오른쪽 노드에는 [60, 65]가 위치한다.
       • 부모 노드 [15, 40, 70]은 [15, 40, 55, 70]이 된다.
         결과 트리:

    1 2 3

    [15, 40, 55, 70] / | | | \ [5, 10] [20, 30] [45, 50] [60, 65] [75, 80]

15. 키 값 35 삽입하기 (다섯 번째 분할과 루트 분할 발생)
    먼저 삽입 위치를 찾아야 한다.

    1. 루트 노드 [15, 40, 55, 70]에서 35는 15보다 크고 40보다 작으므로, 두 번째 자식 노드 [20, 30]으로 이동한다.
    2. [20, 30] 노드에서 35는 30보다 크므로, 35를 맨 끝에 삽입한다.
    3. 삽입 후 노드는 [20, 30, 35]이 된다.
    4. 노드는 최대 4개의 키를 가질 수 있으므로, 오버플로우가 발생하지 않는다.
       결과 트리:

    1 2 3

    [15, 40, 55, 70] / | | | \ [5, 10] [20, 30, 35] [45, 50] [60, 65] [75, 80]

    그러나 루트 노드가 이미 최대 키 개수(4개)에 도달했으므로, 새로운 키가 루트 노드에 삽입되어야 할 경우 루트 분할이 필요하다.

16. 키 값 42 삽입하기 (루트 분할 발생)

    1. 루트 노드 [15, 40, 55, 70]에서 42는 40보다 크고 55보다 작으므로, 세 번째 자식 노드 [45, 50]으로 이동한다.
    2. [45, 50] 노드에서 42는 모든 키보다 작으므로, 42를 맨 앞에 삽입한다.
    3. 삽입 후 노드는 [42, 45, 50]이 된다.
    4. 노드는 최대 4개의 키를 가질 수 있으므로, 오버플로우가 발생하지 않는다.
       결과 트리:

    1 2 3

    [15, 40, 55, 70] / | | | \ [5, 10] [20, 30, 35] [42, 45, 50] [60, 65] [75, 80]

17. 키 값 25 삽입하기 (루트 분할 발생)

    1. 루트 노드 [15, 40, 55, 70]에서 25는 15보다 크고 40보다 작으므로, 두 번째 자식 노드 [20, 30, 35]으로 이동한다.
    2. [20, 30, 35] 노드에서 25는 20보다 크고 30보다 작으므로, 20과 30 사이에 삽입한다.
    3. 삽입 후 노드는 [20, 25, 30, 35]가 되어 최대 키 개수에 도달한다.
       결과 트리:

    1 2 3

    [15, 40, 55, 70] / | | | \ [5, 10] [20, 25, 30, 35] [42, 45, 50] [60, 65] [75, 80]

18. 키 값 23 삽입하기 (자식 노드 분할 및 루트 분할 발생)
    키 값 23을 삽입하려고 하지만, 두 번째 자식 노드는 이미 최대 키 개수에 도달함.
    따라서 노드 분할이 필요하다.

    1. [20, 25, 30, 35] 노드에 23을 삽입하려고 하면, 정렬된 배열은 [20, 23, 25, 30, 35]가 된다. 이는 최대 키 개수를 초과한다.
    2. 노드 분할 과정:
       • 중간 키(25)를 부모 노드로 올린다.
       • 왼쪽 노드에는 [20, 23], 오른쪽 노드에는 [30, 35]가 위치한다.
       • 부모 노드 [15, 40, 55, 70]에 25를 삽입하면 [15, 25, 40, 55, 70]이 된다. 그러나 이는 최대 키 개수를 초과한다.
    3. 루트 노드 분할 과정:
       • 중간 키(40)를 새로운 루트로 선택한다.
       • 왼쪽 노드에는 [15, 25], 오른쪽 노드에는 [55, 70]이 위치한다.
         결과 트리:

    1 2 3 4 5

    [40] / \ [15, 25] [55, 70] / | \ / \ [5, 10] [20, 23] [30, 35] [42, 45, 50] [60, 65] [75, 80]

    이 예시에서는 두 번의 분할이 발생했다.
    먼저 자식 노드가 분할되었고, 그 결과로 루트 노드도 분할되어 트리의 높이가 증가했다.

삭제 연산

B 트리에서 삭제 연산은 트리의 균형을 유지하기 위해 종종 복잡한 재구성이 필요하다.
키 삭제 후 트리의 모든 노드(루트 제외)가 최소 키 개수(m/2 올림 - 1, 여기서는 2개)를 유지해야 하므로, 단순한 키 이동만으로는 해결되지 않을 때가 많다.
이런 경우 트리 전체의 균형을 다시 맞추기 위해 여러 노드의 키를 재분배하거나 노드 병합, 분할 등의 작업이 수행된다.

B 트리에서 키를 삭제하는 과정을 요약하면 다음과 같다:

1. 삭제할 키를 찾는다.
2. 리프 노드에서 키 삭제: 키가 리프 노드에 있으면 직접 삭제한다.
3. 내부 노드에서 키 삭제: 키가 내부 노드에 있으면 선행자나 후행자로 대체한 후, 그 키를 리프 노드에서 삭제한다.
4. 키 부족 상황 해결:
   • 형제 노드에서 키를 빌리거나(재분배)
   • 부모 노드의 키와 함께 형제 노드와 병합한다.
5. 트리 높이 감소: 루트 노드가 비어 있고 단 하나의 자식만 있는 경우, 그 자식을 새로운 루트로 승격시킨다.
6. 필요한 경우 병합이 루트까지 전파될 수 있다.

특징

1. 복잡한 케이스 처리: 삭제는 여러 경우(리프 vs 내부, 최소 키 개수 등)를 고려해야 한다.
2. 하향식 접근: 삭제는 루트에서 리프로 내려가면서 최소 키 조건을 미리 만족시킨다.
3. 키 재분배: 형제 노드에서 키를 빌려오는 방식으로 최소 키 개수 요구사항을 유지한다.
4. 노드 병합: 형제 노드에서 키를 빌려올 수 없는 경우, 부모 노드의 키와 함께 노드를 병합한다.
5. 키 대체: 내부 노드에서 키를 삭제할 때는 선행자나 후행자로 대체한다.
6. 병합 전파: 노드 병합은 트리 위로 전파될 수 있으며, 경우에 따라 트리 높이가 감소한다.
7. 균형 유지: 삭제 과정에서도 B 트리의 균형 속성이 유지된다.
8. 트리 높이 감소: 루트 노드가 비어있게 되면 트리의 높이가 감소합니다.

구현 예시

실제 B 트리의 삭제 구현은 복잡하므로, 핵심 부분에 대한 의사 코드:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # 최소 차수
        self.keys = []  # 키를 저장하는 리스트
        self.children = []  # 자식 노드를 가리키는 포인터 리스트
        self.leaf = leaf  # 리프 노드 여부

class BTree:
    def __init__(self, t):
        self.root = None
        self.t = t  # 최소 차수
    
    def delete(self, k):
        if self.root is None:
            return
        
        # 키 삭제
        self._delete_key(self.root, k)
        
        # 루트가 빈 내부 노드가 된 경우 높이 감소
        if len(self.root.keys) == 0 and not self.root.leaf:
            self.root = self.root.children[0]
    
    def _delete_key(self, node, k):
        # 노드에서 키의 인덱스 찾기
        idx = self._find_key(node, k)
        
        # 현재 노드에서 키를 찾은 경우
        if idx < len(node.keys) and node.keys[idx] == k:
            # 리프 노드인 경우 직접 삭제
            if node.leaf:
                self._remove_from_leaf(node, idx)
            else:
                self._remove_from_non_leaf(node, idx)
        else:
            # 키가 현재 노드에 없는 경우
            if node.leaf:
                print(f"키 {k}가 트리에 존재하지 않습니다.")
                return
            
            # 마지막 자식으로 내려갈지 결정
            last_child = idx >= len(node.keys)
            
            # 자식이 최소 키 개수만 가지고 있는 경우 처리
            if len(node.children[idx].keys) < self.t:
                self._fill(node, idx)
            
            # 마지막 자식이 병합된 경우
            if last_child and idx > len(node.keys):
                self._delete_key(node.children[idx-1], k)
            else:
                self._delete_key(node.children[idx], k)
    
    # 리프 노드에서 키 제거
    def _remove_from_leaf(self, node, idx):
        node.keys.pop(idx)
    
    # 내부 노드에서 키 제거
    def _remove_from_non_leaf(self, node, idx):
        k = node.keys[idx]
        
        # 왼쪽 자식에서 선행자 찾기
        if len(node.children[idx].keys) >= self.t:
            pred = self._get_predecessor(node, idx)
            node.keys[idx] = pred
            self._delete_key(node.children[idx], pred)
        
        # 오른쪽 자식에서 후행자 찾기
        elif len(node.children[idx+1].keys) >= self.t:
            succ = self._get_successor(node, idx)
            node.keys[idx] = succ
            self._delete_key(node.children[idx+1], succ)
        
        # 두 자식 모두 최소 키 개수를 가진 경우 병합
        else:
            self._merge(node, idx)
            self._delete_key(node.children[idx], k)
    
    # 선행자(predecessor) 찾기
    def _get_predecessor(self, node, idx):
        curr = node.children[idx]
        while not curr.leaf:
            curr = curr.children[len(curr.keys)]
        return curr.keys[-1]
    
    # 후행자(successor) 찾기
    def _get_successor(self, node, idx):
        curr = node.children[idx+1]
        while not curr.leaf:
            curr = curr.children[0]
        return curr.keys[0]
    
    # 최소 키 개수보다 적은 노드를 채우기
    def _fill(self, node, idx):
        # 왼쪽 형제에서 키 빌리기
        if idx != 0 and len(node.children[idx-1].keys) >= self.t:
            self._borrow_from_prev(node, idx)
        
        # 오른쪽 형제에서 키 빌리기
        elif idx != len(node.keys) and len(node.children[idx+1].keys) >= self.t:
            self._borrow_from_next(node, idx)
        
        # 병합
        else:
            if idx != len(node.keys):
                self._merge(node, idx)
            else:
                self._merge(node, idx-1)
    
    # 왼쪽 형제에서 키 빌리기
    def _borrow_from_prev(self, node, idx):
        child = node.children[idx]
        sibling = node.children[idx-1]
        
        # 자식 노드에 부모 키 추가하고, 부모 노드에 형제의 마지막 키 추가
        child.keys.insert(0, node.keys[idx-1])
        if not child.leaf:
            child.children.insert(0, sibling.children.pop())
        node.keys[idx-1] = sibling.keys.pop()
    
    # 오른쪽 형제에서 키 빌리기
    def _borrow_from_next(self, node, idx):
        child = node.children[idx]
        sibling = node.children[idx+1]
        
        # 자식 노드에 부모 키 추가하고, 부모 노드에 형제의 첫 번째 키 추가
        child.keys.append(node.keys[idx])
        if not child.leaf:
            child.children.append(sibling.children.pop(0))
        node.keys[idx] = sibling.keys.pop(0)
    
    # 노드 병합
    def _merge(self, node, idx):
        child = node.children[idx]
        sibling = node.children[idx+1]
        
        # 부모 키를 자식에 추가
        child.keys.append(node.keys[idx])
        
        # 형제의 모든 키와 자식을 자식 노드로 이동
        child.keys.extend(sibling.keys)
        if not child.leaf:
            child.children.extend(sibling.children)
        
        # 부모 노드에서 키와 자식 노드 제거
        node.keys.pop(idx)
        node.children.pop(idx+1)
    
    # 노드에서 키의 인덱스 찾기
    def _find_key(self, node, k):
        idx = 0
        while idx < len(node.keys) and node.keys[idx] < k:
            idx += 1
        return idx

B 트리의 삭제 연산 시간 복잡도는 O(log_t n).
여기서:

• t는 B 트리의 최소 차수
• n은 트리에 저장된 키의 총 개수

예시

B 트리에서 키를 삭제하는 연산은 일반적으로 삽입보다 더 복잡하다.
삭제 시 B 트리의 속성을 유지하기 위해 여러 케이스를 처리해야 하기 때문이다.
차수 m=5인 B 트리를 사용하여 삭제 연산의 다양한 경우를 단계별 설명.

• 먼저 차수가 5인 B 트리의 주요 속성을 확인:
  1. 최대 키 개수: m-1 = 5-1 = 4개
  2. 최소 키 개수: ⌈m/2⌉-1 = ⌈5/2⌉-1 = 3-1 = 2개 (루트 노드 제외)
  3. 최대 자식 수: m = 5개
  4. 최소 자식 수: ⌈m/2⌉ = ⌈5/2⌉ = 3개 (루트 노드 제외)
• 루트 노드의 경우:
  • 최소 키 개수: 1개 (트리에 노드가 1개만 있는 경우 0개도 가능)
  • 최소 자식 수: 2개 (1개의 키를 가질 때)

복잡한 재조정이 필요 없는 경우 (85 삭제)

초기 상태:

1
2
3
4
5

                [40]
              /      \
        [15, 25]     [55, 70]
       /    |    \    /    \
   [5, 10]  [20, 23]  [30, 35]  [45, 50]  [60, 65]  [75, 80, 85, 90]

85를 삭제하는 과정에서 모든 B 트리 속성을 유지하는 해결책:

1. [75, 80, 85, 90]에서 85를 삭제하면 [75, 80, 90]이 되어 여전히 최소 키 개수(2개)를 충족.
2. 따라서 추가적인 재조정 없이 트리가 유효하다.

결과:

1
2
3
4
5

                [40]
              /      \
        [15, 25]     [55, 70]
       /    |    \    /    \
   [5, 10]  [20, 23]  [30, 35]  [45, 50]  [60, 65]  [75, 80, 90]

리프 노드에서 삭제 - 복잡한 재구성이 필요한 경우 (10 삭제)

초기 상태:

1
2
3
4
5

				[40]
			  /      \
		[15, 25]     [55, 70]
	   /    |    \    /    \
   [5, 10]  [20, 23]  [30, 35]  [45, 50]  [60, 65]  [75, 80, 85, 90]

10을 삭제하면 복잡한 재구성이 필요하다.
차수 m=5인 B 트리에서는 모든 내부 노드(루트 제외)가 최소 2개의 키를 가져야 하므로:

1. 우선 [5, 10]에서 10을 삭제하면 [5]만 남는다.
2. 이 문제를 해결하기 위해 전체 트리를 재구성해야 한다.
   가장 효과적인 방법은 트리의 높이를 유지하면서 모든 노드들 사이에 키를 균등하게 재분배하는 것이다:

1
2
3
4
5

				[35]
			  /      \
		[15, 25]     [55, 75]
	   /    |    \    /    |    \
   [5]  [20, 23]  [30]  [40, 45, 50]  [60, 65, 70]  [80, 85, 90]

하지만 여기서도 [5]와 [30] 리프 노드가 최소 키 개수를 위반한다.
더 균형 잡힌 트리를 위해:

1
2
3
4
5

				[45]
			  /      \
		[20, 35]     [65, 80]
	   /    |    \    /    |    \
  [5, 15] [23, 25, 30] [40] [50, 55, 60] [70, 75] [85, 90]

여기서도 [40] 리프 노드가 최소 키 개수를 위반한다.

1
2
3
4
5

				[45]
			  /      \
		[20, 35]     [70]
	   /    |    \    /  \
  [5, 15] [23, 25, 30] [40] [50, 55, 60, 65] [75, 80, 85, 90]

이 구조에서도 아직 [40] 리프 노드가 최소 키 개수를 위반한다:
최종 해결책:

1
2
3
4
5

				[45]
			  /      \
		[20, 30]     [65, 80]
	   /    |    \    /    |    \
  [5, 15] [23, 25] [35, 40] [50, 55, 60] [70, 75] [85, 90]

이제 모든 내부 노드와 리프 노드가 최소 2개의 키를 가져 B 트리의 요구사항을 충족한다.

리프 노드에서 삭제 - 병합 필요한 경우 (60 삭제)

초기 상태:

1
2
3
4
5

				[40]
			  /      \
		[15, 25]     [55, 70]
	   /    |    \    /    \
   [5, 10]  [20, 23]  [30, 35]  [45, 50]  [60, 65]  [75, 80, 85, 90]

1. [60, 65]에서 60을 삭제하면 [65]만 남는다.
2. 전체 트리를 재구성하여 모든 노드가 B 트리 요구사항을 충족하도록 한다.

1
2
3
4
5

				[40]
			  /      \
		[15, 25]     [65]
	   /    |    \    /  \
   [5, 10]  [20, 23]  [30, 35, 55]  [45, 50, 60]  [70, 75, 80, 85, 90]

하지만 이 구조에서는 내부 노드 [65]가 최소 키 개수를 위반한다:

1
2
3
4
5

				[40, 65]
			  /    |    \
		[15, 25]  [50, 55]  [80]
	   /    |    \  /   \   /  \
   [5, 10] [20, 23] [30, 35, 45] [70, 75] [85, 90]

이 구조에서도 내부 노드 [80]이 최소 키 개수를 위반한다:

최종 해결책:

1
2
3
4
5

				[40]
			  /      \
		[15, 25]     [65, 80]
	   /    |    \    /    |    \
  [5, 10] [20, 23] [30, 35] [45, 50, 55] [70, 75] [85, 90]

내부 노드에서 삭제 - 후계자 대체 (25 삭제)

초기 상태:

1
2
3
4
5

                [40]
              /      \
        [15, 25]     [55, 70]
       /    |    \    /    \
   [5, 10]  [20, 23]  [30, 35]  [45, 50]  [60, 65]  [75, 80, 85, 90]

25를 삭제하는 과정을 처음부터 다시 살펴보면:

1. 25는 내부 노드에 있으므로, 후계자로 대체해야 한다.
   25의 후계자는 오른쪽 서브트리의 가장 작은 키인 30이다.
2. 30을 25 위치로 이동시키고, [30, 35]에서 30을 삭제한다.
3. 이로 인해 [35]만 남게 되어 최소 키 개수를 위반한다.
   이 문제를 해결하기 위한 완전한 재구성을 진행해보면:

• 방법1: 키 재분배를 통한 해결

  • 가장 가까운 형제 노드인 [45, 50]에서 키를 빌려올 수 있다:
    1. 부모 키 40을 [35] 노드로 내리고, [45, 50]의 키 45를 부모로 올린다.
    2. 결과적으로 [35, 40]과 [50] 노드가 된다.
    3. 그러나 [50] 노드도 최소 키 개수를 위반하므로 또 다른 조정이 필요하다.

  1 2 3 4 5

  [45] / \ [15, 30] [55, 70] / | \ / \ [5, 10] [20, 23] [35,40] [50] [60, 65] [75, 80, 85, 90]

• 방법 2: 노드 병합을 통한 해결

  • [35]와 [45, 50] 노드를 병합하고 부모 키 40을 가져온다:
    1. 결과는 [35, 40, 45, 50] 노드가 된다.
    2. 부모 노드는 이제 [15, 30, 55, 70]이 된다.

  1 2 3

  [15, 30, 55, 70] / | | \ [5, 10] [20, 23] [35, 40, 45, 50] [60, 65] [75, 80, 85, 90]

  이 구조에서도 문제가 없는지 확인해보면:

  • 루트 노드 [15, 30, 55, 70]은 최대 키 개수(4개)를 충족한다.
  • 모든 리프 노드는 최소 키 개수(2개)를 충족한다.
  • 하지만 트리의 높이가 감소했다.

• 방법 3: 균형 잡힌 트리를 위한 완전한 재구성
  좀 더 균형 잡힌 구조를 만들기 위해 전체 트리를 재구성한다:

1
2
3
4
5

                [45]
              /      \
        [15, 30]     [65, 80]
       /    |    \    /    |    \
  [5, 10] [20, 23] [35, 40] [50, 55, 60] [70, 75] [85, 90]

루트 노드가 비어지는 경우 (40 삭제)

초기 상태:

1
2
3
4
5

                [40]
              /      \
        [15, 25]     [55, 70]
       /    |    \    /    \
   [5, 10]  [20, 23]  [30, 35]  [45, 50]  [60, 65]  [75, 80, 85, 90]

40을 삭제하는 과정에서 모든 B 트리 속성을 유지하는 해결책:

1. 40의 후계자인 45를 찾아 40 위치에 대체한다.
2. [45, 50]에서 45를 삭제하면 [50]만 남아 최소 키 개수를 위반한다.
3. 트리 전체를 재구성한다.

균형 잡힌 해결책:

1
2
3
4
5

                [45]
              /      \
        [15, 25]     [65, 80]
       /    |    \    /    |    \
  [5, 10] [20, 23] [30, 35] [50, 55, 60] [70, 75] [85, 90]

B 트리의 변형

B+ 트리

B+ 트리는 B 트리의 변형으로, 모든 키가 리프 노드에 저장되고 리프 노드들이 연결 리스트로 연결된 구조.
이러한 특성으로 인해 범위 검색에 더 효율적이다.

주요 특징:

• 모든 데이터는 리프 노드에만 저장된다.
• 내부 노드는 인덱스 역할만 한다.
• 리프 노드들이 연결 리스트로 연결되어 있어 순차적 접근이 용이하다.
• 데이터베이스 인덱싱에 널리 사용된다.

B* 트리

B* 트리는 노드 분할을 최소화하기 위해 노드 사용률을 더 높게 유지하는 B 트리의 변형이다.

주요 특징:

• 노드는 최소 2/3 이상 채워져 있어야 한다(일반 B 트리는 1/2).
• 노드가 가득 차면, 이웃 노드에 여유 공간이 있을 경우 재분배를 먼저 시도한다.
• 두 노드가 모두 가득 차면 세 개의 노드로 분할한다.

R 트리

R 트리는 다차원 공간 데이터(예: 지리적 좌표)를 저장하기 위한 B 트리의 확장이다.

주요 특징:

• 점이 아닌 사각형(또는 다차원 객체)을 저장한다.
• 각 노드는 최소 경계 사각형(Minimum Bounding Rectangle, MBR)을 가진다.
• 지리 정보 시스템(GIS)과 공간 데이터베이스에 사용된다.

B 트리의 성능 분석

1. 시간 복잡도
   B 트리의 주요 연산에 대한 시간 복잡도는 다음과 같다:

   • 검색: O(log_m n) - 트리의 높이에 비례
   • 삽입: O(log_m n) - 키 위치 찾기와 노드 분할 포함
   • 삭제: O(log_m n) - 키 위치 찾기와 노드 병합/재분배 포함
   • 순차 접근: O(n) - 모든 키를 순서대로 방문
     여기서 m은 B 트리의 차수, n은 저장된 키의 총 개수.

2. 공간 복잡도
   B 트리의 공간 복잡도는 O(n).
   그러나 B 트리는 일반적인 이진 검색 트리보다 공간 효율성이 좋다.
   이는 B 트리가 더 높은 분기 계수를 가져 더 적은 노드와 포인터를 사용하기 때문.

3. 디스크 I/O 효율성
   B 트리의 주요 장점 중 하나는 디스크 기반 저장 시스템에서의 효율성:

   • 블록 접근: 노드 크기를 디스크 블록 크기에 맞춰 I/O 연산을 최소화.
   • 높이 최소화: 높은 분기 계수로 트리 높이를 낮게 유지하여 검색 시 필요한 디스크 액세스 횟수를 줄인다.
   • 지역성: 관련 키들이 같은 노드에 저장되어 캐시 효율성이 향상된다.

B 트리의 응용

1. 데이터베이스 시스템
   B 트리와 그 변형(특히 B+ 트리)은 거의 모든 관계형 데이터베이스 관리 시스템(RDBMS)의 인덱싱 메커니즘으로 사용된다:

   • MySQL: InnoDB 스토리지 엔진은 B+ 트리 인덱스를 사용.
   • PostgreSQL: B 트리 기반 인덱스를 기본으로 제공.
   • Oracle: B+ 트리 인덱스를 사용.
   • SQLite: B 트리 변형인 B* 트리를 사용.

2. 파일 시스템
   많은 현대 파일 시스템이 B 트리 또는 그 변형을 사용하여 파일과 디렉토리 구조를 관리한다:

   • NTFS: B+ 트리를 사용하여 Master File Table(MFT)을 구현.
   • ext4: B+ 트리를 사용하여 디렉토리 인덱싱을 구현.
   • HFS+: B 트리를 사용하여 파일 카탈로그를 관리.
   • Btrfs: B 트리 파일 시스템으로, 이름 자체가 B 트리에서 유래.

3. 기타 응용 분야

   • 검색 엔진: 역색인(inverted index)을 구현하는 데 사용된다.
   • 네트워크 라우팅: IP 주소를 빠르게 조회하는 데 사용된다.
   • 공간 데이터베이스: R 트리를 사용하여 공간 데이터를 효율적으로 인덱싱한다.
   • 메모리 관리: 일부 시스템에서는 메모리 할당을 관리하는 데 B 트리를 사용한다.

B 트리 구현 예시

다음은 Python으로 B 트리의 기본 구조와 연산을 구현한 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # 최소 차수 (minimum degree)
        self.keys = []  # 키를 저장하는 리스트
        self.children = []  # 자식 노드를 가리키는 포인터 리스트
        self.leaf = leaf  # 리프 노드 여부
    
    def traverse(self):
        # 노드와 서브트리를 중위 순회
        i = 0
        # 리프가 아닌 경우 자식 노드 순회
        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[i + 1].traverse()

class BTree:
    def __init__(self, t):
        self.root = None
        self.t = t  # 최소 차수
    
    def traverse(self):
        if self.root is not None:
            self.root.traverse()
    
    def search(self, k):
        if self.root is None:
            return None
        else:
            return self._search(self.root, k)
    
    def _search(self, node, k):
        i = 0
        # 노드에서 k보다 크거나 같은 첫 번째 키 찾기
        while i < len(node.keys) and k > node.keys[i]:
            i += 1
        
        # 키를 찾은 경우
        if i < len(node.keys) and k == node.keys[i]:
            return node, i
        
        # 키를 찾지 못했고 리프인 경우
        if node.leaf:
            return None
        
        # 적절한 자식 노드로 재귀 호출
        return self._search(node.children[i], k)
    
    # 삽입, 삭제 등 다른 메서드 구현…

이 구현은 B 트리의 기본 구조와 몇 가지 핵심 연산만을 포함하고 있다.
실제 완전한 구현에는 삽입, 삭제, 노드 분할, 병합 등의 복잡한 연산이 추가되어야 한다.

최신 연구 및 발전 동향

B 트리는 수십 년 동안 사용되어 왔지만, 여전히 다음과 같은 영역에서 연구와 발전이 계속되고 있다:

1. 병렬 및 분산 B 트리

   • 병렬 B 트리: 다중 코어/프로세서 환경에서 병렬 연산을 지원.
   • 분산 B 트리: 여러 서버에 걸쳐 분산된 B 트리 구현을 통해 확장성을 높인다.
   • Bw-트리: Microsoft에서 개발한 잠금 없는(lock-free) B 트리 변형.

2. 비휘발성 메모리(NVM) 최적화

   • NV-트리: 비휘발성 메모리에 최적화된 B 트리 변형.
   • 영속성: 전원 장애 후에도 데이터 일관성을 유지할 수 있는 기법들이 연구되고 있다.

3. 압축 기법

   • 압축 B 트리: 키와 포인터를 압축하여 메모리 효율성을 높인다.
   • 접두사 압축: 공통 접두사를 공유하여 저장 공간을 절약한다.

참고 및 출처