본문으로 건너뛰기

1. B-Tree 소개​

1.1 B-Tree의 정의와 역사​

  • B-Tree는 1972년 루돌프 바이어(Rudolf Bayer)와 에드워드 맥크레이트(Edward M. McCreight)가 개발한 자료구조입니다.
  • 대용량 데이터의 효율적인 처리를 위해 설계되었으며, 현대 데이터베이스 시스템의 근간이 되는 자료구조입니다.
  • 'B'의 정확한 의미는 명시되지 않았지만, Balanced(균형), Boeing(개발 당시 근무처), Bayer(개발자) 등으로 추측됩니다.

1.2 B-Tree의 특징​

  • 자가 균형(Self-balancing) 트리 구조입니다.
    • 모든 리프 노드가 같은 레벨에 위치하여 검색 성능이 일관적입니다.
  • 하나의 노드가 여러 개의 키와 자식을 가질 수 있습니다.
    • 이진 트리와 달리 차수(degree)가 2보다 큰 트리입니다.
  • 디스크 기반 자료구조에 최적화되어 있습니다.
    • 노드 크기를 디스크 블록 크기에 맞춰 I/O 효율성을 극대화합니다.

2. B-Tree의 구조와 규칙​

2.1 B-Tree의 기본 구성 요소​

  • 노드(Node): B-Tree의 기본 구성 단위
    • 키(Key): 노드 내에 정렬된 상태로 저장되는 데이터
    • 포인터(Pointer): 자식 노드를 가리키는 참조값
  • 노드의 종류
    • 루트 노드(Root Node): 트리의 최상위 노드
    • 내부 노드(Internal Node): 루트와 리프 사이의 노드
    • 리프 노드(Leaf Node): 자식이 없는 말단 노드

2.2 B-Tree의 핵심 규칙​

차수(order)의 이해

B-Tree의 차수 n은 노드가 가질 수 있는 최대 자식 수를 의미합니다. 이를 기준으로 다음 규칙들이 정해집니다.

  • 노드의 키 개수 규칙:
    • 최소 키 개수: ⌈n/2⌉ - 1 (루트 노드 제외)
    • 최대 키 개수: n - 1
  • 노드의 자식 개수 규칙:
    • 최소 자식 개수: ⌈n/2⌉ (루트 노드와 리프 노드 제외)
    • 최대 자식 개수: n
  • 키와 자식 수의 관계:
    • 자식 수 = 키의 수 + 1
  • 정렬 규칙:
    • 노드 내의 키들은 오름차순으로 정렬
    • 각 키의 왼쪽 서브트리의 모든 키 < 현재 키 < 오른쪽 서브트리의 모든 키

2.3 실제 예시: 3차 B-Tree의 제약 조건​

3차 B-Tree 특성

3차 B-Tree는 가장 단순한 형태의 B-Tree로, 학습과 이해에 좋은 예시입니다.

  • 최대 자식 수: 3개
  • 최대 키 수: 2개
  • 최소 자식 수: 2개
  • 최소 키 수: 1개
  • 가능한 노드 구성:
    • [K1] : 키가 1개인 경우
    • [K1|K2] : 키가 2개인 경우

3. B-Tree의 연산​

3.1 검색(Search) 연산​

  • 검색 과정은 루트에서 시작하여 리프까지 진행됩니다:
    1. 현재 노드에서 검색 키와 노드 내 키들을 비교
    2. 적절한 자식 노드로 이동
    3. 키를 찾거나 리프에 도달할 때까지 반복
def search(root, key):
    current = root
    while current:
        i = 0
        # 현재 노드에서 키 찾기
        while i < len(current.keys) and key > current.keys[i]:
            i += 1
        
        if i < len(current.keys) and key == current.keys[i]:
            return (current, i)  # 키를 찾음
            
        if current.is_leaf:
            return None  # 키가 없음
            
        current = current.children[i]  # 다음 노드로 이동

3.2 삽입(Insertion) 연산​

  • 삽입은 항상 리프 노드에서 이루어집니다.
  • 삽입 과정의 주요 단계:
    1. 삽입할 위치 검색
    2. 리프 노드에 키 삽입
    3. 필요시 노드 분할

3.2.1 노드 분할(Split) 과정​

분할 시 주의사항

노드 분할은 상향식(bottom-up)으로 이루어지며, 트리의 높이가 증가할 수 있습니다.

  1. 중간 키(median) 선정
  2. 중간 키를 부모 노드로 이동
  3. 나머지 키들을 두 노드로 분배
  4. 필요시 부모 노드도 분할

3.3 삭제(Deletion) 연산​

  • 삭제는 크게 두 가지 경우로 나뉩니다:
    1. 리프 노드에서의 삭제
    2. 내부 노드에서의 삭제

3.3.1 리프 노드 삭제​

  1. 키 제거 후 노드가 최소 키 개수를 만족하면 종료
  2. 불만족시 다음 단계 진행:
    • 형제 노드에서 키 빌리기(재분배)
    • 형제 노드와 병합(merge)

3.3.2 내부 노드 삭제​

  1. 선행자(predecessor) 또는 후행자(successor) 찾기
  2. 해당 키와 위치 교환
  3. 리프 노드에서 삭제 수행

4. B-Tree의 활용​

4.1 데이터베이스 시스템​

  • 인덱싱(Indexing)
    • 테이블의 컬럼에 대한 빠른 검색 지원
    • 범위 검색(Range Query) 효율적 처리
  • 파일 시스템
    • 디렉토리 구조 관리
    • 파일 접근 효율성 향상

4.2 성능 특성​

  • 시간 복잡도
    • 검색: O(log n)
    • 삽입: O(log n)
    • 삭제: O(log n)
  • 공간 효율성
    • 노드 활용도: 최소 50%
    • 균형 유지로 일관된 성능 보장

5. B-Tree의 확장​

5.1 B+Tree​

  • B-Tree의 변형으로, 모든 데이터를 리프 노드에 저장
  • 리프 노드들을 연결 리스트로 구성
  • 범위 검색에 더욱 효율적

5.2 B*Tree​

  • 노드 분할을 최소화하기 위해 2/3 이상 채워지도록 설계
  • 형제 노드와의 재분배를 우선적으로 시도
  • 공간 활용도가 더 높음

6. 실제 구현 시 고려사항​

6.1 디스크 I/O 최적화​

  • 노드 크기를 디스크 블록 크기에 맞춤
  • 캐시 활용으로 빈번한 I/O 감소
  • 순차적 접근 패턴 고려

6.2 동시성 제어​

  • 락(Lock) 관리
  • 트랜잭션 처리
  • 복구(Recovery) 방안

7. 결론​

  • B-Tree는 대용량 데이터 처리에 최적화된 자료구조입니다.
  • 균형 잡힌 구조와 효율적인 연산으로 데이터베이스 시스템의 핵심 요소입니다.
  • 다양한 확장과 최적화를 통해 현대 컴퓨팅의 근간을 이루고 있습니다.