B-Tree와 인덱스 — 데이터베이스의 보이지 않는 골격

백엔드 개발을 오래 하다 보면 이상한 순간을 마주친다. 쿼리 하나가 100밀리초 걸리던 게 어느 날 3초로 늘어난다. 코드도 그대로고, 인프라도 그대로인데. 대개 원인은 같은 곳에 있다 — 인덱스. 그리고 그 인덱스의 내부를 들여다보면 거의 항상 같은 자료구조가 있다 — B-Tree.

이 글은 B-Tree가 왜 그렇게 생겼는지, 왜 데이터베이스 세계의 표준이 되었는지, 그리고 인덱스 설계에서 이 구조를 알고 있는 것과 모르는 것이 어떤 차이를 만드는지를 다룬다.

 

왜 B-Tree인가 — 먼저 풀어야 할 문제

B-Tree를 이해하려면 B-Tree가 풀고자 했던 문제를 먼저 봐야 한다. 그 문제는 **"디스크는 느리다"**는 한 문장으로 요약된다.

메모리는 한 번 접근에 100나노초 수준, SSD는 100마이크로초, HDD는 10밀리초. 디스크 접근은 메모리 접근보다 수만 배에서 수십만 배 느리다. 데이터가 수백만 건이 넘어가면 메모리에 다 담을 수 없고, 결국 디스크에 저장해야 한다. 디스크에 저장된 데이터를 빠르게 찾으려면 어떻게 해야 하는가 — 이것이 B-Tree가 답하려는 질문이다.

이진 트리(Binary Tree)를 떠올려보자. 노드마다 자식이 둘. 1억 건의 데이터를 저장하면 트리 높이가 약 27이다. 균형 이진 트리인 Red-Black Tree나 AVL Tree도 마찬가지. 탐색마다 27번의 노드 접근이 필요하다. 이게 메모리에서 일어나면 수 마이크로초에 끝나지만, 디스크에서 일어나면 27 × 10ms = 270ms. 단일 탐색에 0.27초다. 이건 쓸 수 없다.

문제의 본질은 트리 높이가 아니라 디스크 I/O 횟수다. 디스크는 느리지만, 한 번 읽을 때 큰 덩어리로 읽는다. 하드디스크의 한 섹터, SSD의 한 페이지, 운영체제의 한 블록. 통상 4KB, 8KB, 16KB 단위다. 4바이트짜리 데이터 하나를 읽든 16KB를 읽든 디스크 접근 시간은 거의 같다. 그렇다면 한 번의 디스크 접근으로 최대한 많은 정보를 가져오는 구조가 필요하다.

 

B-Tree의 핵심 아이디어가 여기서 나온다. "트리의 각 노드를 디스크 블록 하나 크기만큼 키워라. 그러면 한 번의 디스크 읽기로 수백 개의 키를 한꺼번에 가져올 수 있다."

 

B-Tree의 구조 — 뚱뚱한 노드, 낮은 트리

B-Tree의 각 노드는 여러 개의 키와 자식 포인터를 담는다. 한 노드에 100~200개의 키를 담는다고 하면, 자식도 그만큼 많다. 이진 트리는 노드마다 자식이 2개였지만, B-Tree는 자식이 수백 개다. 이런 트리를 m-ary tree 또는 다진 트리라고 부른다.

이게 왜 중요한가. 1억 건의 데이터를 저장한다고 하자.

• 이진 트리: 높이 약 27
• 자식 100개짜리 B-Tree: 높이 약 4 (100⁴ = 1억)

1억 건을 찾는데 4번의 디스크 읽기면 끝이다. 40ms 정도. 이진 트리의 270ms와 비교하면 6~7배 빠르다. 그리고 데이터가 10배 늘어나도 B-Tree 높이는 겨우 1 증가한다. 10억 건이어도 5번의 디스크 읽기.

이게 B-Tree가 "데이터베이스의 표준 인덱스 구조"가 된 이유다. 디스크의 물리적 특성에 최적화된 자료구조인 것이다.

 

B-Tree의 규칙 — 균형을 유지하는 법

B-Tree가 항상 낮은 높이를 유지하려면 규칙이 필요하다.

차수(order) m인 B-Tree의 주요 규칙:

1. 모든 리프 노드는 같은 깊이에 있다 (완전 균형)
2. 각 내부 노드는 최소 ⌈m/2⌉개, 최대 m개의 자식을 가진다
3. 루트를 제외한 모든 노드는 최소 ⌈m/2⌉ - 1개의 키를 가진다
4. 키들은 노드 내에서 정렬되어 있다
5. 자식 포인터는 키 값의 범위에 따라 정확히 나뉜다

