이진 탐색 트리로 왜 충분하지 않을까? M원 트리 그리고 B-트리의 등장 이유 (B트리, B+트리, B* 트리 연산까지)

M원 트리

데이터 구조에서 트리(Tree)는 계층적 데이터 관리와 검색을 위한 필수 구조이다.

특히, 대규모 데이터를 효율적으로 관리하기 위해 M원 트리(M-ary Tree) 가 중요한 역할을 한다.

 

그런데 왜 이진 탐색 트리(Binary Search Tree, BST) 만으로는 충분하지 않은 것일까?

BS 트리의 한계

이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 따르는 트리를 의미한다.

 

그러나 다음과 같은 한계가 존재한다.

1. 불균형 문제 (Skewed Tree Problem)

정렬된 데이터를 순차적으로 삽입하면 한쪽으로 치우친 트리가 생성된다. 삽입 순서에 따라 불균형이 발생한다.

BST (불균형 트리)  
      10  
        \  
         20  
           \  
            30  
              \  
               40

이렇게 트리가 불균형해지면 검색 시간 증가하여, 탐색의 시간 복잡도는 O(n) 으로 증가해 선형 탐색과 동일하게 된다.

2. 노드 활용 비효율성

두 번째 이유는 이진 탐색 트리 정의 그 자체에 기인한다.

 

즉, 각 노드는 최대 두 개의 자식 노드만 관리할 수 있다.

 

이러한 한계는 대규모 데이터를 처리할 때 노드 공간의 낭비가 발생할 수 있다. 왜 그럴까?

 

첫 번째로, 이진 탐색 트리는 각 노드가 두 개의 자식만 가질 수 있기 때문에 데이터가 많아질수록 트리의 깊이(Height)가 증가한다. 이 구조적 제한은 트리가 커질수록 탐색 경로가 길어지게 만들어 검색, 삽입, 삭제 작업이 느려지는 결과를 초래한다. 즉, 노드의 수가 증가할수록 트리는 수직으로 성장하게 되고, 이는 시간 복잡도 측면에서 효율성을 저하시킨다.

 

두 번째로, 대규모 데이터를 처리하는 데이터베이스와 파일 시스템에서는 데이터를 디스크 블록 단위로 관리한다.

 

하나의 디스크 블록에 더 많은 키와 자식 노드 포인터를 저장할 수 있는 구조가 필요하지만, 이진 탐색 트리는 노드당 두 개의 자식만 허용한다. 결과적으로 디스크 블록당 데이터 활용 효율이 낮아 디스크 I/O 작업이 증가하고, 시스템 성능에 부정적인 영향을 미친다.

 

마지막으로, 현대 컴퓨터 시스템은 메모리 계층 구조를 활용하여 캐시 접근 속도를 최적화한다.

 

그러나 이진 탐색 트리는 캐시에 로드되는 데이터 크기가 작아 메모리 활용도가 떨어지며, 캐시 미스(Cache Miss) 가 자주 발생할 수 있다. 이러한 메모리 관리 문제는 대규모 데이터베이스와 검색 시스템에서 성능 저하의 주요 원인이 될 수 있다.

 

예를 들어 다음 두 개의 서로 다른 트리 형태를 살펴보자.

 

첫 번째로, 이진 탐색 트리(BST) 구조이다. 숫자 키를 저장하는 간단한 예로, 각 노드는 최대 두 개의 자식을 가지며, 왼쪽 서브트리는 부모 노드보다 작은 키, 오른쪽 서브트리는 큰 키를 가진다. 예를 들어 숫자 키 (50, 30, 70, 20, 40, 60, 80)을 삽입했다고 가정하면 다음과 같은 트리 구조가 만들어진다.

        (50)
       /    \
    (30)     (70)
   /   \     /   \
(20)  (40) (60)  (80)

 

이 구조에서는 노드가 많아질수록 트리의 높이가 계속 증가하게 된다.

 

만약 수만, 수십만 개의 데이터를 저장해야 한다면 어떨까? 트리는 수직으로 매우 깊어질 것이다.

M원 트리의 도입 필요성

그렇다면 M원 트리는 어떨까?

M원 트리란?

M원 트리(M-ary Tree) 는 각 노드가 최대 M개의 자식 노드를 가질 수 있는 다원 트리(Multi-way Tree) 를 의미한다. 이 구조에서는 노드 하나가 여러 개의 키(Key) 와 자식 노드 포인터(Child Pointers) 를 동시에 저장한다. 따라서, 데이터 검색 경로가 짧아지고, 트리의 깊이가 얕아지며, 디스크 접근 횟수가 감소한다.

 

일반적으로 M원 트리는 정렬된 데이터 관리, 빠른 데이터 검색, 효율적인 데이터 삽입/삭제가 필요한 시스템에서 사용된다.

 

대표적인 예로 데이터베이스 인덱스, 파일 시스템 관리, 검색 엔진 인덱스 등이 있다.

 

 

M원 트리가 문제를 어떻게 해결할까?

M원 트리는 이진 탐색 트리(BST)의 주요 한계였던 깊이 증가, 디스크 접근 비효율성, 메모리 및 캐시 낭비 문제를 데이터 구조적 개선을 통해 해결한다. 다음 예시를 살펴보자.

 

데이터 (10, 20, 30, 40, 50, 60, 70, 80, 90)을 저장하는 M=3인 M원 트리 예시는 다음과 같다.

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

이 트리 구조에서 루트 노드는 두 개의 키(30, 60) 를 저장하고, 각 키 사이의 범위를 나타내는 자식 노드 포인터를 가진다. 이 설계는 다음과 같은 주요 성능 문제를 해결한다.

이와 같은 방식으로, 깊이 증가 문제, 디스크 접근 비효율성 문제, 메모리 및 캐시 효율성 문제를 해결하는 것을 볼 수 있다.

이제 이러한 M원 트리를 기반으로 개발된 B-트리, B+트리, B*트리의 구조적 차이와 동작 원리를 자세히 살펴보자. 🚀

B 트리 (B-Tree)

B 트리는 M원 탐색 트리에 균형 유지(밸런싱) 메커니즘을 도입한 자료구조로서, 노드 분할과 병합을 통해 항상 최소한의 균형 상태를 유지한다.

정의와 특징

1. M원 탐색 트리의 개선:
   기본적인 M원 탐색 트리는 노드 당 여러 키와 포인터를 가질 수 있지만, 균형 유지에 대한 명확한 규칙이 없다. B 트리는 이를 보완하여 각 노드에 최소·최대 키 수, 최소·최대 자식 수에 대한 제약을 명확히 부여한다. 이로써 모든 리프 노드가 동일한 높이에 위치하도록 유지하여, 데이터 접근 시 성능 안정성을 확보한다.
2. 트리 높이 최소화:
   B 트리는 각 노드가 많은 키를 저장할 수 있으므로, 주어진 데이터 양에 대해 트리의 높이가 매우 낮다. 이는 한 번의 디스크 접근을 통해 더 많은 키를 확인할 수 있음을 의미한다.
3. 보장된 균형:
   B 트리는 노드 삽입, 삭제 과정에서 '분할(split)'과 '병합(merge)'을 통해 트리 전체가 항상 균형을 유지하도록 한다. 이를 통해 평균 및 최악의 경우 모두 O(log N)의 탐색, 삽입, 삭제 성능을 보장한다.
   
   

노드 구조와 균형 유지

노드 구조 예시 (M차 B 트리 가정):

+-------------------------------------------+
|  K1  |  K2  |  ... |  Kt-1               |
|  p0  |  p1  |  ... |  pt-1    | pt       |
+-------------------------------------------+

• 키(Key): 노드 안에 정렬된 상태로 저장되며, 각 키는 특정 데이터 값 혹은 범위를 나타낸다.
• 포인터(Pointer): 키 사이사이에 위치하며 해당 범위의 하위 노드를 가리킨다.
  예를 들어, 키가 [K1, K2, ..., Kt-1]가 있다면,
  • p0는 K1보다 작은 값들을 가진 서브트리를 가리킨다.
  • p1는 K1과 K2 사이 범위의 값들을 가진 서브트리를 가리킨다.
  • ...
  • pt는 K(t-1)보다 큰 값들을 가진 서브트리를 가리킨다.

 

B트리의 성립 조건

1. 루트와 잎 노드를 제외한 제외한 모든 노드는 최소 ⌈M/2⌉개의 서브트리를 갖는다.
2. 트리의 루트는 최소한 두 개의 서브 트리를 갖는다.
3. 트리의 모든 잎 노드는 같은 레벨에 있다.

균형 상태 유지 조건

