[자료구조] B-tree, B+tree

B-Tree

Balanced Tree!

이름처럼 균형을 가진 이진 탐색트리입니다.

주로 데이터베이스와 파일 시스템에서 대용량 데아터를 관리하는 데 쓰이며,

디스크 I/O를 최소화하고, 탐색, 삽입, 삭제 작업에서 효율적인 성능을 보여줍니다.

기본 B 트리

• 노드당 여러 개(두 개 이상)의 Key와 자식 포인터를 가지게 됩니다.

• 키는 정렬된 상태로 유지되며, 노드의 키 개수는 최소/최대 범위 내에 있어야 합니다.

• 자식 포인터는 반드시 (키 개수 + 1)개가 됩니다.

• 모든 리프 노드는 같은 깊이에 존재하며, 균형 트리를 유지합니다.

• 만약 노드의 키 개수가 최대를 초과할 경우, 노드를 쪼개어 나눕니다.

• 그렇기 때문에, 노드가 가질 수 있는 최소 키 개수는 (최대 키 개수/2 + 1) 을 초과해선 안 됩니다.

• 루트 노드는 예외로, 최소 키 개수 제약이 없어, 1개의 키만 가져도 됩니다!

동작의 시간 복잡도

• 삽입

  1. 탐색(검색):

     • 삽입할 적절한 리프 노드를 찾습니다 (O(log n)).

  2. 삽입 수행:

  •	리프 노드에 새 키를 정렬된 상태로 삽입합니다 (O(M), M은 차수의 크기). 
  

  1. 분할(Split):

  • 삽입된 노드가 최대 키 개수(M-1)를 초과할 경우, 중간 키를 부모 노드로 올리고 노드를 분할합니다.

  • 필요 시 재귀적 분할(Recursive Split) 발생 (O(log n)).

• 삭제

  1. 탐색(검색):

  • 삭제할 노드를 탐색합니다 (O(log n)).

  1. 삭제 수행:

  • 삭제할 키가 리프 노드에 있는 경우, 해당 키를 직접 삭제합니다 (O(M)).

  • 삭제할 키가 내부 노드에 있는 경우:

  • 왼쪽 최대값(Predecessor) 또는 오른쪽 최소값(Successor)으로 대체합니다.

  1. 병합(Merge) 또는 재분배(Redistribution):

  • 부족한 키 개수로 인해 최소 키 조건을 충족하지 못하면 이웃 노드와 병합하거나 키를 재분배합니다.

  • 필요 시 재귀적 병합(Recursive Merge) 발생.

삭제의 경우, 그림으로 보는 게 훨씬 이해가 잘 됐습니다.

1. 리프노드에서의 제거

        [15]
       /    \
  [5 10]   [20 25]
--------------------------------------
10을 제거합니다.

        [15]
       /    \
  [5]      [20 25]
--------------------------------------
키 개수의 최소값은 2로, 왼쪽 아래 리프 노드는 부족한 키 상태입니다.

오른쪽 노드 [20 25]에서 재분배를 수행합니다.

        [20]
       /    \
  [5 15]   [25]


2. 내부 노드 삭제

          [15]
         /    \
   [5 10]   [20 25]
--------------------------------------
15를 삭제합니다.

          [  ]
         /    \
   [5 10]   [20 25]

--------------------------------------
비어있는 루트 노드에 왼쪽 최대값이나 오른쪽 최소값을 삽입합니다.
        [10]
       /    \
  [5]      [20 25]

3. 내부 노드의 중간값

  [p1 5 p2 10 p3 15 p4]
  /     |      |     \
[3 4] [6 8] [12 14]  [18 19]
--------------------------------------
중간 값인 10을 삭제하게 되면, 포인터 수가 키+2가 되어버립니다.

따라서, 삭제한 중간 노드에 왼쪽 최소값, 오른쪽 최대값을 가져옵니다.

  [p1 5 p2 12 p3 15 p4]
  /     |      |     \
[3 4] [6 8]   [14]  [18 19]

