Ch.11 Binary Search와 B-Tree¶
< 사례 - 매 요청마다 정렬하는 API | 인덱스의 원리 >
앞에서 "인덱스가 있으면 정렬이 필요 없다"고 했다. 왜 그런지 이해하려면 Binary Search부터 시작해야 한다. Binary Search를 디스크에 최적화한 게 B-Tree, 그걸 DB가 쓰는 형태가 B+Tree다.
인덱스가 정렬을 없앤다면, 그 정렬은 어떻게 검색이 되나¶
인덱스가 "이미 정렬된 구조"라는 말의 정체부터 본다. 정렬을 검색으로 바꾸는 가장 기본 알고리즘이 Binary Search다.
사전에서 "Python"이라는 단어를 찾는다고 하자. 1,000페이지짜리 사전을 첫 페이지부터 한 장씩 넘기지 않는다. 중간쯤을 펼쳐서 "P보다 앞이면 왼쪽, 뒤면 오른쪽"을 반복한다.
이게 Binary Search다. 그런데 이 알고리즘에는 두 가지 강한 전제가 있다.
전제 1: 데이터가 정렬되어 있어야 한다¶
"중간값과 비교해서 한쪽을 버린다"는 결정이 의미를 가지려면 데이터가 정렬되어 있어야 한다. 안 그러면 버려진 쪽에 답이 있을 수 있다.
# 정렬 안 된 데이터에 bisect를 쓰면?
data = [5, 2, 9, 1, 7, 3]
import bisect
bisect.bisect_left(data, 3) # 결과 1 (틀린 위치)
# bisect는 데이터가 정렬돼 있다고 '믿고' 동작한다. 검증하지 않는다.
이게 "DB 인덱스는 결국 정렬된 자료구조"라는 말의 출발점이다. 인덱스를 만드는 건 곧 그 컬럼을 정렬해서 따로 보관하는 행위다.
전제 2: 랜덤 접근(Random Access)이 가능해야 한다¶
배열의 i번째 원소를 O(1)로 꺼낼 수 있어야 "중간으로 점프"가 가능하다. 연결 리스트(Linked List)는 i번째에 가려면 i번 순회해야 한다. 그래서 연결 리스트에는 Binary Search를 적용해봤자 O(n)이 된다.
(이게 메모리에서는 자명한데, 디스크에서는 문제가 된다. 디스크의 랜덤 접근은 비싸다. 그래서 B-Tree가 등장한다.)
반씩 줄이면 실제로 얼마나 빨라지나¶
원리는 봤으니 실제로 몇 번 만에 찾는지 세어보자. Python에서 Binary Search를 직접 구현할 일은 거의 없다. 표준 라이브러리 bisect가 다 해준다.
import bisect
sorted_data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# 23을 찾으려면?
# 1단계: 중간값 16과 비교 → 23 > 16 → 오른쪽
# 2단계: 중간값 38과 비교 → 23 < 38 → 왼쪽
# 3단계: 중간값 23과 비교 → 찾았다!
# 값이 들어갈 위치 (왼쪽 기준)
idx = bisect.bisect_left(sorted_data, 23) # → 5
# 값이 있는지 확인하려면 위치를 한 번 더 검증
def contains(arr, target):
i = bisect.bisect_left(arr, target)
return i < len(arr) and arr[i] == target
# 정렬을 유지하면서 삽입
bisect.insort(sorted_data, 20) # → [2, 5, 8, 12, 16, 20, 23, ...]
# 범위 검색: 10 이상 50 이하인 원소들
left = bisect.bisect_left(sorted_data, 10)
right = bisect.bisect_right(sorted_data, 50)
in_range = sorted_data[left:right]
bisect.insort는 정렬을 유지하면서 삽입한다. 다만 리스트에 끼워넣는 비용 자체가 O(n)이라서(뒤 원소를 다 밀어야 함), 자주 삽입하는 데이터에는 안 맞는다. 그럴 땐 트리 기반 자료구조(sortedcontainers.SortedList 같은 외부 라이브러리)나 DB 인덱스를 쓴다.
10개의 데이터에서 3번 만에 찾았다. 100만 개면? 최대 20번이면 된다. log2(1,000,000) ≈ 20이니까.
| 데이터 수 | Linear Search (O(n)) | Binary Search (O(log n)) |
|---|---|---|
| 100 | 100번 | 7번 |
| 10,000 | 10,000번 | 14번 |
| 1,000,000 | 1,000,000번 | 20번 |
| 100,000,000 | 1억 번 | 27번 |
1억 개의 데이터에서 27번 비교면 끝난다. Hash Table의 O(1)에는 못 미치지만, Binary Search는 Hash Table이 못 하는 걸 할 수 있다: 범위 검색.
Binary Search (이진 탐색)
정렬된 데이터에서 절반씩 범위를 줄여가며 찾는 탐색 알고리즘이다. 시간 복잡도 O(log n)이다. 전제 조건은 "데이터가 정렬되어 있어야 한다"와 "랜덤 접근이 가능해야 한다"는 거다. Python에서는 bisect 모듈로 사용한다. DB의 B-Tree 인덱스가 이 원리를 디스크에 최적화해서 확장한 것이다.
O(1)인 Hash Table을 두고 왜 DB는 Binary Search 쪽을 쓰나¶
검색 속도만 보면 Hash Table이 더 빠른데, 사례의 정렬·범위 쿼리는 Hash Table로 풀리지 않는다. 둘이 갈라지는 지점을 짚는다.
| 비교 항목 | Hash Table | Binary Search |
|---|---|---|
| 검색 시간 | O(1) | O(log n) |
| 범위 검색 | 불가능 | 가능 |
| 순서 유지 | 안 함 | 정렬 필요 |
| 정렬 출력 | 불가 (또는 별도 정렬 필요) | 자연스러움 |
| "WHERE price BETWEEN 100 AND 200" | 불가 | 가능 |
| "WHERE email = 'test@test.com'" | 최적 | 가능 |
| 최악의 경우 | O(n) (해시 충돌 심할 때) | O(log n) 보장 |
"같은 값 찾기"에는 Hash Table이 최적이다. "범위로 찾기"에는 Binary Search(정렬된 구조)가 필요하다. DB 인덱스가 Hash Index 대신 B-Tree Index를 기본으로 쓰는 이유가 여기 있다.
(실제 RDBMS도 Hash Index를 옵션으로 제공한다. PostgreSQL의 USING HASH가 그렇다. 그런데 기본은 B-Tree다. 실무 쿼리의 대부분이 범위·정렬을 포함하기 때문이다.)
메모리에서 빠른 Binary Search가 디스크에선 왜 무너지나¶
여기서 막힌다. 사례의 10만 건은 디스크에 있고, 디스크 위에서는 Binary Search의 전제가 그대로 비용으로 돌아온다. Binary Search는 배열에서 잘 동작한다. 문제는 디스크다.
디스크는 한 번에 한 블록(보통 4KB~16KB)을 통째로 읽는다. 배열의 Binary Search는 매 비교마다 멀리 떨어진 위치를 참조하니까 비교 횟수만큼 디스크 I/O가 발생한다. 메모리에서는 27번 비교가 0.001초지만, 디스크에서는 한 번의 랜덤 I/O가 10ms 단위라 27번이면 200ms가 넘는다.
B-Tree는 이 문제를 해결한다. 핵심 아이디어:
- 한 노드에 키를 여러 개 넣어서, 디스크 한 블록 = 트리 한 노드로 만든다.
- 한 번의 I/O로 수십~수백 개의 키와 비교할 수 있다.
- 그래서 트리의 깊이(높이)가 낮아진다. 깊이가 곧 디스크 I/O 횟수다.
[10 | 20 | 30] ← 루트 노드 (1번 읽기)
/ | | \
[3|5|8] [12|15|18] [22|25|28] [35|40|45] ← 중간 노드 (1번 읽기)
/ | \ / | \ / | \ / | \
... ... ... ... ... ... ... ... ← 리프 노드 (1번 읽기)
100만 건이라도 보통 3~4번의 디스크 I/O면 원하는 레코드를 찾을 수 있다. 이게 B-Tree 인덱스의 위력이다.
B-Tree 검색 시간 복잡도 유도¶
한 노드의 키 개수를 b개라고 하자. 각 노드에서 b번 비교하면 하위 b+1개 자식 중 하나로 내려간다.
- 깊이 1: 최대 b+1개 노드
- 깊이 2: 최대 (b+1)^2개 노드
- 깊이 h: 최대 (b+1)^h개 노드
전체 키 개수가 n이면, 트리 깊이는 대략 h = log(b+1)(n)이다. 즉 시간 복잡도는 O(log_b n)이다.
b가 100이면 log_100(1,000,000) = 3, log_100(10억) = 5다. n이 1,000배가 돼도 깊이는 2만 더 깊어진다. 디스크 I/O로 환산하면, 10억 건짜리 테이블에서도 인덱스 검색은 5번의 I/O로 끝난다는 뜻이다.
(메모리상 Binary Search가 O(log_2 n)이라면, B-Tree는 O(log_b n)이다. 밑(base)이 2에서 b로 커진 만큼 깊이가 얕아진다. b는 보통 한 페이지에 들어가는 키 개수로 결정된다.)
그럼 b는 왜 하필 100쯤인가. 노드 하나 = 디스크 페이지 하나(InnoDB 기본 16KB)이고, 거기에 (키 + 자식 포인터)가 몇 개 들어가느냐가 b다. 키가 작을수록 b가 커진다.
b ≈ 페이지 크기 ÷ (키 1개 + 포인터) 크기
INT 키(4B) + 포인터(6B) ≈ 10B → 16KB ÷ 10B ≈ 1,600
VARCHAR(100) 키 ≈ 100B 이상 → 16KB ÷ 100B ≈ 160
여기서 실무 결론이 따라 나온다. 인덱스 컬럼의 타입이 크면 b가 작아지고, b가 작아지면 트리가 깊어진다(= I/O가 늘어난다). "긴 문자열 컬럼에 인덱스를 함부로 걸지 마라", "PK는 짧은 정수로" 같은 조언의 근거가 바로 이 fanout 계산이다.
B-Tree (B-트리)
하나의 노드에 여러 개의 키를 가지는 균형 트리(Balanced Tree)다. 디스크 기반 저장소에 최적화되어 있어서 대부분의 RDBMS가 인덱스 자료구조로 사용한다. MySQL의 InnoDB, PostgreSQL, SQLite 모두 B-Tree(정확히는 B+Tree) 기반 인덱스를 사용한다. 검색, 삽입, 삭제 모두 O(log_b n)이고, 균형이 자동으로 유지되어 최악과 평균 성능이 같다. Ch.14에서 B+Tree와의 차이, 실무 인덱스 설계를 더 자세히 다룬다.
균형 트리 (Balanced Tree)
모든 리프 노드의 깊이가 비슷하게 유지되는 트리다. 한쪽으로 쏠리면 O(n)으로 퇴화하지만, 균형이 유지되면 O(log n)이 보장된다. B-Tree, AVL Tree, Red-Black Tree가 대표적이다. DB는 데이터가 어떻게 들어오든 일관된 성능을 보장해야 하므로 균형 트리가 필수다.
그런데 DB가 실제로 쓰는 건 왜 B-Tree가 아니라 B+Tree인가¶
사례의 "가격순 정렬"과 범위 조회를 떠올리면 한 발 더 들어가야 한다. 실제 RDBMS에서는 B-Tree의 변형인 B+Tree를 쓴다. 차이점:
- B-Tree: 모든 노드(루트, 중간, 리프)에 데이터(또는 레코드 포인터)를 저장한다.
- B+Tree: 리프 노드에만 데이터를 저장하고, 리프 노드끼리 연결 리스트로 연결되어 있다.
| 항목 | B-Tree | B+Tree |
|---|---|---|
| 데이터 위치 | 모든 노드 | 리프 노드만 |
| 리프 노드 연결 | 없음 | 양방향 연결 리스트 |
| 단일 키 검색 | 중간 노드에서 끝날 수 있음 (약간 빠름) | 반드시 리프까지 내려감 |
| 범위 검색 | 트리 순회 필요 (비효율) | 리프 시작점 찾고 연결 리스트 따라감 (효율) |
| 노드당 키 개수 | 적음 (데이터도 저장) | 많음 (중간 노드는 키만 저장) |
| 트리 깊이 | 같은 n에 대해 더 깊음 | 더 얕음 |
| 전체 스캔 | 트리 순회 필요 | 리프 연결 리스트만 순회 |
B+Tree가 B-Tree보다 거의 모든 면에서 DB에 유리하다. 특히 범위 검색과 전체 스캔. 그래서 MySQL InnoDB, PostgreSQL, Oracle, SQL Server 다 B+Tree를 쓴다.
graph TD
subgraph "B+Tree 구조"
R["루트: [10 | 20 | 30]"] --> L1["리프: [3,5,8]"]
R --> L2["리프: [12,15,18]"]
R --> L3["리프: [22,25,28]"]
R --> L4["리프: [35,40,45]"]
L1 -->|"next"| L2
L2 -->|"next"| L3
L3 -->|"next"| L4
end"WHERE price BETWEEN 100 AND 200"이 빠른 이유: price=100인 리프 노드를 O(log_b n)으로 찾고, 거기서 연결 리스트를 따라 price=200까지 순회하면 된다. 트리 탐색은 한 번만 한다.
(B+Tree의 리프 연결 리스트는 페이지 단위 순차 I/O가 되니까, 같은 100건을 읽어도 디스크가 좋아하는 패턴이 된다. 이게 OLTP에서 인덱스 범위 스캔이 빠른 진짜 이유다.)
그런데 "디스크가 순차를 좋아한다"는 건 왜인가. 디스크는 흩어진 위치를 읽는 랜덤 I/O보다 이어진 위치를 읽는 순차 I/O가 훨씬 싸다.
- HDD: 랜덤은 매번 헤드를 옮기고(seek, ~5ms) 회전을 기다린다(rotational latency). 순차는 그 비용을 한 번만 내고 쭉 읽는다. 같은 1MB라도 랜덤(4KB씩 256번 점프)이면 256 × ~5ms ≈ 1초가 넘고, 순차면 수~수십 ms다.
- SSD: 물리적 seek은 없지만 여전히 랜덤이 불리하다. 읽기 단위(페이지·블록) 경계를 걸치는 비용, 큐 깊이, 컨트롤러 오버헤드 때문에 순차 처리량(throughput)이 랜덤 IOPS 환산보다 크다.
그래서 같은 100건이라도 B+Tree 리프를 순차로 훑는 것과 여기저기 흩어진 행을 랜덤으로 점프하는 것은 디스크 입장에서 자릿수가 다른 일이다. 이 차이가 다음 페이지에서 다룰 "인덱스로 찾고 본체를 또 읽는 두 단계가 왜 비싼가", 그리고 "옵티마이저가 인덱스를 두고도 Full Scan을 고르는 경우"의 바탕이 된다.
결국 검색 한 번에 디스크를 몇 번 때리는지로 따져보자¶
깊이 하나가 I/O 하나라는 앞의 설명을 데이터 건수별로 환산하면 인덱스의 위력이 숫자로 드러난다. B+Tree에서 가장 중요한 숫자는 "깊이(높이)"다. 깊이가 곧 검색 1회에 필요한 디스크 I/O 횟수이기 때문이다.
| 데이터 건수 | B+Tree 깊이 (b=100 가정) | 디스크 I/O 횟수 |
|---|---|---|
| 1만 | 2 | 2 |
| 100만 | 3 | 3 |
| 1억 | 5 | 5 |
| 100억 | 6 | 6 |
데이터가 1만 배 늘어도 I/O는 3배만 늘어난다. 이게 인덱스가 "데이터 양에 무딘" 자료구조라는 얘기다. 반대로 인덱스 없는 Full Table Scan은 데이터 양에 정비례(O(n))로 느려진다. 둘의 격차는 데이터가 쌓일수록 벌어진다.
(루트와 자주 쓰이는 중간 노드는 DB 버퍼 풀에 캐시된다. 그래서 실제 I/O는 깊이보다 1~2 적게 일어나는 경우가 많다. 잘 튜닝된 OLTP 환경에서는 인덱스 검색 한 번에 리프 1회 I/O만 발생하기도 한다.)
다음에서 실제 DB 인덱스가 어떻게 동작하는지, EXPLAIN으로 어떻게 확인하는지, 인덱스를 무효화시키는 안티패턴은 뭔지 본다.