• 이때, 모든 리프 노드는 동일한 레벨(깊이)에 위치하므로, 탐색 시 특정 노드까지만 내려가면 항상 리프를 만날 수 있다.
• 삽입이나 삭제로 인해 노드가 최소 자식 수 조건을 벗어나면, 노드 분할(Split) 혹은 형제 노드와의 병합(Merge)으로 조건을 회복한다.
• 삽입 시: 노드가 가득 차면(Split) 중간 키(Median Key) 를 부모 노드로 이동시키고, 노드를 분할(Split) 한다.
• 삭제 시: 키가 부족하면 인접 노드에서 재분배(Redistribute) 하거나 병합(Merge) 을 수행해 균형을 유지한다.
• 탐색 시: 키를 기준으로 왼쪽, 중간, 오른쪽으로 탐색 방향을 결정하며, 항상 정렬된 상태를 유지한다.

삽입 알고리즘

1) 탐색을 통한 위치 결정:
새로운 키를 삽입하기 전, 해당 키가 들어갈 리프 노드를 먼저 찾는다.

 

2) 삽입 수행:
찾은 리프 노드에 키를 삽입한다. 노드에 여유 공간이 있다면 그대로 삽입하고 종료한다.

 

3) 노드 분할(Split):
만약 삽입으로 인해 노드가 수용 가능한 키 수를 초과했다면, 노드를 분할한다.

• 노드를 대략 절반으로 나누어 키 일부를 새로운 노드로 이동시킨다.
• 중간 키를 상위 부모 노드로 올려서 부모 노드에 새로운 포인터를 추가한다.
• 분할이 상위 노드도 꽉 차게 만들면 다시 상위 노드로 분할이 전파될 수 있으며, 이는 최상위 루트까지 올라갈 수 있다.
• 루트가 분할되는 경우 트리 높이가 증가하지만, 전체적으로 여전히 O(log N)의 높이를 유지하게 된다.

삽입 알고리즘 예시

예를 들어, 최대 자식 수 M=3인 B 트리를 생각해 보자. (M=3인 B 트리에서는 각 노드 최대 키 = 2개)

 

초기 상태를 다음과 같이 가정한다.

초기 상태:

  (   10 |   | 20   )
    /      |       \
   ...    ...      ...

 

여기서 (10 | 20)는 현재 하나의 노드(루트 노드)이며, 이 노드가 2개의 키(10과 20)를 갖고 있다.

 

M=3 B트리에서는 한 노드가 가질 수 있는 최대 키 수는 M-1 = 2이므로, 현재 루트 노드는 이미 최대 키를 갖고 있는 상태이다.

 

... 부분은 자식 노드를 가리키는 포인터이며, 여기서는 더 이상 하위 노드가 없다고 가정하자. 즉, 현재 루트 노드 자체가 리프이기도 하다.

 

이 상태에서 새로운 키 25를 삽입하는 과정을 살펴보자.

1단계: 탐색을 통한 위치 결정

새로운 키 25를 삽입할 위치를 찾기 위해 루트 노드(10 | 20)와 비교한다.

• 25는 20보다 크므로, 20의 오른쪽 포인터 방향(가장 오른쪽 자식)으로 내려가야 한다.
• 하지만 현재 루트 노드는 리프 노드이므로 실제 더 내려갈 자식이 없다. 따라서 삽입 위치는 루트 노드 그 자체이다.

2단계: 삽입 수행

루트 노드가 리프이므로 여기서 바로 25를 삽입하려고 시도한다.

 

현재 루트 노드 키: (10 | 20)

 

여기에 25를 삽입하면: (10 | 20 | 25) 가 된다.

 

하지만 B 트리의 규칙 상 하나의 노드가 가질 수 있는 키의 최대 개수는 2개이다.

 

지금 키가 3개가 되어버렸으므로 오버플로(Overflow) 상태가 발생한다.

3단계: 노드 분할(Split)

오버플로를 해결하기 위해 노드 분할을 수행한다.

• 현재 노드의 키: 10, 20, 25
• 키를 정렬하면 이미 정렬된 상태 (10 < 20 < 25)
• 가운데 키(중간 키)는 20으로 선정한다. 이 키는 상위 부모 노드로 올라갈 키가 된다.
• 왼쪽 노드에는 10, 오른쪽 노드에는 25를 배치한다.

분할 과정 요약:

• 원래 노드: (10 | 20 | 25)
• 중간 키: 20 -> 부모 노드로 승격
• 왼쪽 노드: (10)
• 오른쪽 노드: (25)

루트 노드 자체가 분할되면서 트리 높이가 1 증가한다.

 

이제 새로운 루트 노드는 중간 키 20이 되고, 왼쪽 자식에 10을 가진 노드, 오른쪽 자식에 25를 가진 노드가 생겨난다.

      (20)
     /    \
  (10)    (25)

 

이제 각각의 노드는 키를 1개씩 갖고 있으므로 규칙 위반이 없다.

 

B 트리는 분할 과정을 통해 오버플로 상태를 해결하고, 여전히 모든 리프가 같은 레벨에 위치하여 균형을 유지할 수 있다.

삭제 알고리즘

삭제 알고리즘에서의 핵심 포인트는 트리의 균형을 유지하면서 최소 키 수(minimum degree)를 만족하도록 관리하는 것이다.

 

삭제 과정에서 발생할 수 있는 키 부족 문제는 재분배(Redistribution) 또는 노드 병합(Merge) 을 통해 해결한다.

 

1) 탐색을 통한 삭제 위치 결정:

 

삭제하려는 키가 있는 리프 노드를 찾는다. 삽입과 마찬가지로 O(log N)에 가능하다.

 

2) 키 삭제:

 

해당 리프에서 키를 제거한다. 제거 후에도 노드가 최소 키 수를 만족한다면 문제없이 종료할 수 있다.

 

3) 노드 병합(Merge) 또는 재분배(Redistribution):

삭제로 인해 노드가 최소 키 수를 만족하지 못한다면, 형제 노드에서 키를 빌려오거나(재분배) 형제 노드와 병합하여 부족한 키 수를 보완한다.

• 형제 노드에 여유가 있는 경우: 형제 노드로부터 키를 하나 가져와(재분배) 균형을 맞춘다.
• 형제 노드에도 여유가 없는 경우: 형제 노드와 합쳐서(병합) 하나의 노드로 만든다. 이 때 상위 부모 노드에서 키를 내려받아 균형을 유지할 수 있다. 필요하다면 상위 노드에도 병합이 전파될 수 있다.

삭제 알고리즘 예시

앞서 삽입 과정에서 사용한 것과 유사한 B 트리(M=3)를 가정하여, 아래와 같이 균형을 잘 유지하고 있는 B 트리를 예시로 들어보자.

 

초기 상태:

        (20)
       /    \
    (10)    (25 | 30)

 

여기서 (20)이 루트 노드이고, 왼쪽 자식 노드 (10)은 1개의 키를, 오른쪽 자식 노드 (25 | 30)는 2개의 키를 가지고 있다.

 

모든 리프 노드는 동일한 레벨이며, 각 노드가 최소 키 수를 만족한다.

 

이번에는 키 30을 삭제해보자.

1단계: 탐색을 통한 삭제 위치 결정

삭제하려는 키: 30

• 루트 노드 (20)를 확인한다. 삭제할 키 30은 20보다 크므로 20의 오른쪽 자식 방향으로 내려간다.
• 오른쪽 노드 (25 | 30)를 확인한다. 여기서 바로 30을 찾을 수 있다.
• (25 | 30)는 리프 노드이므로 더 이상 내려갈 필요가 없다. 삭제할 키가 있는 리프 노드를 찾았다.

2단계: 키 삭제

리프 노드 (25 | 30)에서 키 30을 삭제한다. 삭제 후 상태는 (25)만 남는다.

 

삭제 결과, 

        (20)
       /    \
    (10)    (25)

 

이제 오른쪽 노드에는 키가 하나 (25)만 남았다. 최소 키 수 조건을 다시 확인해야 한다.

• M=3인 B 트리의 경우, 각 노드는 최소 ⌈M/2⌉ 개 이상의 자식을 가져야 하며, 각 내부 노드는 최소 ⌈M/2⌉-1 개 이상의 키를, 리프 노드 역시 최소 1개 이상의 키를 가져야 한다.
• 여기서 최소 키 수는 1개 이상이므로, (25) 노드는 이미 1개의 키를 가지고 있고 문제 없다.
  
  

 

만약 삭제 대상이 최소 키 수를 깨뜨렸다면 어떨까?

추가로 생각해볼 것: 노드 부족 상황에서의 처리

다음과 같은 B 트리 구조를 고려해보자. (여전히 M=3)

 

삭제 전 상태:

         (20)
       /      \
   (5 | 10)   (25 | 30)

 

여기서 5와 10을 가진 왼쪽 노드, 25와 30을 가진 오른쪽 노드가 있다.

 

이 상태에서 키 10을 삭제한다고 가정해보자.

• 10은 왼쪽 노드 (5 | 10)에 있다.
• 10 삭제 후 왼쪽 노드는 (5)만 남다.

삭제 결과:

        (20)
       /    \
    (5)     (25 | 30)

 

