DB - B 트리를 사용하는 이유

B트리(B-tree)와 데이터베이스

B트리의 기본 구조와 동작 원리

B트리는 다음과 같은 특징을 가진 균형 트리 자료구조입니다:

1. 각 노드는 여러 개의 키(key)를 가질 수 있습니다.
2. 노드의 키들은 항상 정렬된 상태를 유지합니다.
3. 각 노드는 M차 B트리일 때 최대 M-1개의 키를 가질 수 있습니다.
4. 루트 노드를 제외한 모든 노드는 최소 ⌈M/2⌉-1개의 키를 가져야 합니다.

간단한 3차 B트리의 예시입니다:

       [4]
      /    \
    [2]    [6]
   /  \    /  \
[1] [3] [5] [7,8]

B트리를 사용하는 이유

1. 디스크 접근 최적화

데이터베이스에서 B트리를 사용하는 주된 이유는 디스크 I/O를 최적화하기 위해서입니다. 이는 다음과 같은 특성 때문입니다:

• 디스크는 블록 단위로 데이터를 읽고 씁니다
• 하나의 B트리 노드는 디스크의 한 블록에 대응되도록 설계됩니다
• 한 노드에 여러 키를 저장함으로써, 한 번의 디스크 접근으로 더 많은 데이터를 처리할 수 있습니다

2. 균형 유지와 성능

• 모든 리프 노드가 같은 레벨에 있어 균형이 유지됩니다
• 검색, 삽입, 삭제 모두 O(log N)의 시간 복잡도를 보장합니다
• 노드당 여러 키를 저장함으로써 트리의 높이가 이진 트리보다 작아집니다
  • 예: 1,000,000개의 레코드를 저장할 때
  • 이진 트리: 높이 약 20
  • 100차 B트리: 높이 약 4

3. 순차 접근의 효율성

• 모든 키가 정렬된 상태로 유지됩니다
• 범위 검색(range query)이 효율적입니다
• 리프 노드들이 링크드 리스트로 연결되어 있어 순차 접근이 용이합니다

이러한 특성들로 인해 B트리는 데이터베이스의 인덱스 구조로 널리 사용되고 있습니다. 특히 디스크 기반의 데이터베이스 시스템에서 매우 효율적인 성능을 제공합니다.