#CS#DataStructure#Tree#Database#BTree#Index
B-Tree: 디스크를 위한 뚱뚱한 트리 (DB 인덱스 원리)
이진 트리는 메모리용입니다. 디스크(SSD/HDD)는 느리니까 트리 키를 낮추고 옆으로 뚱뚱하게 만들어서 디스크 I/O 횟수를 최소화했습니다. B-Tree vs B+Tree 차이와 MySQL 인덱스의 비밀.
2025년 4월 18일
Codemapo
이진 트리는 메모리용입니다. 디스크(SSD/HDD)는 느리니까 트리 키를 낮추고 옆으로 뚱뚱하게 만들어서 디스크 I/O 횟수를 최소화했습니다. B-Tree vs B+Tree 차이와 MySQL 인덱스의 비밀.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.
미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?
이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?
매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.
제 첫 프로젝트에서 100만 건의 주문 데이터를 다루게 됐을 때의 일입니다.
로컬 개발 환경(데이터 1,000건)에서는 0.005초면 나오던 쿼리가, 운영 서버(데이터 100만 건)에서는 2.5초나 걸렸습니다.
500배 느려진 겁니다.
급히 인덱스를 추가했습니다.
CREATE INDEX idx_user_id ON orders(user_id);
결과는 0.003초. 마법처럼 빨라졌습니다.
도대체 CREATE INDEX는 무슨 짓을 한 걸까요?
그 뒤에는 B-Tree라는 자료구조가 숨어있었습니다.
데이터베이스를 만드는 개발자라고 상상해보세요. 데이터 1억 개를 저장해야 합니다.
O(1)?), 데이터 중간에 하나 넣으려면 1억 개를 뒤로 밀어야 합니다. (O(N)). 쓰기 성능 꽝입니다.O(N)). 읽기 성능 꽝입니다.O(log N)이라 빠르네요? 하지만 치명적인 문제가 있습니다. 바로 "디스크(Disk)"의 물리적 특성입니다.이진 트리는 메모리에서는 효율적입니다. 포인터(주소)만 따라가면 되니까요. 하지만 디스크에서는 최악입니다.
비유하자면, 메모리에서 데이터 찾는 게 "책상 위 노트 집기"라면, 디스크에서 찾는 건 "부산 도서관까지 걸어가서 책 찾기"입니다. 이진 트리는 높이가 높습니다(High Height). 노드 하나 찾을 때마다 부산을 왔다 갔다 해야 한다면? 쿼리 하나에 몇 분이 걸릴 겁니다.
그래서 우리는 "부산에 한 번 갔을 때, 트럭으로 책을 왕창 실어오자"고 결심합니다. 이것이 B-Tree의 핵심 철학입니다.
B-Tree의 전략은 "높이(Height)를 줄이고 옆으로(Width) 퍼지자"입니다. 이진 트리는 자식이 2명이지만, B-Tree는 자식을 수천 명 가질 수 있습니다. (이것을 차수(Order) 또는 Fan-out이라고 합니다.)
노드 하나 크기를 디스크 블록 크기(보통 4KB 또는 16KB)에 딱 맞춥니다. 이 16KB 노드 하나에 데이터(키)를 수백 개 꽉꽉 채워 넣습니다. 그러면 트리의 높이가 기적적으로 낮아집니다.
결론: 압도적으로 빠릅니다. DB가 B-Tree를 쓰는 이유는 단 하나, Disk I/O 횟수를 줄이기 위해서입니다.
사실 현대의 DB(MySQL InnoDB, Oracle)는 순수 B-Tree가 아니라 B+Tree를 씁니다. 이 미묘하지만 결정적인 차이를 알아야 "DB 좀 아네?" 소리를 듣습니다.
SELECT * FROM users WHERE age BETWEEN 20 AND 30개발자가 꼭 알아야 할 실제 지식입니다.
Apple 다음에 바로 Apricot 내용이 나옴).CREATE INDEX로 만드는 일반 인덱스입니다.Tip: 그래서 커버링 인덱스(Covering Index)를 쓰면 성능이 좋아집니다. (인덱스 안에 필요한 데이터가 다 들어있어서, 실제 테이블을 안 뒤져도 되는 상태).
B-Tree는 완벽해 보이지만, 쓰기(Write) 성능은 그저 그렇습니다. 데이터를 넣을 때마다 빈 공간 찾고, 정렬 유지하고, 노드 쪼개고(Split)... 디스크 헤드가 춤을 춥니다(Random I/O).
만약 카카오톡 로그나 주식 거래 내역처럼 엄청난 속도로 쌓이는 데이터라면? 이때는 LSM Tree (Log Structured Merge Tree)를 씁니다. (Cassandra, HBase, Kafka 등 NoSQL들이 사용).
결론:
왜 B-Tree가 이렇게까지 처절하게 디스크 I/O를 줄이려고 노력할까요? 디스크의 물리적 구조를 뜯어보면 눈물이 날 지경이기 때문입니다.
하드디스크(HDD)는 LP판처럼 생긴 플래터(Platter)가 고속으로 회전하고, 헤드(Head)가 움직이며 데이터를 읽습니다.
이 두 가지 물리적 시간 때문에 랜덤 I/O는 끔찍하게 느립니다. B-Tree는 데이터를 한 페이지(Page, 16KB)에 몰아넣음으로써, 한 번 헤드가 움직였을 때 최대한 많은 정보를 긁어오게 설계된 것입니다.
DB에 데이터를 INSERT 할 때, B-Tree의 구조를 바꾸는 건(노드 분할, 밸런싱) 시간이 걸립니다.
그렇다고 디스크에 쓸 때까지 기다리면 사용자가 답답해합니다.
그래서 DB는 꼼수를 씁니다.
SSD는 모터가 없어서 탐색 시간이 없습니다. 그래서 HDD보다 랜덤 액세스가 훨씬 빠릅니다. 하지만 그럼에도 불구하고 RAM보다는 1,000배 느립니다. 그리고 SSD도 내부적으로 페이지(Page) 단위로 읽고 씁니다. 즉, 1바이트만 고치고 싶어도 4KB 전체를 썼다가 지워야 합니다. (이것을 Write Amplification이라고 합니다). 그래서 B-Tree처럼 데이터를 뭉쳐서 관리하는 전략은 SSD 시대에도 여전히, 아니 더욱 중요합니다.
B-Tree 인덱스를 만들었는데도 DB가 느리다면? 90%는 이 규칙을 몰라서입니다. B-Tree는 데이터를 "사전순"으로 정렬합니다.
CREATE INDEX idx_name_age ON users(name, age)라고 복합 인덱스를 만들었습니다.
이것은 "이름으로 먼저 정렬하고, 이름이 같으면 나이로 정렬하라"는 뜻입니다.
SELECT * FROM users WHERE name = 'Alice' -> 인덱스 탐 (O)SELECT * FROM users WHERE name = 'Alice' AND age = 20 -> 인덱스 탐 (O)SELECT * FROM users WHERE age = 20 -> 인덱스 안 탐 (X) (Full Scan)왜 age만 검색하면 인덱스를 못 탈까요?
사전에서 "두 번째 글자가 'B'인 단어"를 찾을 수 있나요? 못 찾습니다. 첫 번째 글자부터 찾아야 순서가 의미가 있죠.
B-Tree도 똑같습니다. 인덱스의 첫 번째 컬럼(Leftmost)을 조건절에 넣지 않으면 인덱스는 무용지물입니다.
WHERE name LIKE 'Kim%' -> 인덱스 탐 (O) ("Kim"으로 시작하는 건 정렬되어 있으니까)WHERE name LIKE '%Kim' -> 인덱스 안 탐 (X) ("Kim"으로 끝나는 건 정렬과 상관없음)검색엔진처럼 중간에 있는 단어를 찾고 싶다면 B-Tree로는 불가능합니다. 이때는 Elasticsearch 같은 역색인(Inverted Index) 기반 검색 엔진을 도입해야 합니다. 모든 도구에는 용도가 있는 법이니까요.
데이터가 100억 개가 넘어가면 샤딩(Sharding)을 해야 합니다. 이때 B-Tree는 어떻게 될까요? 서버 10대에 데이터를 쪼개 넣으면, 인덱스도 10개로 쪼개집니다. (Local Index).
문제는 "전체 정렬"이 깨진다는 것입니다.
ORDER BY created_at을 하려면?
10대 서버에서 각각 정렬된 데이터를 가져와서, 애플리케이션 서버가 다시 합병 정렬(Merge Sort)을 해야 합니다. (Scatter-Gather).
이 과정이 너무 느리기 때문에, 대규모 분산 시스템에서는 조인(Join)과 정렬(Sort)을 최대한 배제하는 데이터 모델링을 합니다.
B-Tree의 한계를 넘어서는 순간, 당신은 시스템 아키텍트의 영역에 진입한 것입니다.
MySQL 5.6부터 도입된 ICP (Index Condition Pushdown)라는 기법이 있습니다. 과거에는 인덱스에서 조건이 맞지 않으면 무조건 테이블로 가서 데이터를 가져온 후 검사를 했습니다. 하지만 ICP는 "인덱스에 있는 정보만으로도 안 된다는 걸 알 수 있다면, 굳이 테이블까지 가지 말자"는 최적화입니다.
예를 들어, ZIP_CODE LIKE '%99' (뒷자리 검색) 같은 조건은 인덱스 정렬을 쓸 수는 없지만,
인덱스 안에 ZIP_CODE 값이 저장되어 있으므로 "이 데이터는 99로 안 끝나네?"라고 판단하고 버릴 수 있습니다.
이로 인해 불필요한 디스크 읽기(Random I/O)를 획기적으로 줄일 수 있습니다.
DB 엔진은 지금도 계속 똑똑해지고 있습니다.