이 규칙들이 맞물려서 트리가 한쪽으로 치우치지 않는다. 삽입·삭제 시에도 이 규칙을 유지하기 위해 **노드 분할(split)**과 **병합(merge)**이 일어난다.

삽입 — 가득 차면 나눈다

새 키를 삽입할 자리를 찾아 내려가고, 리프 노드에 자리가 있으면 그냥 넣는다. 자리가 없으면 그 노드를 둘로 쪼갠다. 중간 키는 부모로 올린다. 부모도 가득 차 있으면 부모도 쪼갠다. 이 과정이 루트까지 올라갈 수 있다. 루트가 쪼개지면 트리 높이가 1 증가한다. 트리가 성장하는 방향은 위쪽, 즉 루트에서 일어난다. 이것이 B-Tree가 항상 균형을 유지하는 비밀이다.

삭제 — 너무 비면 합친다

키를 지우면 노드의 키 개수가 최소치 아래로 내려갈 수 있다. 이 경우 이웃 노드에서 키를 빌려오거나(재분배), 이웃 노드와 합친다(병합). 병합이 일어나면 부모의 키 하나가 내려와서 합쳐진 노드의 중간 키가 된다. 부모도 이로 인해 최소치 아래로 내려가면 연쇄적으로 병합이 일어난다. 루트까지 전파되면 트리 높이가 1 감소한다.

이 삽입·삭제의 우아함이 B-Tree의 또 다른 미덕이다. 트리는 스스로 균형을 맞춘다. 개발자가 별도로 리밸런싱을 신경 쓸 필요가 없다.

B+Tree — 실제 데이터베이스가 쓰는 건 이쪽이다

"B-Tree"라고 흔히 부르지만, MySQL의 InnoDB, PostgreSQL, Oracle, SQL Server가 실제로 사용하는 건 B+Tree다. B-Tree의 변종이면서, 실무에서는 거의 모든 RDBMS가 이 구조를 쓴다.

B-Tree와 B+Tree의 핵심 차이는 두 가지다.

첫째, 실제 데이터는 리프 노드에만 저장된다. B-Tree는 내부 노드에도 실제 레코드(또는 레코드 포인터)가 있지만, B+Tree는 내부 노드에 오직 탐색을 위한 키만 있다. 실제 데이터는 리프 노드에 전부 몰려 있다.

이 차이가 왜 중요한가. 내부 노드가 가벼워지므로 한 노드에 더 많은 키를 담을 수 있다. 그만큼 트리 높이가 더 낮아지고, 탐색 시 디스크 I/O가 더 줄어든다.

둘째, 리프 노드들이 연결 리스트로 이어져 있다. 모든 리프 노드가 순서대로 포인터로 연결되어 있어서, 한 번 시작점을 찾으면 순차 스캔이 가능하다. 이 구조가 **범위 검색(range query)**에서 빛을 발한다.

 

 

sql

SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-03-31';

이런 쿼리에서 B+Tree는 1월 1일에 해당하는 리프 노드를 찾고, 그 다음 리프 노드들을 연결 리스트처럼 따라가며 3월 31일까지 읽는다. 트리를 다시 타고 올라갈 필요가 없다. 범위 쿼리가 매우 빠른 이유다.

클러스터드 인덱스 vs 세컨더리 인덱스 — 리프에 무엇이 담기는가

인덱스 설계에서 반드시 구별해야 하는 개념이 클러스터드(clustered) 인덱스와 세컨더리(secondary) 인덱스다. 이 차이를 모르면 인덱스 추가가 왜 어떤 경우에는 신의 한 수이고 어떤 경우에는 악수인지 이해할 수 없다.

클러스터드 인덱스는 리프 노드에 실제 행(row) 전체가 저장된다. MySQL InnoDB의 Primary Key가 대표적이다. 테이블 자체가 B+Tree이고, 리프가 곧 데이터다. 그래서 InnoDB에서는 Primary Key로 조회하는 것이 가장 빠르다 — 인덱스를 찾으면 거기가 곧 데이터니까.

세컨더리 인덱스는 리프 노드에 "실제 데이터가 있는 위치"를 담는다. InnoDB에서는 그 위치가 Primary Key 값이다. 그래서 세컨더리 인덱스로 조회하면 다음과 같은 흐름이 일어난다:

1. 세컨더리 인덱스 B+Tree를 타고 내려가 리프에서 Primary Key 값을 얻는다
2. 그 Primary Key로 클러스터드 인덱스 B+Tree를 다시 타고 내려가 실제 행을 읽는다

