B+Tree 기본 구조

MySQL InnoDB는 B+Tree(비플러스트리)를 인덱스 자료구조로 사용합니다. MySQL 문서에서는 "B-tree"라고 표기하지만, 실제 구현은 B+Tree입니다. 특징은 아래와 같습니다.

  • 정렬된 구조: 키 값이 정렬되어 있어 범위 검색에 효율적
  • 균형 트리: 모든 리프 노드가 같은 깊이에 위치
    • 삽입 삭제시에 자동으로 정렬
    • 트리의 높이 = 디스크 I/O 횟수(메모리에 없는 최악의 경우 가정)
    • => 즉, 모든 리프 노드가 같은 깊이(높이)라는 것은 데이터가 몇 건이던 데이터를 조회할 때 같은 I/O 횟수로 접근함을 의미합니다.
  • 시간 복잡도: O(log n)의 검색/삽입/삭제 성능
  • 페이지 기반: 노드 하나 = 디스크 페이지 하나 (16KB)
    • 처음부터 디스크에 어떻게 효율적으로 접근할지에 대한 고민으로 설계된 B-tree 구조의 파생 자료 구조이기 때문입니다.
    • B-tree와의 차이점은 추후 다룰 예정입니다.

노드 특징

내부 노드 (Internal/Branch Node)

B+트리에서 내부 노드는 실제 데이터는 없고 길잡이 역할만 수행합니다.

저장 내용:

  • 키 값 (정렬된 상태)
  • 자식 노드 포인터
  • ❌ 실제 데이터는 없음

리프 노드 (Leaf Node)

리프 노드의 경우 실제 데이터를 포함하며, 다음 리프 노드(형제)에 대한 포인터를 가지고 있습니다. 즉 리프노드 끼리는 LinkedList 형태로 구성되어 있습니다.

저장 내용:

  • 키 값
  • 실제 데이터 (또는 데이터 포인터)
  • 다음 리프 노드 포인터 (연결 리스트)

연결 리스트로 되어있어서 생기는 장점

  • 시작점부터 범위의 마지막에 해당되는 노드까지 포인터를 타고 쭉 순회하면 되기 때문에 범위 검색에 아주 효과적입니다.