현재 왼쪽 노드 (5)는 키가 1개이므로 여전히 최소 키 수(1)를 만족하므로 문제없다.

 

그러나 만약 더 극단적인 예를 들어, 왼쪽 노드에 (5 | 10) 대신 (10)만 있었다고 해보자.

삭제 전 극단적 예:

    (20)
   /    \
(10)    (25 | 30)

여기서 10을 삭제해보자.

1. 10 삭제 후 왼쪽 노드: 빈 노드 ()가 되어버린다. 즉, 최소 키 수 1개를 만족하지 못하는 상태가 된다.
2. 이 상황을 해결하기 위해 오른쪽 노드 (25 | 30)에서 재분배하거나 병합을 고려할 수 있다.
   오른쪽 노드 (25 | 30)는 2개의 키를 가지고 있다. 하나를 왼쪽으로 재분배할 수 있다.
   예를 들어 25를 부모(20)와 교환하여 왼쪽 노드로 가져올 수 있다.

재분배 과정:

• 부모 노드 (20)에서 20을 왼쪽 노드로 내려보내고, 오른쪽 노드 (25 | 30)에서 25를 부모로 올린다.
• 이 과정은 다음과 같이 이루어질 수 있다.
  • 오른쪽 노드 (25 | 30) 중 25를 부모에게 올리고, 부모의 20을 왼쪽 노드로 내린다.
  • 결과적으로 트리는 다음과 같이 변한다.

        (25)
       /    \
    (20)    (30)

 

여기서 (20)는 왼쪽 노드, (30)는 오른쪽 노드, 부모는 (25)를 가지게 된다.

 

원래 왼쪽 노드는 (10)이 삭제되어 키가 없었지만, 재분배를 통해 (20)를 얻었고, 이제 최소 키 수를 만족할 수 있다.

 

만약 재분배할 수 있는 형제 노드가 없고, 형제 노드도 여유가 없는 경우에는 두 노드를 병합(Merge)한다.

병합은 두 자식 노드와 그 사이의 부모 노드 키 하나를 합쳐 하나의 노드로 만드는 과정으로, 병합이 일어나면 트리 높이가 낮아질 수도 있다.

예를 들어 다음과 같은 상태를 생각해보자.

 

삭제 전 상태:

        (20)
       /    \
    (10)    (30)

여기서 10을 삭제한다고 가정해보자.

 

1) 삭제 후 상태:

• 왼쪽 노드 (10)에서 키 10을 삭제하면 왼쪽 노드는 비어 있게 된다.

     (20)
    /    \
  ()     (30)

이 상태에서 왼쪽 노드는 최소 키 수(1)를 만족하지 못하므로 병합이 필요하다.

 

2) 병합 과정:

• 왼쪽 노드 ()와 부모 노드의 키 (20) 그리고 오른쪽 형제 노드 (30)을 병합하여 하나의 노드로 만든다.
• 병합된 노드는 (20 | 30)이 되며, 부모 노드는 제거된다.

 

병합 후 트리 상태:트리의 높이가 1 감소했으며, 병합을 통해 모든 노드는 여전히 최소 키 수를 만족하게 된다.

 

(20 | 30)

병합은 다음 조건에서 수행된다.

• 삭제로 인해 노드가 최소 키 수를 만족하지 못함.
• 형제 노드도 재분배할 키를 가지고 있지 않음.

병합의 결과로,

1. 부모 노드의 키가 하나 제거된다.
2. 두 자식 노드와 부모 노드의 키 하나가 합쳐져 새로운 노드가 된다.
3. 병합된 노드는 루트가 될 수도 있고, 부모와 병합 과정을 반복적으로 수행해야 할 수도 있다.

병합 과정은 B 트리의 균형을 유지하며, 트리의 높이를 감소시킬 수 있는 유일한 과정이다.

B* 트리 (B*Tree)

B*트리는 B-트리를 개선한 또 다른 변형 구조로, 노드 분할 시 보다 적극적인 재분배를 통해 노드 이용률을 높이고, 전체 트리의 균형을 더욱 촘촘히 유지하는 자료구조이다.

 

B-트리가 삽입/삭제 시 발생하는 분할 과정을 통해 높이를 최소화하는 기본 전략을 따른다면, B*트리는 한 걸음 더 나아가 노드 분할 전 이웃(형제) 노드와 키를 재분배하여 가능한 한 노드 분할을 늦추고 각 노드의 키 밀도를 높이는 전략을 취한다.

정의와 특징

1. B-트리의 개선된 형태:
   B*트리는 기본적인 구조나 균형 유지 전략은 B-트리와 유사하지만, 노드가 가득 차기 전에도 인접 노드와의 재분배(키 이동)를 통해 불필요한 분할을 줄이고, 노드 밀도를 높인다.
   결과적으로 일반적인 B-트리에 비해 각 노드가 평균적으로 더 많은 키를 가지게 되므로 트리의 높이가 더 낮아지고 탐색 성능이 향상된다.
2. 더 높은 최소 노드 활용도:
   B-트리는 노드가 최소 반 정도는 채워져 있어야 하는 반면, B* 트리는 최소 2/3 이상(약 66%) 노드가 채워지도록 보장한다.
   이렇게 노드 밀도를 높이면, 동일한 양의 데이터에 대해 B* 트리가 더 낮은 높이를 유지할 수 있어 디스크 접근 횟수가 감소한다.
3. 재분배를 통한 균형 유지 강화:
   B*트리는 삽입 시 단순히 노드가 가득 찼을 때만 분할하지 않고, 먼저 형제 노드와 키를 재분배해 분할을 회피하려고 한다.
   이를 통해 불필요한 루트 분할이나 높이 증가를 줄여 안정적인 성능을 보장한다.

노드 구조와 균형 유지

B*트리의 노드 구조는 B-트리와 유사하게 키와 포인터를 가지는 내부 노드, 그리고 데이터를 담는 리프 노드(또는 B-트리처럼 리프와 내부에 모두 데이터를 둘 수도 있지만, 일반적으로 B-트리 변형 방식과 유사)로 구성된다.

차이점:

• B*트리는 최소 충전율(minimum filling factor)이 더 높다. 즉, 노드에 삽입할 수 있는 키 수의 하한을 더 높은 비율로 강제한다. 이를 통해 노드들이 더 '꽉 찬' 상태를 유지하도록 하여 디스크 접근 효율을 높인다.
• 삽입이나 삭제 시, 단순히 노드 분할/병합 전에 이웃 노드들과 키를 재분배하려는 시도를 통해 최대한 균형을 유지하고, 트리 구조의 변동을 최소화한다.

B* 트리 구조 

다음과 같은B* 트리(M=3) 구조를 살펴보자.

 

각 노드는 최대 3개의 키와 4개의 자식 포인터를 가질 수 있으며, 노드가 가득 차더라도 인접 노드 간 재분배가 우선적으로 시도된다.

 

분할은 재분배가 불가능한 경우에만 발생한다.

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

삽입 알고리즘

B*트리에서의 삽입 알고리즘은 B-트리와 유사하나, 노드 분할 전 재분배 과정을 강화한 것이 특징이다.

1. 탐색을 통한 위치 결정:
   삽입할 키를 넣을 리프 노드를 찾는다.
2. 노드에 여유가 있을 경우 직접 삽입:
   해당 리프 노드에 여유 공간이 있다면 키를 그대로 삽입하고 종료한다.
3. 노드 가득 참 -> 이웃 노드 재분배 시도:
   노드가 가득 차서 키 삽입이 불가능하다면, 먼저 형제 노드(왼쪽 또는 오른쪽 형제)와 재분배를 시도한다.
   형제 노드에 여유가 있다면 일부 키를 옮겨와 현재 노드 공간을 확보한 뒤 키를 삽입한다.
4. 재분배 불가능 시 노드 분할(Split):
   형제 노드와의 재분배로도 키 삽입이 불가능한 경우에 한해 노드를 분할한다.
   1. 분할 시 중간 키를 부모 노드로 승격시키며, 필요하다면 부모 노드에 대해서도 동일한 재분배 또는 분할 과정을 수행한다.
   2. 이러한 방식을 통해 최대한 분할을 늦추고, 분할 시에도 부모 노드를 포함한 상위 레벨의 구조적 변동을 최소화한다.

정리하자면 다음과 같다.

• B-트리 삽입 시 오버플로 → 바로 노드 분할
• B*트리 삽입 시 오버플로 → 형제 노드에 여유 키 존재? 재분배 시도 → 재분배 실패 시 분할

삽입 알고리즘 예시

다음과 같은 초기 상태의 B* 트리에 4를 삽입하는 과정을 살펴보자.

      (      | 6 |  | ...)
          /         \
( 1 | 2 | 3 | 5 | )    ( | 7 | 8 | ...)

 

1) 삽입 위치 탐색:
삽입할 키 4는 6보다 작으므로 왼쪽 자식 노드 ( 1 | 2 | 3 | 5 )로 이동하여 탐색한다.

 