이걸 **"테이블 룩업" 또는 "bookmark lookup"**이라고 부른다. 한 번 더 B+Tree를 타야 한다는 뜻이다. 세컨더리 인덱스 조회가 클러스터드 인덱스 조회보다 느린 이유가 여기에 있다.

이 구조를 알면 실무에서 왜 **"커버링 인덱스(covering index)"**가 자주 등장하는지 이해된다. 커버링 인덱스는 쿼리에 필요한 모든 컬럼을 인덱스에 포함시켜서 테이블 룩업을 생략하는 기법이다. 세컨더리 인덱스의 리프에서 필요한 모든 데이터를 얻을 수 있으면, 클러스터드 인덱스까지 갈 필요가 없다. 쿼리 성능이 몇 배로 빨라진다.

복합 인덱스의 정렬 원칙 — 왼쪽부터 쓴다

B+Tree는 키를 정렬된 상태로 저장한다. 복합 인덱스(composite index)도 마찬가지다. (a, b, c) 복합 인덱스는 먼저 a로 정렬하고, a가 같으면 b로, b도 같으면 c로 정렬한다. 전화번호부처럼.

이 정렬 순서 때문에 왼쪽 접두사(leftmost prefix) 원칙이 나온다. (a, b, c) 인덱스는 다음 쿼리에 유효하다:

• WHERE a = ?
• WHERE a = ? AND b = ?
• WHERE a = ? AND b = ? AND c = ?

하지만 다음 쿼리에는 전혀 쓸모가 없거나 제한적이다:

• WHERE b = ? — 무용지물. a 없이는 B+Tree 탐색 불가
• WHERE c = ? — 무용지물
• WHERE a = ? AND c = ? — a까지만 인덱스 활용, c는 스캔

전화번호부로 비유하면 명확하다. 성-이름 순으로 정렬된 전화번호부에서 성을 모르고 이름만으로 찾으려면 처음부터 끝까지 뒤져야 한다. B+Tree도 똑같다.

이 원칙을 무시하고 인덱스를 아무렇게나 만들면, "인덱스는 있는데 왜 안 타지?" 하는 상황이 생긴다. 대부분의 "인덱스 안 타는 쿼리" 이슈는 이 왼쪽 접두사 원칙 위반이다.

인덱스의 비용 — 공짜가 아니다

B+Tree 인덱스의 장점을 알면, 모든 컬럼에 인덱스를 걸고 싶어질 수 있다. 하지만 인덱스는 공짜가 아니다. 세 가지 비용이 있다.

첫째, 저장 공간. 인덱스 자체가 B+Tree 구조로 디스크를 차지한다. 큰 테이블에 여러 인덱스를 걸면, 인덱스의 총 크기가 테이블 데이터보다 클 수도 있다.

둘째, 쓰기 성능 저하. 레코드를 INSERT/UPDATE/DELETE 할 때마다 모든 관련 인덱스의 B+Tree를 수정해야 한다. 트리 균형을 위한 split·merge가 일어나면 비용이 더 크다. 인덱스가 5개 있는 테이블은 쓰기마다 6개의 B+Tree(테이블 클러스터드 + 5개 세컨더리)가 수정된다.

셋째, 잘못된 인덱스는 옵티마이저를 혼란시킨다. 데이터베이스 옵티마이저는 통계 정보를 바탕으로 어떤 인덱스를 쓸지 결정한다. 비슷하고 중복적인 인덱스들이 많으면 옵티마이저가 최적 선택을 못 하는 경우가 생긴다.

좋은 인덱스 설계는 "어떤 인덱스를 추가할까"만큼이나 "어떤 인덱스를 만들지 않을까"에 관한 것이다.

카디널리티와 선택도 — 어떤 컬럼에 인덱스를 걸 것인가

실무에서 인덱스를 설계할 때 판단 기준이 되는 개념이 **카디널리티(cardinality)**와 **선택도(selectivity)**다.

카디널리티는 컬럼의 고유 값 개수다. gender 컬럼은 카디널리티가 2~3 정도, email 컬럼은 거의 전체 행 수와 같다.

선택도는 "이 조건으로 필터링했을 때 얼마나 좁혀지는가"다. 선택도가 높으면 인덱스가 효과적이고, 낮으면 인덱스를 타도 별 도움이 안 된다.

gender = 'M'으로 조회하면 전체의 절반이 결과에 포함된다. 이 경우 인덱스를 타는 것이 오히려 전체 스캔(full scan)보다 느릴 수 있다. B+Tree를 타고 내려갔다가 다시 테이블 룩업을 해야 하니까. 옵티마이저가 인덱스를 무시하고 풀스캔을 선택하는 이유다.

