B+ 트리 (B+ Tree)

한 줄 정의: 데이터베이스와 파일시스템이 수백만 건의 자료를 빠르게 찾기 위해 쓰는, 모든 실제 데이터를 맨 아래 잎(leaf) 노드에만 저장하는 균형 트리 구조입니다.

쉽게 풀면

전화번호부에서 "김"씨를 찾는다고 생각해봅시다. 처음부터 끝까지 한 장씩 넘기면 너무 오래 걸리니, 책 중간중간에 "가~나", "다~라" 같은 색인 탭을 붙여두면 훨씬 빨리 찾을 수 있습니다. B+ 트리는 이 색인 탭을 여러 층으로 쌓은 구조입니다. 위쪽 층(내부 노드)에는 "어느 방향으로 가야 하는지" 알려주는 안내 값만 있고, 실제 데이터는 전부 맨 아래 층(잎 노드)에 순서대로 저장됩니다. 게다가 잎 노드끼리는 옆으로 연결되어 있어서, "이 값 이상 모두 보여줘" 같은 범위 검색도 한 번에 쭉 훑을 수 있습니다.

왜 중요한가

B+ 트리는 관계형 데이터베이스, 파일시스템, 검색 엔진 등 대용량 데이터를 저장하고 빠르게 조회해야 하는 거의 모든 시스템의 인덱스 구조로 쓰이기 때문에, 데이터베이스·스토리지 시스템 연구에서 성능 비교의 기준선(baseline)으로 자주 등장합니다. 특히 디스크나 SSD처럼 접근 단위가 큰 저장 매체에서 입출력 횟수를 줄이는 방향으로 트리 구조를 개선하는 연구가 많아, 새로운 인덱스 구조를 제안하는 논문은 대부분 B+ 트리와의 비교를 통해 자신의 개선점을 입증합니다. 최근에는 학습 기반 인덱스(learned index)나 인메모리 데이터베이스처럼 B+ 트리를 대체하거나 변형하려는 연구 흐름도 활발합니다.

논문에서는 이렇게 쓰입니다

"제안한 인덱스 구조는 B+ 트리 기반 인덱스 대비 범위 질의(range query) 처리 시간을 약 30% 단축했다."

이 문장은 "새로 제안한 방법이, 데이터베이스에서 표준으로 쓰이는 B+ 트리 인덱스보다 특정 범위의 데이터를 찾는 속도가 더 빠르다"는 뜻입니다.

"본 파일시스템은 메타데이터 관리를 위해 B+ 트리 기반 인덱스를 채택하여 대규모 디렉터리에서도 안정적인 탐색 성능을 유지한다."

이 문장은 "파일시스템이 수많은 파일과 폴더 정보를 효율적으로 찾기 위해 B+ 트리 구조를 사용했고, 그 덕분에 파일이 아주 많아져도 속도가 크게 느려지지 않는다"는 뜻입니다.

"제안된 학습 기반 인덱스(learned index)는 전통적인 B+ 트리 대비 메모리 사용량을 크게 줄이면서도 유사한 조회 성능을 보였다."

이 문장은 "머신러닝 모델로 데이터 분포를 학습해 인덱스 역할을 하게 만든 새로운 방식이, 기존 B+ 트리보다 메모리는 덜 쓰면서도 검색 속도는 비슷하게 유지했다"는 뜻입니다.

조금 더 깊게 보면

논문을 읽다 보면 B+ 트리의 "차수(order, fan-out)"라는 표현을 자주 만나게 되는데, 이는 노드 하나가 가질 수 있는 자식(또는 키)의 최대 개수를 뜻하며 차수가 클수록 트리의 높이가 낮아져 탐색에 필요한 디스크 접근 횟수가 줄어듭니다. 그래서 많은 연구가 노드 크기를 디스크 페이지 크기(예: 4KB)에 맞추어 한 번의 입출력으로 최대한 많은 안내 값을 읽어오도록 설계합니다. 또한 삽입·삭제가 잦은 환경에서는 노드 분할(split)과 병합(merge) 과정에서 발생하는 오버헤드를 줄이는 것이 성능 비교의 핵심 지표가 되며, 동시성 제어를 위한 잠금(lock) 기법이나 캐시 친화적인 레이아웃 개선도 관련 연구 주제로 자주 다뤄집니다.

주의할 점

비슷한 이름의 B-트리와 혼동하기 쉽지만 구조가 다릅니다. B 트리는 데이터가 내부 노드에도 저장되지만, B+ 트리는 내부 노드에는 안내 값만 두고 실제 데이터는 잎 노드에만 저장합니다. 이 차이 때문에 B+ 트리가 범위 검색과 순차 접근에 더 유리해, 실무 데이터베이스 인덱스로는 B+ 트리가 훨씬 널리 쓰입니다.