2) 리프 노드 여유 공간 확인:
왼쪽 리프 노드 ( 1 | 2 | 3 | 5 )는 이미 가득 차 있어 키를 직접 삽입할 수 없다.

 

3) 형제 노드 재분배 시도:

• 왼쪽 노드 ( 1 | 2 | 3 | 5 )의 형제 노드 ( 7 | 8 )를 확인한다.
• 형제 노드 ( 7 | 8 )에 여유 공간이 있으므로 일부 키를 형제 노드로 이동하여 재분배를 수행한다.
• 중간 키 6을 중심으로, 부모 노드에서 조정하여 다음과 같이 재배치한다:
  • 왼쪽 노드: ( 1 | 2 | 3 )
  • 부모 노드: ( 4 ) (4는 새롭게 삽입된 키)
  • 오른쪽 노드: ( 5 | 6 | 7 | 8 )

재분배 이후 상태:

      ( 4 )
     /     \
( 1 | 2 | 3 ) ( 5 | 6 | 7 | 8 )

이 과정을 통해 노드 분할 없이 재분배를 통해 키 삽입하는 것을 볼 수 있다.

B 트리에서의 삽입 과정

B 트리는 재분배를 고려하지 않으므로, 동일한 상황에서 노드 분할이 바로 발생한다.

 

1) 삽입 위치 탐색 및 오버플로:
키 4를 삽입하려면 ( 1 | 2 | 3 | 5 ) 리프 노드가 가득 차므로 분할이 필요하다.

 

2) 노드 분할 수행:

• 왼쪽 노드 ( 1 | 2 | 3 | 5 )를 중간 키 3을 기준으로 분할한다.
  • 왼쪽 노드: ( 1 | 2 )
  • 부모로 승격: 3
  • 오른쪽 노드: ( 4 | 5 ) (4는 새롭게 삽입된 키)
• 분할된 오른쪽 노드 ( 4 | 5 )는 기존 부모 노드와 다시 연결된다.

분할 이후 상태:

         ( 3 | 6 )
        /    |    \
( 1 | 2 ) ( 4 | 5 ) ( 7 | 8 )

B* 트리와 B 트리의 차이점 정리

• B* 트리:
  형제 노드 간 재분배를 통해 노드 분할을 지연시킴으로써 트리의 높이 증가를 방지한다.
  결과적으로 더 많은 키를 하나의 레벨에 유지할 수 있어 탐색 비용이 줄어든다.
• B 트리:
  오버플로 시 즉시 노드 분할을 수행하므로, 트리의 높이가 더 빨리 증가할 가능성이 있다.
  결과적으로 B 트리의 분할 과정은 간단하지만, 노드 효율성은 B* 트리에 비해 낮다.

삭제 알고리즘

B*트리의 삭제 알고리즘 역시 B-트리와 비슷하나, 최소 키 수를 유지하기 위해 병합이나 재분배 전략을 적극 활용한다.

1. 탐색을 통한 삭제 위치 결정:
   삭제할 키가 있는 리프 노드를 찾는다.
2. 키 삭제 후 최소 키 수 유지 확인:
   키를 삭제한 후 노드가 최소 키 충족 조건(2/3 이상 유지)을 만족하는지 확인한다.
3. 재분배(Redistribution) 우선 시도:
   최소 조건을 만족하지 못하면 먼저 형제 노드로부터 키를 빌려올 수 있는지 시도한다.
   형제 노드에 여유 키가 있다면 일부를 가져와 현재 노드를 보충한다.
4. 재분배 불가능 시 노드 병합(Merge):
   형제 노드에도 여유가 없는 경우, 형제 노드와 병합하여 하나의 노드로 만든다.
   이때 상위 노드의 키를 내려받아 구조를 정리하며, 필요하다면 상위 노드에도 같은 과정을 적용한다.

삭제 알고리즘 예시

M=3인 B*트리를 기준으로 삭제 과정을 예시와 함께 살펴보자.

          (20 |40)
         /    |    \
    (10 |30)  (35)  (45)

• 루트 노드: 20, 40
• 왼쪽 자식 노드: 10, 30
• 중앙 자식 노드: 35
• 오른쪽 자식 노드: 45

모든 노드는 최소 키 수(1개)를 만족하고 있으며, 트리는 균형을 이루고 있다.

삭제할 키: 30

이제 키 30을 B*트리에서 삭제하는 과정을 단계별로 살펴보자

 

1) 삭제 위치 탐색:

 

삭제할 키 30은 루트 키 20보다 크고 40보다 작으므로, 왼쪽 자식 노드 (10 | 30)에서 삭제 위치를 찾는다.

 

2) 키 삭제 및 최소 조건 확인:

키 30을 삭제한 후 왼쪽 자식 노드는 (10)만 남는다.

그러나, B* 트리에서는 노드의 최소 키 수가 전체 용량의 2/3 이상이어야 한다.

• 현재 왼쪽 노드는 키 하나만 남아 최소 조건을 충족하지 못한다.

 

3) 형제 노드로부터 재분배 시도:

• 왼쪽 노드 (10)의 형제 노드 (35)를 확인한다.
• 중앙 노드 (35)에서 부모 노드 20을 내려받고, 자신은 35를 부모로 승격시킨다.
• 결과적으로 키를 재분배하여 모든 노드가 최소 조건을 만족한다.

재분배 이후 상태:

          (35 | 40)
         /    |    \
    (10 | 20)  (35)  (45)

B 트리에서의 삭제 과정

동일한 상황에서 B 트리의 삭제 과정을 살펴보자.

 

1) 삭제 위치 탐색 및 최소 조건 확인:

키 30을 삭제한 후, 왼쪽 자식 노드는 (10)만 남아 최소 키 조건을 충족하지 못한다.

 

2) 병합 수행:

• 부모 노드 20과 현재 노드 (10)을 병합한다.
• 병합 후 왼쪽 노드는 (10 | 20)이 되고, 부모 노드의 구조가 변경된다.
• 결과적으로 병합된 노드 수가 늘어나고, 트리 높이에는 변화가 없다.

병합 이후 상태:

          (40)
         /    \
    (10 | 20)  (45)

B* 트리와 B 트리의 차이점

• B* 트리:
  병합보다 재분배를 우선적으로 수행하여 구조적 변동을 최소화한다.
  재분배를 통해 최소 조건을 충족하더라도 병합하지 않으므로, 노드 밀집도가 높아지고 트리의 균형이 유지된다.
• B 트리:
  재분배를 고려하지 않고 병합을 더 자주 수행한다. 병합은 간단한 연산이지만 노드 밀도가 낮아지고, 특정 상황에서 트리 높이 증가를 초래할 가능성이 있다.
  
  
  

B+트리 (B+Tree)

B+트리는 B-트리를 개선한 자료구조로, 특히 데이터베이스 인덱스에서 널리 사용된다.

 

기본적인 균형 유지 메커니즘은 B-트리와 유사하지만, 모든 실제 데이터(레코드)가 리프 노드에 저장되고 내부 노드는 탐색을 위한 인덱스 역할만 한다.

 

또한 리프 노드들이 연결 리스트 형태로 연결되어 있어 범위 조회(Range Query)에 대한 성능이 뛰어나다.

 

즉, 왜 B+ 트리가 필요한가?

 

B+ 트리는 리프 노드를 연결 리스트로 연결하여 빠른 순차 접근(Sequential Access)을 지원하고, 범위 기반 검색(Range Queries)으로 효율적인 범위 검색에 매우 효율적이기 때문이다.

 

따라서 모든 데이터가 리프 노드에 위치하므로 연속된 데이터 범위를 빠르게 검색할 수 있다.

 

정의와 특징

1. 리프 노드에만 실제 데이터 저장:
   B+트리에서는 모든 레코드(실제 값)가 리프 노드에 저장되며, 내부 노드는 탐색을 위한 키와 포인터만을 가진다.
   이는 내부 노드가 최대한 많은 키를 가질 수 있어 트리의 높이를 더 낮추고, 탐색 성능을 개선하는 데 기여한다.
2. 연결된 리프 노드:
   리프 노드들이 연결 리스트로 서로 연결되어 있어, 특정 키 범위 내 데이터를 연속적으로 탐색할 때 매우 빠르게 접근할 수 있다.
   예를 들어, 10부터 50까지 키를 가진 데이터를 탐색할 때, 10이 위치한 리프 노드를 찾은 뒤 오른쪽으로 연결된 노드를 순회하기만 하면 50까지의 데이터를 효율적으로 조회할 수 있다.
3. B-트리와 유사한 삽입/삭제 규칙:
   B+트리 역시 B-트리처럼 삽입과 삭제 시 노드 분할(Split) 및 병합(Merge), 재분배(Redistribution) 과정을 통해 항상 균형을 유지한다.
   모든 리프 노드가 동일한 깊이에 유지되는 점도 B-트리와 동일한다.