경험칙: 결과가 전체 테이블의 10~20% 이상이면 인덱스가 별 효과가 없다. 이 경계는 DB와 데이터 분포에 따라 달라지지만, 대략의 기준으로 쓸 수 있다.

B-Tree가 잘 못하는 것 — 한계를 알아야 쓸 수 있다

B-Tree/B+Tree가 만능은 아니다. 잘 못하는 영역이 있다.

전문(full-text) 검색. WHERE content LIKE '%keyword%'는 B+Tree로 처리할 수 없다. 앞부분이 와일드카드이면 정렬된 구조를 활용할 수 없기 때문이다. 이런 경우 **역색인(inverted index)**이 필요하다. Elasticsearch, PostgreSQL의 GIN 인덱스가 이 용도다.

공간 데이터. 위경도 기반 근접 검색은 2차원 데이터인데, B+Tree는 1차원 정렬에 기반한다. 이런 경우 R-Tree나 Quadtree를 쓴다. PostGIS, MySQL Spatial 인덱스가 이 구조다.

매우 높은 쓰기 부하. B+Tree는 쓰기마다 트리 수정이 일어나 쓰기 비용이 있다. 시계열 데이터나 로그처럼 쓰기가 지배적이고 읽기는 범위 스캔이 대부분인 경우, **LSM-Tree(Log-Structured Merge Tree)**가 더 적합하다. Cassandra, RocksDB, ScyllaDB가 이 구조를 쓴다.

도구는 문제에 맞아야 한다. B-Tree는 **"정렬 가능한 키에 대한 균형잡힌 읽기·쓰기"**에 최적화된 도구다. 이 범위를 벗어나면 다른 도구를 찾아야 한다.

실무에서 B-Tree를 이해한다는 것

B-Tree의 내부를 안다는 것은 다음과 같은 판단을 할 수 있다는 뜻이다.

EXPLAIN을 읽을 때 **"왜 옵티마이저가 이 인덱스를 선택했는가"**를 추측할 수 있다. 통계 정보(카디널리티, 선택도, 인덱스 높이)를 기반으로 한 비용 계산이 보이기 시작한다.

복합 인덱스를 추가할 때 **"컬럼 순서가 왜 중요한가"**를 느낌으로 안다. 단순히 "자주 쓰는 순서대로"가 아니라, 선택도 높은 컬럼을 앞으로, 범위 검색 컬럼을 뒤로 배치해야 B+Tree의 힘이 최대화된다는 것을 안다.

인덱스가 "갑자기 느려진" 원인을 **단편화(fragmentation)**나 통계 정보 노후화에서 찾을 수 있다. B+Tree의 split·merge가 누적되면 트리가 느슨해지고, REBUILD나 REORG가 필요해진다.

Primary Key를 설계할 때 **"왜 UUID보다 순차 ID가 쓰기 성능에 유리한가"**를 안다. 클러스터드 인덱스에서 순차 ID는 항상 오른쪽 리프에 추가되지만, UUID는 무작위 위치에 삽입되어 페이지 분할을 자주 일으킨다. 그래서 ULID나 Snowflake ID처럼 시간 순서가 반영된 ID가 선호되는 것이다.

마치며 — 보이지 않는 골격

데이터베이스 엔지니어링의 많은 부분은 추상화의 계층을 어디까지 파고들 것인가의 문제다. ORM 사용자는 테이블만 생각하면 되고, SQL 작성자는 실행 계획까지 보고, 성능 튜너는 인덱스 내부 구조까지 안다. B-Tree는 이 중 가장 깊은 계층에 있다.

매일 쓰는 도구의 내부를 알면 같은 도구로 더 많은 것을 할 수 있다. B-Tree는 단순한 자료구조가 아니라, "디스크 기반 대규모 데이터에서 빠른 탐색과 정렬된 접근을 어떻게 지원할 것인가"라는 근본 질문에 대한 50년 된 답이다. 1970년 Rudolf Bayer와 Edward McCreight가 발표한 이 구조가 지금까지도 거의 모든 관계형 데이터베이스의 심장에 자리잡고 있다는 사실은, 좋은 추상이 얼마나 오래 살아남는지를 보여준다.

백엔드 개발자에게 B-Tree는 보이지 않는 골격이다. 평소에는 의식하지 않지만, 쿼리가 느려지는 순간 그 골격이 존재한다는 것이 드러난다. 그 골격을 이해하고 있으면, 문제 앞에서 패닉하지 않고 정확한 지점을 짚어낼 수 있다. 이게 시니어 개발자와 주니어 개발자를 가르는 지점 중 하나다.