데이터베이스 B+ 트리 구조와 저장소 효율성

개요

1970년대 초, IBM 연구원 루돌프 바이어(Rudolf Bayer)와 에드워드 맥크레이트(Edward McCreight)가 발표한 하나의 자료구조가 이후 반세기 동안 거의 모든 관계형 데이터베이스의 심장부에 자리 잡게 될 줄은 아무도 몰랐다. 1972년 보잉의 연구 부서에서 근무하던 이 둘은 디스크 접근 횟수를 최소화하면서도 정렬된 데이터를 빠르게 검색할 방법을 고민했고, 그 결과물이 B-트리였다. 오늘날 MySQL의 InnoDB, PostgreSQL, Oracle, SQL Server 등 사실상 모든 주요 RDBMS가 인덱스 구조로 B+ 트리를 채택하고 있다.

B-트리에서 B+ 트리로

원조 B-트리는 내부 노드(internal node)에도 실제 데이터를 저장할 수 있었다. 문제는 여기서 시작된다. 내부 노드에 데이터가 섞이면 노드 하나에 담을 수 있는 키의 개수가 줄어들고, 트리의 높이가 늘어나며, 결과적으로 디스크 I/O 횟수가 증가한다. B+ 트리는 이 구조를 개량해 실제 데이터(또는 데이터를 가리키는 레코드 포인터)를 오직 리프 노드(leaf node)에만 저장하도록 강제한다. 내부 노드는 오로지 키 값과 자식 포인터만 갖는 "이정표" 역할만 수행한다.

이 단순해 보이는 설계 변경의 효과는 막대하다. 내부 노드가 순수하게 라우팅 정보만 담으면, 하나의 노드(대개 디스크 페이지 크기인 4KB, 8KB, 16KB 단위와 맞춘다)에 훨씬 더 많은 키를 우겨넣을 수 있다. 예를 들어 키가 8바이트, 포인터가 8바이트인 환경에서 16KB 페이지를 쓴다면 한 노드에 약 1,000개의 자식 포인터를 담을 수 있다. 이는 팬아웃(fanout)이 1,000이라는 뜻이고, 10억 개의 레코드를 저장해도 트리의 높이는 3~4단계면 충분하다는 계산이 나온다. 실제로 InnoDB의 B+ 트리는 페이지 크기 16KB 기준으로 대략 3단계만으로 수천만 행을 커버하는 것으로 알려져 있다.

리프 노드의 연결 리스트, 그리고 범위 검색

B+ 트리가 B-트리보다 실무에서 압도적으로 선호되는 또 하나의 이유는 리프 노드들이 양방향(혹은 단방향) 연결 리스트로 이어져 있다는 점이다. WHERE age BETWEEN 20 AND 30처럼 범위 검색을 수행할 때, 루트에서 시작 지점을 찾은 뒤부터는 트리를 다시 타고 내려갈 필요 없이 리프 노드를 옆으로 순회하기만 하면 된다. B-트리에서는 데이터가 내부 노드에도 흩어져 있어 이런 순차 접근이 불가능하거나 훨씬 비효율적이다.

저장소 효율성과 트레이드오프

B+ 트리가 만능은 아니다. 삽입·삭제가 빈번한 워크로드에서는 노드 분할(split)과 병합(merge)이 발생하며, 이 과정에서 페이지 재배치 비용이 든다. 특히 순차적이지 않은 키(예: UUID)를 기본키로 쓰면 삽입 위치가 트리 전역에 무작위로 흩어지면서 페이지 채움률(fill factor)이 낮아지고 디스크 단편화가 심해진다. 이 때문에 실무에서는 시간순으로 증가하는 ULID나 정렬 가능한 UUID(UUIDv7 등)를 선호하는 흐름이 2020년대 들어 뚜렷해졌다.

또한 B+ 트리는 정렬된 접근에는 강하지만, 완전 무작위 접근(랜덤 룩업)이 지배적인 워크로드에서는 해시 인덱스보다 느릴 수 있다. 이 때문에 PostgreSQL은 B-tree 외에도 Hash, GiST, GIN, BRIN 등 다양한 인덱스 타입을 별도로 제공하며, 개발자가 쿼리 패턴에 맞춰 선택하도록 한다.

논쟁: LSM-트리와의 경쟁

2010년대 이후 RocksDB, LevelDB, Cassandra 등이 채택한 LSM-트리(Log-Structured Merge-tree)가 쓰기 집약적 워크로드에서 B+ 트리의 대안으로 부상하면서, "어느 구조가 더 나은가"는 데이터베이스 엔지니어링 커뮤니티의 단골 논쟁거리가 됐다. B+ 트리는 제자리 갱신(in-place update)을 하기 때문에 읽기 성능이 안정적이지만 쓰기 시 랜덤 I/O가 발생하는 반면, LSM-트리는 쓰기를 순차적으로 몰아넣어 쓰기 처리량은 높지만 컴팩션(compaction) 비용과 읽기 증폭(read amplification) 문제를 안고 간다. 결국 어느 쪽을 택할지는 워크로드의 읽기·쓰기 비율에 달려 있다는 것이 중론이며, 이 트레이드오프 자체가 지난 10여 년간 스토리지 엔진 설계의 핵심 화두였다.