4. 다양한 시스템에서 인덱스로 활용:
   대규모 데이터베이스, 파일 시스템의 디렉토리 구조, Key-Value 스토어 등에서 인덱스 구조로 B+트리를 많이 활용한다.
   범위 조회 성능 향상을 위해 B+트리를 택하는 경우가 많다.
   
   
   

노드 구조와 균형 유지

B+트리의 내부 노드와 리프 노드는 다음과 같이 구성된다.

• 내부 노드(Internal Node):
  • 키와 포인터로만 구성되며, 각 키는 자식 노드 범위를 정의한다.
  • 실제 데이터는 포함하지 않는다.
  • B-트리와 마찬가지로 노드 내 키 수와 포인터 수에 대해 최소/최대 개수 규칙을 가지며, 노드가 최소 개수 이하가 되지 않도록 삽입/삭제 시 균형을 맞춘다.
• 리프 노드(Leaf Node):
  • 모든 실제 데이터를 저장한다.
  • 리프 노드끼리는 Linked List로 연결되어 있어, 인접한 리프 노드로 바로 이동하여 데이터 범위 검색이 빠르다.
  • 각 리프 노드는 자신이 가진 키를 정렬된 상태로 저장하며, 그 키들에 대응하는 데이터(레코드)에 직접 접근 가능하다.

균형 유지 조건:

• 모든 리프 노드는 동일한 레벨에 위치한다.
• 노드 삽입 시 가득 찬 노드가 있으면 분할(Split)을 통해 상위 노드로 키를 승격시키고, 노드 삭제 시 부족한 키 수를 가지게 되면 병합(Merge) 또는 재분배를 통해 균형을 회복한다.

삽입 알고리즘

B+트리의 삽입 과정은 B-트리의 삽입과 유사하나, 데이터를 항상 리프 노드에 삽입한다는 점에서 차이가 있다.

 

 

1) 탐색을 통한 삽입 위치 결정:

삽입할 키가 들어갈 리프 노드를 찾는다. 내부 노드는 경로 안내 역할만 하며, 결국 리프 노드까지 내려가서 삽입할 위치를 확정한다.

 

2) 리프 노드 삽입:

 

찾은 리프 노드에 새 키와 데이터를 삽입한다. 노드에 여유 공간이 있다면 그대로 삽입하고 종료한다.

 

3) 노드 분할(Split) 및 키 승격:

 

만약 리프 노드가 가득 차 있다면 리프 노드를 분할한다.

• 리프 노드를 두 개로 나누고, 중간 키를 상위 내부 노드로 올려 승격시킨다.
• 내부 노드 역시 오버플로가 발생하면 같은 과정이 상위 노드로 전파될 수 있으며, 필요하다면 루트 노드도 분할되어 트리 높이가 증가할 수 있다.

삽입 알고리즘 예시

M=3인 B+트리를 기준으로 삽입 과정을 살펴보자.

초기 상태

M=3인 B+트리는 각 노드가 최대 2개의 키를 가질 수 있으며, 최소 1개의 키를 유지해야 한다. 또한, 리프 노드들이 서로 연결 리스트로 연결되어 있다.

 

다음과 같은 초기 B+트리를 가정해보자.

       [20]
       /  \
    [10]  [30 |40]

• 루트 노드: 키 20
• 왼쪽 리프 노드: 키 10
• 오른쪽 리프 노드: 키 30, 40
• 리프 노드 연결: [10] <-> [30 |40]

모든 리프 노드는 동일한 깊이에 있으며, 각 노드는 최소 키 수를 만족하고 있다.

삽입할 키: 25

이제 키 25를 B+트리에 삽입하는 과정을 단계별로 살펴보면,

 

1) 삽입 위치 탐색:

 

삽입할 키 25는 루트 노드의 키 20보다 크므로 오른쪽 자식 노드 [30 | 40]로 내려간다.

 

이때 B+트리에서는 항상 리프 노드에 데이터를 삽입하므로, 최종적으로 오른쪽 리프 노드 [30 | 40]에 삽입할 위치를 결정한다.

 

2) 리프 노드 여유 공간 확인:

 

삽입 대상인 리프 노드 [30 | 40]은 이미 최대 키 수(2개)를 가지고 있어 여유 공간이 없다.

 

따라서 리프 노드를 분할해야 한다.

 

 

3) 리프 노드 분할(Split):

• 리프 노드 [30 | 40]을 중간 키 30을 기준으로 분할한다.
  • 왼쪽 리프 노드: [25 | 30] (25은 새로 삽입된 키)
  • 오른쪽 리프 노드: [40]
• 리프 노드 간 연결도 업데이트한다.
  새로운 노드 [40]은 기존 연결 리스트에 포함되어야 하므로, 분할 이후 리프 노드 연결은 [10] <-> [25 | 30] <-> [40]가 된다.
• 중간 키 승격:
  • 분할 과정에서 발생한 중간 키 30을 부모 노드로 승격시킨다.
  • 부모 노드 [20]에 승격된 키 30을 삽입하여 구조를 갱신한다.

분할 이후 트리 상태:

       [20 | 30]
       /    |    \
    [10] [25 |30] [40]

 

삭제 알고리즘

B+트리의 삭제 역시 B-트리와 유사하다. 키 삭제는 항상 리프 노드에서 이루어지며, 삭제 후 최소 키 수를 만족하지 못하면 재분배나 병합을 통해 균형을 맞춘다.

1. 삭제할 키 위치 탐색:
   내부 노드를 거쳐 리프 노드까지 내려가 삭제할 키를 찾는다.
2. 키 삭제:
   리프 노드에서 키를 제거한다. 제거 후에도 최소 키 수를 만족한다면 별다른 추가 조치 없이 종료한다.
3. 노드 병합(Merge) 또는 재분배(Redistribution):
   최소 키 수에 미달한다면, 형제 리프 노드로부터 키를 빌리거나(재분배) 형제 노드와 병합하여 하나의 노드로 만든다. 이 과정에서 부모(내부) 노드의 키를 조정하게 되며, 필요 시 상위 노드까지 변경이 전파될 수 있다.

삭제 알고리즘 예시

       [30]
       /  \
 [10 |20] [35 |40]

• 루트 노드: 키 30
• 왼쪽 리프 노드: 키 10, 20
• 오른쪽 리프 노드: 키 35, 40
• 리프 노드 연결: [10 |20] <-> [35 |40]

모든 리프 노드는 동일한 깊이에 있으며, 각 노드는 최소 키 수를 만족하고 있다.

삭제할 키: 20

이제 키 20을 B+트리에서 삭제하는 과정을 단계별로 살펴보자.

1단계: 탐색을 통한 삭제 위치 결정

삭제할 키 20의 위치를 찾기 위해 트리를 탐색한다.

• 루트 노드 [30]와 비교: 20은 30보다 작으므로, 왼쪽 리프 노드 [10 |20]로 이동한다.
• 왼쪽 리프 노드 [10 |20]에서 키 20을 찾는다.

2단계: 키 삭제

왼쪽 리프 노드 [10 |20]에서 키 20을 삭제한다.

• 삭제 후 상태: [10]

삭제 결과 트리 구조:

       [30]
       /  \
    [10]  [35 |40]

• 루트 노드: 30
• 왼쪽 리프 노드: 10
• 오른쪽 리프 노드: 35, 40
• 리프 노드 연결: [10] <-> [35 |40]

3단계: 최소 키 수 유지 확인 및 재분배

삭제 후 각 노드가 최소 키 수를 만족하는지 확인한다.

• 왼쪽 리프 노드 [10]는 최소 키 수인 1을 유지하고 있으므로, 추가 조치가 필요하지 않다.
• 오른쪽 리프 노드 [35 |40]는 여전히 2개의 키를 가지고 있으므로 문제가 없다.

결과: 삭제 과정에서 노드의 최소 키 수가 유지되었으므로, 추가적인 재분배나 병합이 필요하지 않다.

추가 예시: 노드 병합이 필요한 상황

이번에는 키 10을 삭제하여 노드 병합이 필요한 상황을 살펴보자.

초기 상태

삭제를 진행하기 전에 트리 구조는 다음과 같다.

       [30]
       /  \
    [10]  [35 |40]

• 루트 노드: 30
• 왼쪽 리프 노드: 10
• 오른쪽 리프 노드: 35, 40
• 리프 노드 연결: [10] <-> [35 |40]

삭제할 키: 10

키 10을 삭제하는 과정을 단계별로 살펴보자.

1단계: 탐색을 통한 삭제 위치 결정

삭제할 키 10의 위치를 찾기 위해 트리를 탐색한다.

• 루트 노드 [30]와 비교: 10은 30보다 작으므로, 왼쪽 리프 노드 [10]로 이동한다.
• 왼쪽 리프 노드 [10]에서 키 10을 찾는다.

2단계: 키 삭제

왼쪽 리프 노드 [10]에서 키 10을 삭제한다.

• 삭제 후 상태: [] (빈 노드)

