B-tree는 한 노드가 키 여러 개와 자식 여러 개를 가지는 균형 잡힌 다진 탐색 트리(balanced multi-way search tree)다. 어떤 키를 찾든 루트에서 잎까지의 깊이가 같다. 이진 탐색 트리처럼 정렬 규칙으로 가지를 고르지만(이진 탐색 트리), 노드 하나에 키를 많이 담아 트리가 아주 낮다. 1970년대에 바이어(Bayer)와 맥크레이트(McCreight)가 만들었고, "B"가 무엇의 약자인지는 저자들이 밝힌 적이 없다(balanced, Bayer, Boeing 등 여러 설이 있다).
왜 디스크에 맞나
DB는 데이터를 페이지 단위(PostgreSQL은 8KB)로 읽는다. 디스크에서는 몇 바이트를 읽든 페이지 하나를 읽는 비용이 비슷하므로, 노드 하나 = 페이지 하나로 두고 그 안에 키를 꽉 채운다.
- 노드 하나가 자식을 수백 개 가리키면, 높이 3~4만으로 수억 개의 키를 다룬다
- 찾기는 높이만큼의 페이지 읽기로 끝난다. 위쪽 몇 단은 자주 읽혀 거의 늘 메모리에 있다
- 탐색·삽입·삭제 모두 O(log n)(빅오 표기법). 노드가 넘치면 나누고(split) 부모로 키를 올려 균형을 유지한다
B+tree: DB가 실제로 쓰는 모양
DB 인덱스의 B-tree는 대개 B+tree 형태다.
내부 노드: [ 30 | 60 ] ← 길 안내용 키만
/ | \
잎: [10 20] ⇄ [30 45] ⇄ [60 75] ← 모든 키 + 행 위치, 형제끼리 연결- 키와 행 위치(PostgreSQL에서는 힙의 튜플 위치)는 잎에만 있고, 내부 노드는 범위를 안내하는 키만 가진다. 그래서 내부 노드에 키가 더 많이 들어가 트리가 더 낮다. PostgreSQL 문서에 따르면 B-tree 인덱스 페이지의 99% 이상이 잎이다
- 잎끼리 양방향 연결 리스트로 이어져 있어, 범위의 시작점 하나만 트리로 찾고 나머지는 옆으로 훑는다
잘하는 것과 못하는 것
- 잘함: 같음(
=), 범위(<·BETWEEN), 정렬(ORDER BY를 정렬 없이 순서대로 읽기), 앞이 고정된 패턴(LIKE 'abc%'. PostgreSQL에서는 C 로캘이 아니면text_pattern_ops같은 별도 연산자 클래스가 필요하다) - 못함:
LIKE '%abc'처럼 앞이 열린 패턴, 전문 검색, 배열·JSON 포함 관계. PostgreSQL에서는 이런 건 GIN·GiST 같은 다른 인덱스가 맡는다(역색인과 검색 엔진) - 비용: 쓰기마다 트리를 고쳐야 하고 페이지 분할이 일어난다. 무작위 키(UUIDv4 등)는 연달아 만든 값도 인덱스의 아무 위치에나 들어가서, 여기저기 페이지가 쪼개지고 쓰기와 캐시 효율이 떨어진다. 시간순으로 커지는 UUIDv7이 나온 이유다
해시 테이블(해시 테이블)은 같음 비교만이라면 더 빠를 수 있지만 순서가 없어서 범위·정렬을 못 한다. B-tree가 관계형 DB의 기본 인덱스인 이유가 이 "정렬된 채로 낮은 높이"다. 인덱스를 거는 판단은 DB 인덱스와 트레이드오프, PostgreSQL에서 인덱스가 실제로 어떻게 쓰이는지는 PostgreSQL 내부 동작(MVCC·VACUUM·WAL·플래너)를 본다.
출처: PostgreSQL 18 — B-Tree Indexes: Implementation · PostgreSQL 18 — Index Types: B-Tree · RFC 9562 — UUID: Sorting · Wikipedia — B-tree · Wikipedia — B+ tree