--------------------------------------
다만, 이럴 경우 p3에 해당하는 노드의 키 개수가 부족해질 수 있으므로

  [p1 5 p2+p3 15 p4]
  /     |         \
[3 4] [6 8 14]  [18 19]

이처럼 포인터 자체를 합쳐 하위 노드를 병합할 수도 있습니다.

차수와 깊이의 관계

• 높은 차수(M이 큼):

  • 장점:

    • 더 낮은 깊이(Height) → 더 빠른 탐색

      • 디스크 접근 횟수 감소 → 디스크 I/O 최적화.

  • 단점:

    • 노드 관리 오버헤드 증가: 키와 포인터가 많아 노드 내부 탐색 시간 증가(O(M)).

    • 메모리 사용량 증가.

• 낮은 차수(M이 작음):

  • 장점:

    • 노드 관리가 용이: 각 노드의 키 개수가 적어 관리와 탐색이 빠름.

    • 메모리 사용량 절약.

  • 단점:

  • 더 큰 깊이(Height) → 더 많은 디스크 접근 필요.

  • 탐색 성능 저하

  • 예시 - 데이터베이스 인덱스:

    • MySQL InnoDB는 B+트리 인덱스를 사용하며, 차수를 디스크 블록 크기와 맞춥니다.

    • 예: 블록 크기 4KB, 키 크기 100B → 최대 자식 수 M은 약 40개.

B+Tree

B 트리의 구조를 유지하며 확장된 형태로, 대용량 데이터 관리와 범위 검색을 위해 설계된 균형 트리입니다.

B+트리와 B트리의 차이점을 정리하면 다음과 같습니다.

특성	B-트리	B+트리
데이터 저장 위치	모든 노드(내부 + 리프 노드)	리프 노드에만 데이터 저장
내부 노드 구성	키와 데이터 모두 저장 가능	키와 포인터만 저장 (데이터 없음)
리프 노드 연결	연결 없음	Linked List 형태로 리프 노드 연결
범위 검색 (Range Query)	느림 (전체 트리 순회 필요)	빠름 (리프 노드 연결 리스트 탐색)
중복 데이터 저장	없음 (중복 키 없음)	있음 (내부 노드와 리프 노드 키 중복)
트리 높이 (Height)	더 낮음 (데이터가 모든 노드에 있음)	더 큼 (데이터가 리프 노드에만 있음)
탐색 성능 (Search)	O(log n)	O(log n) + 순차 검색 가능
삽입/삭제 시 복잡성	복잡 (내부 노드 조정 필요)	단순 (리프 노드 중심)
적용 사례	파일 시스템 인덱스, 데이터베이스 관리	데이터베이스 인덱스, 키-값 저장소

핵심적인 내용은 두 가지입니다.

• 리프 노드에만 데이터를 저장하고, 내부 노드는 키와 포인터만 가집니다.

• 리프 노드는 링크드 리스트로 연결되어 데이터 검색이 훨씬 용이합니다.

내부 노드에는 데이터를 저장하지 않아, 더 많은 인덱스 키와 포인터를 저장할 수 있어,

결과적으로 더 작은 트리 높이를 유지할 수 있어 디스크 I/O를 줄일 수 있습니다.

B+tree의 삽입과 삭제에 대해서는 다음 블로그에 너무 설명이 잘 되어있습니다!

https://ajroot5685.github.io/posts/B+-Tree/

그렇다면 왜 DB에서는 B tree 구조를 사용할까?

일반적인 이진트리의 경우 단점이 대단히 많습니다.

• 2개의 자식 노드만 갖게 되면, 깊이가 대단히 깊어져 디스크 I/O가 매우 많이 발생합니다.

• 균형 조정이 이루어지지 않을 경우, 최악의 경우 탐색에 O(n)의 복잡도가 발생할 수 있습니다.

• DB에서 B-트리는 디스크 블록 크기에 맞춰 노드를 관리하는 방식으로 최적화할 수 있습니다.

• B+트리는 리프 노드가 연결 리스트이므로, 범위 검색이 가능합니다.

이외에도 다양한 이유로 DBMS에서는 B tree 활용하고 있습니다!