삭제 결과 트리 구조:

       [30]
       /  \
      []  [35 |40]

• 루트 노드: 30
• 왼쪽 리프 노드: 빈 노드 []
• 오른쪽 리프 노드: 35, 40
• 리프 노드 연결: [] <-> [35 |40]

3단계: 최소 키 수 유지 확인 및 병합

삭제 후 각 노드가 최소 키 수를 만족하는지 확인한다.

• 왼쪽 리프 노드 []는 키가 없어 최소 키 수 1을 충족하지 못한다.
• 따라서, 형제 노드인 오른쪽 리프 노드 [35 |40]와의 재분배 또는 병합을 시도한다.

재분배 시도:

• 형제 노드 확인: 오른쪽 리프 노드 [35 |40]는 2개의 키를 가지고 있어 재분배가 가능하다.
• 키 이동: 오른쪽 리프 노드에서 하나의 키를 빌려와 왼쪽 리프 노드로 이동시킨다.
  • 빌려올 키: 35
  • 이동 후 상태:
    • 왼쪽 리프 노드: [35]
    • 오른쪽 리프 노드: [40]
• 부모 노드 업데이트:
  • 부모 노드 [30]의 키 30을 재조정하여 새로운 최소 키를 반영한다.
  • 부모 노드의 키: [40] (최소 키가 35로 변경됨)

변경된 트리 구조:

       [35]
       /  \
    [30]  [40]

• 루트 노드: 35
• 왼쪽 리프 노드: 30
• 오른쪽 리프 노드: 40
• 리프 노드 연결: [30] <-> [40]

결과: 삭제 과정에서 재분배를 통해 노드 병합 없이 균형을 유지할 수 있었다.

---

비교 요약: B-트리 vs B 트리 vs B+ 트리*

비교 항목	B-트리 (B-Tree)	B* 트리 (B*Tree)	B+트리 (B+Tree)
데이터 저장 위치	내부 노드와 리프 노드 모두에 데이터 저장	내부 노드와 리프 노드 모두에 데이터 저장	모든 실제 데이터는 리프 노드에만 저장
노드 구조	키와 포인터를 포함한 내부 노드, 키와 데이터를 포함한 리프 노드	B-트리와 유사하나, 노드 분할 전에 형제 노드와의 재분배를 우선적으로 시도	내부 노드는 키와 포인터만 포함, 리프 노드는 키와 데이터 포함
리프 노드 연결	연결 리스트로 연결되지 않음	연결 리스트로 연결되지 않음	리프 노드들이 연결 리스트로 연결되어 있어 범위 조회에 효율적
최소 키 수	각 노드는 최소 ⌈M/2⌉ - 1개의 키를 가져야 함	각 노드는 최소 2/3 이상의 키를 가져야 함	각 리프 노드는 최소 ⌈M/2⌉ - 1개의 키를 가져야 함
노드 분할 및 재분배	노드가 가득 찼을 때 바로 분할	노드 분할 전에 형제 노드와의 재분배를 시도하여 분할을 늦춤	리프 노드가 가득 찼을 때 분할, 내부 노드도 필요 시 분할
트리 높이	상대적으로 높을 수 있음	B-트리에 비해 더 낮을 수 있음	트리 높이가 낮아 검색 성능이 우수
범위 조회 성능	범위 조회 시 효율성이 낮을 수 있음	범위 조회 시 효율성이 낮을 수 있음	리프 노드들이 연결 리스트로 연결되어 있어 매우 효율적
검색 성능	O(log N)	O(log N)	O(log N)
삽입 및 삭제 성능	균형을 유지하기 위해 분할 및 병합 필요	B-트리보다 더 효율적인 분할 및 병합 메커니즘	균형을 유지하기 위해 리프 노드에서만 분할 및 병합 수행
사용 사례	데이터베이스 인덱스, 파일 시스템의 디렉토리 구조	고밀도 인덱싱이 필요한 대규모 데이터베이스	데이터베이스 인덱스, 파일 시스템, Key-Value 스토어
노드 밀도	상대적으로 낮을 수 있음	높은 노드 밀도를 유지하여 더 적은 노드로 더 많은 데이터를 저장	리프 노드에 모든 데이터를 저장하여 높은 노드 밀도 유지
장점	구현이 비교적 간단하고, 다양한 응용에 사용 가능	B-트리에 비해 더 낮은 트리 높이와 높은 노드 밀도로 성능 향상	빠른 범위 조회와 높은 검색 성능, 모든 데이터가 리프에 저장되어 일관된 검색 속도 보장
단점	트리 높이가 커질 경우 디스크 접근 횟수가 증가	구현이 B-트리보다 복잡하며, 재분배 과정이 추가로 필요	내부 노드에 데이터가 없기 때문에 특정 상황에서 데이터 접근 시 더 많은 단계를 거칠 수 있음

• 데이터 저장 위치: 각 트리에서 실제 데이터가 저장되는 위치. B+트리는 모든 데이터를 리프 노드에만 저장하여 내부 노드는 인덱스 역할만 한다.
• 노드 구조: B* 트리는 B-트리의 구조를 기반으로 더 높은 노드 밀도를 유지하기 위한 추가적인 재분배 메커니즘을 도입한다.
• 리프 노드 연결: B+트리는 리프 노드들이 연결 리스트로 연결되어 있어 범위 조회가 매우 효율적이다.
• 최소 키 수: B* 트리는 노드의 밀도를 더욱 높이기 위해 B-트리보다 더 높은 최소 키 수를 요구한다.
• 노드 분할 및 재분배: B*트리는 노드 분할 전에 형제 노드와의 재분배를 시도하여 분할을 늦추고 노드 밀도를 높인다.
• 트리 높이: 트리의 높이가 낮을수록 검색 성능이 향상되는데, B* 트리는 높은 노드 밀도를 유지하여 B-트리보다 낮은 높이를 가질 수 있다.
• 범위 조회 성능: B+트리는 리프 노드 간의 연결 리스트 덕분에 범위 조회가 매우 효율적이다.
• 검색 성능: 모든 트리는 균형 잡힌 구조로 O(log N).
• 삽입 및 삭제 성능: 각 트리는 균형을 유지하기 위해 삽입과 삭제 시 분할 및 병합 과정을 거친다. B* 트리는 재분배 과정을 강화하여 보다 효율적인 균형 유지를 도모한다.

B+ 트리와 B 트리, B* 트리의 삽입 차이점

• B+ 트리:
  데이터는 항상 리프 노드에 저장되며, 리프 노드가 연결 리스트로 연결되어 있어 순차 검색이 빠르다.
  삽입 시 리프 노드가 가득 차면 분할하고, 중간 키를 내부 노드로 승격하여 검색 경로를 확장한다.
• B 트리:
  데이터는 리프 노드뿐만 아니라 내부 노드에도 저장될 수 있다.
  삽입 시 오버플로 발생 시 바로 분할하며, 데이터의 검색은 리프까지 내려갈 필요가 없다.
• B* 트리:
  삽입 시 재분배를 우선 시도하여 분할을 최대한 지연한다.
  형제 노드로부터 키를 재분배하거나 여유 공간을 활용해, 분할로 인한 구조적 변동을 최소화한다.
  
  

---

실 사용 사례

B-트리, B+트리, B*트리는 다양한 시스템과 애플리케이션에서 효율적인 데이터 저장과 검색을 위해 널리 사용된다.

 

특히, 데이터베이스 관리 시스템(DBMS)과 운영 체제의 파일 시스템에서 그 활용도가 매우 높다. 먼저 주요 DBMS에서 B 트리 계열이 인덱싱으로 사용되는 원리를 살펴보자.

주요 DBMS 인덱싱 원리

B+트리 기반 인덱싱

B+트리는 대부분의 상용 DBMS에서 기본 인덱스 구조로 채택하고 있다. 그 이유는 B+트리가 제공하는 뛰어난 검색 성능과 범위 조회 효율성 때문이다.

대표적인 DBMS와 B+트리 인덱스

1) MySQL (InnoDB 스토리지 엔진):

• 구조: InnoDB는 클러스터형 인덱스(clustered index)로 B+트리를 사용한다. 기본 키(primary key)는 클러스터형 인덱스로 저장되며, 이 인덱스는 실제 데이터 페이지와 직접 연결된다.
• 장점: 데이터가 인덱스 순서대로 저장되기 때문에 범위 조회가 매우 효율적이다. 또한, B+트리의 높은 노드 밀도로 인해 디스크 I/O 횟수가 줄어들어 성능이 향상된다.

 

2) PostgreSQL:

• 구조: PostgreSQL은 B+트리에 기반한 btree 인덱스를 기본 인덱스 구조로 사용한다.
• 장점: 다양한 데이터 타입과 복합 인덱스 지원, 효율적인 삽입 및 삭제 작업 등이 가능한다. 또한, PostgreSQL은 인덱스의 균형을 유지하기 위해 정기적으로 VACUUM 및 REINDEX 작업을 수행한다.

 

