B-Tree

균형 잡힌 트리 자료구조입니다. 데이터베이스 인덱스에서 가장 많이 사용됩니다.

왜 B-Tree인가

이진 트리의 문제

          1
           \
            2
             \
              3
               \
                4
                 \
                  5

한쪽으로 치우치면 결국 순차 탐색과 같아집니다.

B-Tree는 항상 균형

        [3]
       /   \
    [1,2]  [4,5]

모든 리프 노드의 깊이가 같습니다.

특징

구조 (차수 3인 B-Tree)

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

• 차수(order): 한 노드가 가질 수 있는 최대 자식 수
• 한 노드에 최대 (차수-1)개의 키

탐색 과정

55 찾기:

1. 루트 [30, 60] 확인
   - 55 > 30, 55 < 60 → 가운데 자식으로

2. [40, 50] 확인
   - 55 > 50 → 오른쪽 자식으로

3. 리프에서 55 찾음

100만 건도 3~4번 비교로 찾습니다.

삽입 과정

25 삽입:

Before:
        [30]
       /    \
   [10, 20] [40, 50]

After:
          [30]
         /    \
  [10, 20, 25] [40, 50]

노드가 꽉 차면 분할(split):

Before: [10, 20, 25, 30] ← 꽉 참

After:
      [20]
     /    \
  [10]  [25, 30]

B-Tree vs B+Tree

B+Tree 구조

        [30, 60]           ← 내부 노드 (키만 저장)
       /    |    \
   [10,20] [40,50] [70,80] ← 리프 노드 (실제 데이터)
      ↔       ↔       ↔    ← 리프끼리 연결됨

범위 검색(BETWEEN 20 AND 50)시 리프만 따라가면 됩니다.

시간 복잡도