B+ Tree 인덱싱과 순차 키 삽입

Database System Foundation이 말하듯 DBMS는 index 같은 저장 구조로 Disk I/O를 줄인다. 이 페이지는 그 index가 실제로 어떻게 동작하는지 — B+ Tree의 root/branch/leaf 구조와, Auto Increment key가 INSERT에 유리한 이유 — 를 다룬다. DB 조회 읽기 성능 최적화 패턴은 이 index가 선택한 page를 Buffer Pool·스토리지·복제가 어떻게 더 빨리 읽는지를 다룬다.

Root/Branch/Leaf 구조

flowchart TD
    R[Root page] --> B1[Branch page]
    R --> B2[Branch page]
    B1 --> L1[Leaf: 1..11]
    B1 --> L2[Leaf: 12..31]
    B2 --> L3[Leaf: 32..63]
    B2 --> L4[Leaf: 64..90]
    L1 <--> L2 <--> L3 <--> L4

• Root page: 탐색을 시작하고 첫 분기 방향을 정한다.
• Branch page: key 범위를 비교해 다음 child page를 정한다.
• Leaf page: 정렬된 index key와 row 접근 정보(또는 clustered row)를 가진다.
• Leaf page는 key 순서대로 연결된다. 이 연결이 시작점을 찾은 뒤 범위를 연속적으로 읽게 한다.^[1]

동등 조회와 범위 조회는 어떻게 다른가

• id = 12 같은 동등 조건은 root → branch → leaf 순으로 내려가 해당 key가 있는 leaf page를 찾는다.^[1:1]
• id > 12 AND id < 90 같은 범위 조건은 먼저 12 근처 leaf page를 찾고, 이후 leaf page의 옆 연결을 따라 90 전까지 순차적으로 읽는다.^[2]
• InnoDB 관점에서 Primary Key id와 secondary index email은 모두 index lookup을 할 수 있다. 다만 secondary index는 보통 Primary Key 값을 가진 뒤 clustered Primary Key에서 row를 다시 찾는 단계가 추가될 수 있다.^[3]

범위 조회: root → branch → leaf(12) → leaf(다음) → ... → 90
순차 삽입: root → branch → 오른쪽 끝 leaf → 새 key append
랜덤 삽입: root → branch → 임의 leaf → 공간 없으면 split

Auto Increment가 INSERT에 유리한 이유

증가하는 Auto Increment key는 일반적으로 가장 오른쪽 leaf page에 이어 삽입된다. 랜덤 key는 여러 leaf page 중간에 들어가 page split과 재배치를 더 자주 유발할 수 있다.^[4]

Auto Increment는 "숫자라서" 빠른 것이 아니라 삽입 위치가 시간에 따라 한 방향으로 진행되는 key라서 유리하다고 볼 수 있다. DBMS는 보통 오른쪽 끝 page를 계속 사용하므로 cache locality가 좋아지고, 중간 page split·page 이동·랜덤 I/O가 줄어든다. 반대로 UUID처럼 완전히 랜덤한 key는 분산 삽입을 만들어 page split 가능성을 높인다. 다만 시간순 UUID처럼 어느 정도 정렬되는 key는 이 비용을 완화할 수 있다.^[5]

인덱스의 장점은 단순히 "트리가 있어서 빠르다"가 아니라고 볼 수 있다. 필요한 leaf page까지의 탐색 비용을 작게 만들고, 범위 조회에서는 이미 정렬된 leaf 연결을 재사용해 root부터 다시 탐색하는 일을 줄인다는 데 있다. email이 unique index라면 동등 조회의 탐색 자체는 빠르지만, id Primary Key보다 항상 같은 비용이라고 볼 수는 없다 — secondary index leaf에서 얻은 Primary Key로 row를 다시 찾는 back-to-table 단계가 생길 수 있기 때문이다.^[5:1]

무엇을 얻고 무엇을 감수하는가

-- 동등 조회: 하나의 leaf 위치를 찾는다.
SELECT * FROM member WHERE id = 12;

-- 범위 조회: 12가 있는 leaf부터 90 전까지 순차로 읽는다.
SELECT * FROM member WHERE id > 12 AND id < 90 ORDER BY id;

-- email index가 secondary index라면 PK를 통한 row 접근이 추가될 수 있다.
SELECT * FROM member WHERE email = 'user@example.com';

이 페이지가 다루지 않는 것

• 이 페이지는 B+ Tree의 일반 원리를 설명한다. 특정 DBMS의 page 크기, optimizer 비용 모델, lock 구현 세부는 다루지 않는다.
• Auto Increment가 모든 write workload에서 최선이라는 뜻은 아니다. 매우 높은 동시 INSERT에서는 오른쪽 끝 page의 경합이 병목이 될 수 있다.
• index가 있더라도 함수 적용, 낮은 선택도, 복합 index의 선두 column 미사용 등으로 optimizer가 index를 사용하지 않을 수 있다.
• hash index는 동등 조회에는 적합할 수 있지만, 정렬된 범위 순회에는 B+ Tree처럼 자연스럽지 않다.

흔히 놓치는 지점

• email에 index가 없는데 WHERE email = ?가 빠를 것이라고 가정하면, 실제로는 full scan이 일어날 수 있다.
• id 범위 조회가 leaf 연결을 따른다는 사실을 무시하고, 각 id마다 독립 동등 조회를 반복하면 불필요한 탐색이 늘어난다.
• Random UUID Primary Key의 insert 비용을 무시하고 대량 INSERT에서 page split과 buffer pool churn을 관찰하지 않는 경우가 있다.
• Auto Increment가 빠르다는 이유만으로 workload·보안 요구·분산 ID 생성 요구를 고려하지 않는 경우가 있다.

관련

• Database System Foundation — index가 Disk I/O를 줄이는 저장 구조라는 상위 원리.
• DB 조회 읽기 성능 최적화 패턴 — index가 선택한 page의 메모리·스토리지 접근 비용을 다룬다.

출처

테스트 질문

• id > 12 AND id < 90에서 DBMS가 12부터 순차적으로 읽을 수 있는 이유는 무엇인가?
• email에 index가 있는데도 id Primary Key 조회보다 row 조회 비용이 클 수 있는 이유는 무엇인가?
• Auto Increment가 INSERT에 유리한 것은 어떤 B+ Tree page 동작 때문인가?