---
type: Topic
status: living
related_to:
  - acid-innodb
  - memory-hierarchy
---

# 트리와 인덱스 (Tree & Index)

이진 트리가 빠른 이유, B+ tree와 Hash Index의 차이, OLTP/OLAP 워크로드에 따른
인덱스 선택. bomb lab 시크릿 페이즈의 이진 트리에서 출발해 DB 인덱스 원리로 이어진 주제.

## 이진 트리가 빠른 이유, 그리고 한계

정렬된 이진 탐색 트리는 비교 한 번에 탐색 범위를 절반으로 줄여 O(log n)에 값을 찾는다.
다만 균형이 무너지면(한쪽으로 치우친 트리) O(n)으로 퇴화하므로, 실전 자료구조는 균형을
유지하는 변형을 쓴다. 그런데 디스크 기반 DB에서는 이진 트리를 그대로 쓰지 않는다.
노드 하나 읽을 때마다 디스크 I/O가 한 번씩 필요한데, 자식이 2개뿐이면 트리가 너무 깊어
I/O 횟수가 많아지기 때문이다.

## B+ tree

B+ tree는 노드 하나를 디스크 페이지(InnoDB 기준 16KB) 크기에 맞추고 자식을 수백 개씩
두는(높은 fanout) 다진 균형 트리다. 그 결과 수천만 건도 깊이 3~4 수준에서 찾는다.
내부 노드는 길잡이용 키만 갖고 실제 데이터(또는 데이터 위치)는 전부 리프에만 있으며,
리프들이 연결 리스트로 이어져 있어 범위 검색(`BETWEEN`, 부등호)과 정렬 순회에 강하다.
등호 검색, 범위 검색, `ORDER BY`를 모두 지원하는 범용성 덕분에 RDBMS 기본 인덱스다.

## Hash Index

키를 해시 함수에 넣어 버킷 위치를 바로 계산하므로 등호 검색(`=`)은 평균 O(1)로 B+ tree보다
빠르다. 대신 해시값에는 순서가 없어서 범위 검색과 정렬에는 전혀 쓸 수 없다. "정확히 이
키 하나"만 찾는 워크로드(예: key-value 조회)에 맞는 인덱스다.

## OLTP vs OLAP

OLTP(Online Transaction Processing)는 소수 행을 빠르게 읽고 쓰는 트랜잭션 중심
워크로드로, 행 단위 저장 + B+ tree 인덱스 조합이 맞는다(MySQL/InnoDB가 대표).
OLAP(Online Analytical Processing)는 대량 데이터를 스캔·집계하는 분석 워크로드로,
개별 행 인덱스보다 컬럼 지향 저장이 유리하다. 어떤 인덱스가 좋은지는 자료구조 자체가
아니라 워크로드가 결정한다.

## 자주 혼동하는 포인트

- B-tree와 B+ tree의 차이: B-tree는 내부 노드에도 데이터를 두지만, B+ tree는 리프에만
  데이터를 두고 리프를 연결 리스트로 잇는다. 범위 검색에 유리한 쪽은 B+ tree다.
- 해시 인덱스는 등호에만 쓰인다. `<`, `>`, `BETWEEN`, `ORDER BY`, prefix 검색(`LIKE 'a%'`)
  은 못 탄다.
- "트리라서 빠르다"가 아니라 "디스크 I/O 횟수를 줄여서 빠르다"가 핵심이다. 메모리
  계층([[memory-hierarchy]])에서 캐시가 block 단위로 데이터를 옮기듯, DB는 페이지 단위로
  I/O하고 B+ tree는 그 페이지 크기에 노드를 맞춘 자료구조다.

## 관련 문서

- 노트: [[2025-09-21-study-log]]
- 관련 토픽: [[acid-innodb]]