데이터베이스 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여 년간 스토리지 엔진 설계의 핵심 화두였다.

구성 요소와 탐색 절차

B+ 트리는 관계형 데이터베이스 관리 시스템(RDBMS)에서 인덱스를 구성하여 정렬된 데이터를 빠르게 검색하는 데 사용하는 자료구조이다. B+ 트리의 구성 요소는 내부 노드(internal node)와 리프 노드(leaf node)로 나뉜다. 내부 노드는 키 값과 자식 포인터를 저장하며 하위 노드의 위치를 전달하는 라우팅 역할을 수행한다. 리프 노드는 실제 데이터 또는 레코드 포인터를 저장하며 다른 리프 노드와 연결 리스트로 이어진다.

단일 키 검색은 루트 노드에서 시작하여 리프 노드에 도달하는 순서로 진행된다. 첫째, 루트 노드에 검색 키가 입력되면 내부 노드에 저장된 키 값과 비교한다. 둘째, 비교 결과에 따라 해당 범위의 자식 포인터를 선택하여 하위 노드로 이동한다. 셋째, 최하위 계층인 리프 노드에 도달하면 저장된 실제 데이터 또는 레코드 포인터를 조회하여 검색을 완료한다.

범위 검색은 특정 범위의 시작 지점을 찾은 뒤 리프 노드를 순회하는 순서로 진행된다. 첫째, 루트 노드부터 시작하여 조건 범위의 시작 키가 위치한 리프 노드를 탐색한다. 둘째, 시작 리프 노드에 도달한 후 연결 리스트를 통해 인접한 리프 노드로 이동한다. 셋째, 상위 노드를 다시 거치지 않고 연결된 리프 노드를 차례로 순회하며 범위에 해당하는 데이터를 연속으로 조회한다.

이러한 범위 검색 방식은 리프 노드가 단방향 또는 양방향 연결 리스트로 연결되어 있을 때 성립한다. 내부 노드에도 데이터가 분산 저장되는 B-트리에서는 순차 접근의 효율이 떨어지는 것으로 알려졌다.

데이터 갱신과 저장소 상태 변화

B+ 트리에서 데이터의 삽입과 삭제가 반복되면 노드의 구조적 변화가 발생한다. 노드의 허용 용량을 초과하여 새 데이터가 입력되면 노드 분할(split)이 일어난다. 반대로 데이터가 삭제되어 노드의 저장량이 줄어들면 노드 병합(merge)이 일어난다. 노드 분할과 노드 병합이 진행되면 디스크 페이지의 재배치 과정이 수반된다.

B+ 트리는 데이터 수정 시 기존 위치에 데이터를 덮어쓰는 제자리 갱신(in-place update) 방식을 취한다. 제자리 갱신 방식은 데이터를 조회할 때 일정한 읽기 성능을 유지하는 효과를 낸다. 다만 데이터를 기록할 때는 디스크의 여러 위치에 접근하는 무작위 입출력(랜덤 I/O)이 발생하는 한계가 있다.

기본키의 형태는 저장소의 상태 변화에 직접적인 영향을 준다. 순차적이지 않은 무작위 키(예: UUID)가 입력되면 데이터의 삽입 위치가 트리 전반으로 분산된다. 무작위 분산이 발생하면 페이지 채움률(fill factor)이 낮아지고 디스크 단편화가 심화된다. 이러한 이유로 시간순으로 정렬 가능한 ULID나 UUIDv7 형태의 키를 선호하는 경향이 2020년대에 형성된 것으로 알려졌다.

인덱스 구조의 비교와 적용 환경

데이터베이스 관리 시스템은 워크로드의 특성에 따라 인덱스 구조를 다르게 적용한다.

해시 인덱스와의 비교에서 B+ 트리는 정렬된 데이터 접근과 범위 검색에 적합한 구조를 제공한다. 그러나 단일 값을 직접 찾는 무작위 룩업이 중심이 되는 환경에서는 B+ 트리가 해시 인덱스보다 처리 속도가 느릴 수 있다. 이에 따라 PostgreSQL은 B-tree 외에 Hash, GiST, GIN, BRIN과 같은 인덱스 형식을 제공하여 쿼리 패턴에 따라 선택하도록 구성되어 있다.

로그 구조화 병합 트리(LSM-트리, Log-Structured Merge-tree)와의 비교에서 B+ 트리는 읽기 작업 중심의 환경에 적합하다. LSM-트리는 쓰기 작업을 순차적으로 기록하여 쓰기 처리량을 높이는 방식으로 작동한다. 반면 LSM-트리는 컴팩션(compaction) 비용이 발생하고 읽기 증폭(read amplification) 문제를 동반한다. 따라서 시스템에 적용할 인덱스 구조는 읽기 작업과 쓰기 작업의 상대적 비율에 따라 선택해야 한다는 평가를 받는다.