3) Oracle:

• 구조: Oracle Database는 B+트리 구조를 사용하는 인덱스를 기본으로 제공하며, 이는 글로벌 및 로컬 인덱스 모두에 적용된다.
• 장점: Oracle의 인덱스는 고도의 최적화와 함께 대규모 데이터베이스 환경에서 안정적인 성능을 보장한다. 또한, 비트맵 인덱스와 같은 특수한 인덱스 유형도 지원하여 다양한 쿼리 최적화에 기여한다.

B+트리 인덱스의 작동 원리

B+트리 인덱스는 데이터베이스 테이블의 특정 열에 대한 검색을 빠르게 수행할 수 있도록 도와준다.

 

예를 들어, 직원 테이블에서 employee_id 열에 B+트리 인덱스를 생성하면, 특정 employee_id를 가진 레코드를 신속하게 찾을 수 있다.

 

다음과 같은 인덱스 구조를 생각해보자.

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

• 내부 노드: [30 |60 |90]는 인덱스 키를 포함하며, 각 키는 하위 노드의 범위를 정의한다.
• 리프 노드: [10 |20], [40 |50], [70 |80], [100]은 실제 데이터 레코드에 대한 포인터를 포함한다.
• 연결 리스트: 리프 노드들이 순차적으로 연결되어 있어 범위 조회 시 효율적으로 데이터를 탐색할 수 있다.

B+트리 인덱스의 작동 원리를 보다 명확히 이해하기 위해, 특정 키를 검색하고 범위 조회를 수행하는 과정을 단계별로 살펴보자.

1. 특정 키 검색 예시: 50 검색

목표: 직원 테이블에서 employee_id가 50인 레코드를 찾는다.

단계 1: 루트 노드 탐색

• 현재 노드: [30 |60 |90]
• 비교: 50은 30보다 크고 60보다 작다.
• 이동 경로: 50이 속한 범위는 [40 |50] 리프 노드가 있는 두 번째 자식 노드.

단계 2: 해당 리프 노드 탐색

• 리프 노드: [40 |50]
• 비교: 50이 존재하는지 확인.
• 결과: 50이 발견되어, 해당 레코드의 포인터를 통해 employee_id = 50인 직원 레코드를 신속하게 접근할 수 있다.

검색 과정:

루트 노드: [30 |60 |90]
           /      |      |      \
    [10 |20] [40 |50] [70 |80] [100]

검색 경로: 루트 노드 → [40 |50] 리프 노드 → 레코드 찾기

2. 범위 조회 예시: 25부터 75까지의 employee_id 검색

목표: 직원 테이블에서 employee_id가 25부터 75까지인 모든 레코드를 찾는다.

단계 1: 시작 키 검색 (25)

• 루트 노드: [30 |60 |90]
• 비교: 25은 30보다 작으므로, 왼쪽 자식 노드 [10 |20]로 이동.
• 리프 노드: [10 |20]
• 결과: 25은 [10 |20] 리프 노드에 없으므로, 다음 리프 노드로 이동.

단계 2: 연결 리스트를 통한 연속 리프 노드 탐색

• 다음 리프 노드: [40 |50]
• 비교 및 수집: 40, 50이 25부터 75 사이에 포함되므로, 해당 레코드를 수집.
• 다음 리프 노드: [70 |80]
• 비교 및 수집: 70이 포함되지만, 80은 제외됨. 따라서 70 레코드만 수집.

단계 3: 종료 조건 확인

• 다음 리프 노드: [100]
• 비교: 100은 범위를 벗어나므로 조회 종료.

범위 조회 과정 시각화:

루트 노드: [30 |60 |90]
           /      |      |      \
    [10 |20] [40 |50] [70 |80] [100]

범위 조회 경로:
- 시작: [10 |20] (25는 없음)
- 다음: [40 |50] (40, 50 수집)
- 다음: [70 |80] (70 수집, 80은 제외)
- 종료: [100] (범위 밖)

결과: 40, 50, 70에 해당하는 직원 레코드가 수집된다.

이러한 특성 덕분에 B+트리는 대규모 데이터베이스에서 인덱스 구조로 널리 채택되며, 빠른 데이터 접근과 효율적인 범위 조회를 가능하게 한다.

B*트리의 활용

B* 트리는 B-트리의 변형으로, 일부 DBMS에서 특정 상황에서 더 높은 노드 밀도와 낮은 트리 높이를 필요로 할 때 사용된다.

하지만 B+트리만큼 널리 사용되지는 않는다.

활용 사례

1) IBM DB2:

• 구조: IBM의 DB2는 일부 인덱스 구조에서 B*트리를 사용하여 노드 밀도를 높이고 성능을 최적화한다.
• 장점: B*트리는 B-트리에 비해 더 높은 노드 밀도를 제공하여 디스크 공간을 효율적으로 사용하고, 트리 높이를 낮추어 검색 성능을 향상시킨다.

2) 특정 커스텀 애플리케이션:

• 구조: 일부 커스텀 데이터베이스 애플리케이션이나 특수 목적의 데이터 저장 시스템에서는 B*트리를 채택하여 높은 데이터 밀도와 빠른 검색 성능을 구현한다.
• 장점: B*트리는 재분배 과정을 강화하여 노드 분할을 줄이고, 트리의 균형을 더 효과적으로 유지할 수 있다.

1.  

BST, AVL, BB 트리도 있는데 왜 하필 B 트리 계열일까?

비슷한 목적을 가진 다양한 트리 자료구조들이 존재하지만, 실제 인덱싱과 같은 대규모 데이터 관리에서 B-트리 계열이 가장 널리 사용되는 이유는 여러 가지이다.

BST, AVL 트리, BB 트리와 비교하여 B-트리 계열이 인덱싱에서 선호되는 이유를 구체적으로 보자.

1. 높은 노드 분기도(Branching Factor)

• B-트리는 높은 분기도를 가짐으로써 트리의 높이를 낮게 유지할 수 있다. 이는 트리의 깊이를 줄여 검색, 삽입, 삭제 연산 시 필요한 단계 수를 감소시킨다.
• 예시: m = 101인 B-트리를 고려해보자. 여기서 m은 각 노드가 가질 수 있는 자식 노드의 최대 개수이다.
  • 최소 키 수: 각 노드는 최소 ⌈m/2⌉ - 1 = 51 - 1 = 50개의 키를 가져야 한다.
  • 최대 키 수: 각 노드는 최대 m - 1 = 100개의 키를 가질 수 있다.
  • 트리 깊이: 예를 들어, 데이터 수가 10,510,100,501개일 때 B-트리의 깊이는 다음과 같이 계산할 수 있다.
    • 레벨 1 (루트): 최대 100개의 키 → 101개의 자식 노드
    • 레벨 2: 각 자식 노드가 최대 100개의 키를 가짐 → 101 * 101 = 10,201개의 키
    • 레벨 3: 101^3 = 1,030,301개의 키
    • 레벨 4: 101^4 = 104,060,401개의 키
    • 레벨 5: 101^5 = 10,510,100,501개의 키
    • 따라서, 트리의 깊이는 5이다.
  • 탐색 횟수: 깊이가 5인 트리에서 특정 키를 검색하려면 최대 5번의 노드 접근이 필요하다. 이는 매우 효율적인 검색을 가능하게 한다.

B-트리 (m=101)

• 노드당 키 수: 최소 50, 최대 100
• 데이터 수: 10,510,100,501 (≈1.05 × 10¹⁰)
• 트리 깊이: 5
• 탐색 횟수: 최대 5번
• 디스크 I/O 횟수: 최대 5번

AVL 트리

• 노드당 키 수: 1 (각 노드는 하나의 키만 가짐)
• 데이터 수: 10,510,100,501 (≈1.05 × 10¹⁰)
• 트리 깊이: 약 37 (log₂(10,510,100,501) ≈ 36.34)
• 탐색 횟수: 최대 37번
• 디스크 I/O 횟수: 최대 37번

BB 트리

• 노드당 키 수: 제한적 (예: m=4인 경우, 최소 2, 최대 3)
• 데이터 수: 10,510,100,501 (≈1.05 × 10¹⁰)
• 트리 깊이: 약 10 (log₄(10,510,100,501) ≈ 10.00)
• 탐색 횟수: 최대 10번
• 디스크 I/O 횟수: 최대 10번

이러한 비교에서 B-트리는 높은 분기도와 낮은 트리 깊이를 통해 다른 트리들에 비해 훨씬 적은 탐색 횟수와 디스크 I/O를 필요로 하여 압도적인 성능을 보인다.

디스크 I/O에서의 B-트리의 특성

디스크 기반 시스템에서는 데이터의 물리적 저장 방식이 성능에 큰 영향을 미친다. B-트리는 디스크 블록 단위로 데이터를 효율적으로 관리할 수 있도록 설계되었다.

 

1) 노드의 블록 적합성:

