B-tree와 B+tree

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이 나온 이유다

잎만 읽고 끝내기: 인덱스 온리 스캔

잎에는 키 값이 그대로 들어 있다. 그래서 쿼리가 고르는 컬럼이 모두 인덱스에 있으면 힙에 가지 않고 인덱스만 읽어 답할 수 있다. PostgreSQL은 이것을 인덱스 온리 스캔(Index-Only Scan)이라 부르고, 조건을 둘로 정리한다.

• 인덱스가 원래 값을 저장하거나 되살릴 수 있어야 한다. B-tree는 늘 된다. GIN은 항목마다 값의 일부만 가져서 안 된다
• 쿼리가 인덱스에 저장된 컬럼만 참조해야 한다. (x, y) 인덱스로 SELECT x, y FROM tab WHERE x = 'key'는 되지만, 인덱스에 없는 z까지 고르면 안 된다

인덱스 항목에는 그 행이 지금 트랜잭션에 보이는지(MVCC 가시성) 정보가 없다. 그래서 인덱스 온리 스캔은 힙 페이지마다 "모든 행이 모두에게 보인다"를 표시한 가시성 맵(Visibility Map)을 먼저 본다. 표시된 페이지의 행은 힙을 읽지 않고 돌려주고, 표시되지 않은 페이지는 결국 힙을 읽는다. 이 표시는 VACUUM이 켜고, 페이지의 행이 바뀌면 꺼진다. 그래서 자주 바뀌는 테이블일수록 이득이 줄어든다 → PostgreSQL 내부 동작(MVCC·VACUUM·WAL·플래너)

INCLUDE 컬럼: 커버링 인덱스

검색 조건에는 쓰지 않지만 자주 함께 읽는 컬럼을 잎에 얹어 두면, 인덱스 온리 스캔으로 끝나는 쿼리가 늘어난다. 이런 인덱스를 커버링 인덱스(Covering Index)라고 한다.

CREATE INDEX tab_x_y ON tab (x) INCLUDE (y);
-- SELECT y FROM tab WHERE x = 'key'; 를 힙 없이 처리할 수 있다

• INCLUDE 컬럼은 잎 항목에만 저장되고, 길을 안내하는 위쪽 노드에는 들어가지 않는다. 검색이나 탐색 방향을 정하는 데는 쓰이지 않는다
• UNIQUE 인덱스에 INCLUDE를 붙이면 유일성은 키 컬럼(x)에만 적용된다
• 테이블 데이터를 한 벌 더 저장하는 셈이라 인덱스가 커지고 검색이 느려질 수 있다. INCLUDE가 있는 B-tree는 중복 제거(deduplication)도 쓰지 못한다. 넓은 컬럼은 조심하고, 테이블이 천천히 바뀌어 힙을 읽을 일이 드물 때 붙일 만하다
• PostgreSQL에서는 B-tree, GiST, SP-GiST가 INCLUDE를 지원한다(18 기준)

해시 테이블(해시 테이블)은 같음 비교만이라면 더 빠를 수 있지만 순서가 없어서 범위·정렬을 못 한다. B-tree가 관계형 DB의 기본 인덱스인 이유가 이 "정렬된 채로 낮은 높이"다. 인덱스를 거는 판단은 DB 인덱스와 트레이드오프, PostgreSQL에서 인덱스가 실제로 어떻게 쓰이는지는 PostgreSQL 내부 동작(MVCC·VACUUM·WAL·플래너)를 본다.

책: 8장. 데이터베이스: 인덱스와 트랜잭션

출처: PostgreSQL 18 — B-Tree Indexes: Implementation · PostgreSQL 18 — Index-Only Scans and Covering Indexes · PostgreSQL 18 — CREATE INDEX: INCLUDE · PostgreSQL 18 — Updating the Visibility Map · PostgreSQL 18 — Index Types: B-Tree · RFC 9562 — UUID: Sorting · Wikipedia — B-tree · Wikipedia — B+ tree