B-트리 (B-Tree)와 B+트리 (B+ Tree) 비교하기

B-트리와 B+트리는 데이터베이스와 파일 시스템에서 널리 사용되는 데이터 구조로, 효율적인 검색, 삽입, 삭제를 위해 설계되었습니다. 이 두 구조는 비슷해 보이지만, 특정 용도에 따라 다른 특징과 이점을 제공합니다. 여기서 각 트리의 기본 개념과 차이점을 예시와 함께 살펴보겠습니다.

B-트리 (B-Tree)

B-트리는 균형 유지 이진 탐색 트리의 한 형태로, 모든 리프 노드가 같은 레벨에 위치하는 자가 균형 트리입니다. B-트리는 각 노드가 여러 개의 키를 저장할 수 있으며, 노드 내 키는 정렬된 상태를 유지합니다. 각 노드의 키 사이에는 자식 포인터가 있어서, 키 값에 따라 탐색 경로가 결정됩니다.

예시:

      [17 | 30]
     /     |     \
[5 | 12] [18 | 25] [31 | 40]

• 여기서 루트 노드는 17과 30이라는 두 개의 키를 가지고 있으며, 각 키는 자식 노드들로 연결됩니다.
• 17의 왼쪽에는 17보다 작은 모든 키([5 | 12]), 17과 30 사이의 키([18 | 25]), 그리고 30보다 큰 키([31 | 40])를 가진 노드가 위치합니다.

B+트리 (B+ Tree)

B+트리는 B-트리를 기반으로 하지만, 모든 실제 데이터(키)는 리프 노드에만 저장되고, 리프 노드들은 서로 연결 리스트로 연결되어 있어 순차 접근이 용이합니다. 내부 노드는 데이터가 아닌 키만을 저장하고, 이 키들은 리프 노드에서 찾을 수 있는 가장 큰 키를 가리킵니다. 이 특징 때문에 B+트리는 데이터베이스 시스템에서 효율적인 인덱싱을 위해 선호됩니다.

예시:

        [17 | 30]
       /     |     \
[5 | 12] [18 | 25] [31 | 40]
    |        |        |
[5, 12]  [18, 25]  [31, 40]

• B+트리에서는 모든 데이터가 리프 레벨에 있으며, 리프 노드들은 순차적으로 연결됩니다.
• 내부 노드([17 | 30])는 자식 노드를 가리키는 키를 가지고 있지만, 실제 데이터는 포함하고 있지 않습니다.

B-트리와 B+트리의 차이점

• 데이터 위치: B-트리는 각 노드에 데이터를 저장할 수 있지만, B+트리는 모든 데이터를 리프 노드에만 저장합니다.
• 리프 노드의 연결: B+트리의 리프 노드들은 링크드 리스트처럼 서로 연결되어 있어 순차 접근이 용이하지만, B-트리의 리프 노드들은 서로 연결되어 있지 않습니다.
• 탐색 성능: B+트리에서는 모든 리프 노드가 동일한 깊이에 위치하므로 데이터 접근 시간이 일관됩니다. B-트리는 리프 노드의 깊이가 다를 수 있어 불균형한 접근 시간이 발생할 수 있습니다.
• 공간 활용: B+트리는 내부 노드에 데이터를 저장하지 않기 때문에 더 많은 키를 저장할 수 있어 더 나은 공간 효율성을 제공합니다.

이러한 차이점들로 인해, B+트리는 대규모 데이터베이스 시스템에서 범위 검색과 같은 연산에 더 적합하며, B-트리는 균형 유지가 중요한 다양한 애플리케이션에서 사용됩니다.