• 각 노드는 하나의 디스크 블록에 맞춰 설계된다. 이는 한 번의 디스크 읽기/쓰기 연산으로 노드 전체를 처리할 수 있음을 의미한다.
• 예를 들어, 디스크 블록 크기가 4KB일 때, B-트리 노드는 이 크기에 맞춰 키와 포인터를 저장하도록 구성된다.

2) 높은 분기도:

• 높은 분기도 덕분에 트리의 깊이가 낮아진다. 이는 검색, 삽입, 삭제 시 필요한 디스크 I/O 횟수를 줄여준다.
• 예시: m=101인 B-트리는 10,510,100,501개의 데이터를 관리하기 위해 최대 5번의 디스크 I/O만으로 원하는 데이터를 찾을 수 있다.

3) 순차 접근 최적화:

• B-트리는 트리의 리프 노드들이 연결 리스트 형태로 연결되어 있어, 범위 조회와 같은 순차적인 데이터 접근이 매우 효율적이다.
• 이는 특히 대규모 데이터베이스에서 연속된 레코드를 빠르게 조회할 수 있게 해준다.

4) 디스크 공간 효율성:

• 높은 노드 밀도로 인해 디스크 공간을 효율적으로 사용할 수 있다. 이는 더 많은 데이터를 더 적은 디스크 블록에 저장할 수 있음을 의미한다.
• 결과적으로, 디스크의 공간 활용도가 높아지고, 데이터 접근 속도가 향상된다.
  
  
  

결론

B-트리 계열이 인덱싱에서 가장 많이 사용되는 이유는 높은 노드 분기도와 낮은 트리 깊이를 통해 디스크 I/O 횟수를 최소화하면서도 대규모 데이터를 효율적으로 관리할 수 있기 때문이다.

 

또한, B+트리와 같은 변형은 범위 조회의 효율성을 더욱 높여 데이터베이스 인덱싱에 최적화된 구조를 제공한다. 반면, BST, AVL 트리, BB 트리는 메모리 기반 시스템에서는 효과적일 수 있으나, 디스크 기반 시스템에서의 성능 최적화 측면에서는 B-트리 계열에 비해 열세이다.

 

이러한 이유로 B-트리 계열이 데이터베이스 인덱싱과 같은 대규모 데이터 관리 시스템에서 널리 채택되고 있다.

---

자주 묻는 질문

1. m원 트리가 곧 b-트리인 건가요? 개념적으로 어떻게 다른가요 ?

1. m-원 트리

• 정의: 각 노드가 최대 ( m )개의 자식을 가질 수 있는 트리 구조이다.
• 특징:
  • 자식 노드의 개수가 고정되어 있지 않고, 최대 ( m )까지 가능.
  • 균형을 강제하지 않으므로, 특정 삽입/삭제 과정에서 트리의 높이가 불균형해질 수 있음.
  • 단순한 계층적 구조를 표현하는 데 적합.
• 사용 사례:
  • 기본적인 계층적 데이터 구조를 나타내는 데 주로 사용.

2. B-트리

• 정의: ( m )-원 트리의 특수한 형태로, 균형이 유지되도록 설계된 트리이다.
• 특징:
  • 각 노드는 최대 ( m-1 )개의 키를 가지며, 최대 ( m )개의 자식을 가질 수 있음.
  • 모든 리프 노드는 같은 깊이를 가짐 (완전 균형 트리).
  • 노드의 키는 정렬된 상태를 유지하며, 검색, 삽입, 삭제 연산 시 재구조화가 이루어짐.
  • 높이 균형을 유지하기 때문에 디스크 접근을 최소화하고 효율적인 검색이 가능.
• 사용 사례:
  • 데이터베이스 및 파일 시스템에서 인덱스 구조로 많이 사용 (예: MySQL의 InnoDB).

주요 차이점

특징	m-원 트리	B-트리
구조	균형이 강제되지 않음	균형 트리 (모든 리프 노드 깊이 동일)
노드 속성	최대 ( m )개의 자식 가능	( m-1 )개의 키와 ( m )개의 자식
사용 목적	일반적인 계층적 구조 표현	검색, 삽입, 삭제 시 높은 효율 제공
효율성	데이터 크기에 따라 비효율 가능	균형 유지로 항상 효율적인 탐색 가능

요약

m-원 트리는 일반적인 계층 구조를 표현하는 데 초점이 맞춰져 있고, 균형이나 효율성을 강제하지 않는다. 반면, B-트리는 m-원 트리의 한 유형으로, 균형을 강제하여 데이터 검색 및 관리에 최적화된 트리 구조이다.

 

결론적으로, B-트리는 m-원 트리의 특수한 경우라 할 수 있다.

---

2. B-트리, B+트리, B* 트리의 차이점이 무엇인가요 ?

1. B-트리

• 균형 이진 트리의 일반화로, 노드가 최대 ( m-1 )개의 키와 ( m )개의 자식을 가질 수 있음.
• 노드 내 키는 정렬되어 있으며, 키를 기준으로 트리 탐색이 이루어짐.
• 리프 노드를 포함한 모든 노드가 같은 깊이를 가짐 (완전 균형 트리).
• 삽입 및 삭제 시 노드 분할과 병합 과정을 통해 균형을 유지.
• 노드 내에서 키 검색, 삽입, 삭제가 모두 이루어짐.
• 사용 사례: 데이터베이스, 파일 시스템 등.

2. B+-트리

• B-트리의 변형으로, 리프 노드에만 데이터(키와 값)를 저장.
• 내부 노드는 키만 저장하며, 데이터 탐색의 경로 역할을 함.
• 리프 노드가 링크드 리스트 형태로 연결되어 있어 순차 접근에 유리.
• 삽입 및 삭제 시 리프 노드에서만 데이터 변경이 발생.
• 디스크 접근을 최소화하며, 범위 쿼리(순차 검색)에서 높은 성능을 제공.
• 사용 사례: 데이터베이스 인덱스 (예: MySQL InnoDB).

3. B*-트리

• B-트리의 변형으로, 노드의 최소 채우기 비율을 50%에서 66%로 증가.
• 노드 분할 전에 형제 노드와 데이터를 재배치하여 분할 빈도를 줄임.
• 일부 데이터는 분할 대신 인접 노드로 이동시켜 트리의 높이 증가를 지연.
• 노드 분할이 적어 B-트리보다 공간 효율성이 높음.
• 삽입 및 삭제 시 노드 병합과 재구조화 과정을 추가적으로 수행.
• 사용 사례: 디스크 기반 데이터 구조에서 높은 공간 효율성을 요구할 때.

주요 차이점 요약

특징	B-트리	B+-트리	B*-트리
데이터 저장	모든 노드	리프 노드	모든 노드
리프 연결	없음	있음 (링크드 리스트 형태)	없음
효율성	일반적	순차 검색에 유리	공간 효율성 높음
분할 빈도	높음	중간	낮음

 

---

3. 근데 왜 b* 트리가 잘 사용되지 않는 이유는 무엇 때문일까요 ?

B*-트리가 잘 사용되지 않는 이유는 다음과 같은 몇 가지 실용적인 한계와 대안 구조의 존재 때문이다.

1. 복잡한 구현

• B*-트리는 삽입 및 삭제 시 형제 노드 간 데이터 재배치와 같은 추가 작업이 필요하다.
• 이로 인해 구현이 복잡해지고, 유지보수가 어려워질 수 있다.
• 반면, B-트리와 B+-트리는 상대적으로 간단한 알고리즘으로도 충분히 효율적인 성능을 제공.

2. 메모리 관리의 어려움

• B*-트리는 노드 최소 채우기 비율(66%)을 강제하므로 노드 간 데이터 이동이 더 자주 발생한다.
• 이러한 재배치 과정은 메모리와 디스크 I/O의 추가 비용을 유발해 성능이 저하될 수 있다.
• 특히 대규모 데이터 세트에서 B*-트리의 이점이 상대적으로 감소한다.

3. 성능 차이의 미미함

• B*-트리는 노드 분할 빈도를 줄이고 공간 효율성을 높이는 장점이 있지만, 디스크 기반 시스템에서는 큰 차이를 만들지 못하는 경우가 많다.
• B+-트리와 같은 구조는 범위 검색 및 순차 접근에서 충분히 효율적이며, B*-트리의 장점이 두드러지지 않는다.

4. 범용성 부족

• B*-트리는 특정 환경(예: 매우 큰 데이터 세트나 높은 공간 효율성이 중요한 경우)에서만 유리하다.
• 반면, B+-트리는 데이터베이스 인덱스 등 일반적인 데이터 처리에서 널리 사용되며, 다양한 활용 사례를 커버한다.

5. 대체 기술의 존재

• 현대 시스템에서는 B+-트리와 같은 구조 외에도 LSM 트리(Log-Structured Merge Tree)와 같은 대안이 더 많이 사용된다.
• 이러한 구조들은 디스크 I/O를 최적화하고, 병렬 처리를 지원하는 데 더 효과적이다.