1. 프롤로그 - "왜 내 쿼리는 2.5초나 걸릴까?"
제 첫 프로젝트에서 100만 건의 주문 데이터를 다루게 됐을 때의 일입니다.
로컬 개발 환경(데이터 1,000건)에서는 0.005초면 나오던 쿼리가, 운영 서버(데이터 100만 건)에서는 2.5초나 걸렸습니다.
500배 느려진 겁니다.
급히 인덱스를 추가했습니다.
CREATE INDEX idx_user_id ON orders(user_id);
결과는 0.003초. 마법처럼 빨라졌습니다.
도대체 CREATE INDEX는 무슨 짓을 한 걸까요?
그 뒤에는 B-Tree라는 자료구조가 숨어있었습니다.
2. 왜 DB는 배열이나 리스트를 안 쓸까?
데이터베이스를 만드는 개발자라고 상상해보세요. 데이터 1억 개를 저장해야 합니다.
- 배열(Array): 조회는 빠르지만(
O(1)?), 데이터 중간에 하나 넣으려면 1억 개를 뒤로 밀어야 합니다. (O(N)). 쓰기 성능 꽝입니다. - 연결 리스트(Linked List): 넣는 건 빠르지만, 찾으려면 1억 개를 처음부터 훑어야 합니다. (
O(N)). 읽기 성능 꽝입니다. - 이진 탐색 트리(BST/AVL/Red-Black): 오!
O(log N)이라 빠르네요? 하지만 치명적인 문제가 있습니다. 바로 "디스크(Disk)"의 물리적 특성입니다.
3. 메모리(RAM)와 디스크(HDD/SSD)의 거대한 장벽
이진 트리는 메모리에서는 효율적입니다. 포인터(주소)만 따라가면 되니까요. 하지만 디스크에서는 최악입니다.
물리적 현실
- RAM 접근: 약 100나노초 (0.0000001초)
- HDD 탐색: 약 10밀리초 (0.01초)
- 차이: 10만 배.
비유하자면, 메모리에서 데이터 찾는 게 "책상 위 노트 집기"라면, 디스크에서 찾는 건 "부산 도서관까지 걸어가서 책 찾기"입니다. 이진 트리는 높이가 높습니다(High Height). 노드 하나 찾을 때마다 부산을 왔다 갔다 해야 한다면? 쿼리 하나에 몇 분이 걸릴 겁니다.
그래서 우리는 "부산에 한 번 갔을 때, 트럭으로 책을 왕창 실어오자"고 결심합니다. 이것이 B-Tree의 핵심 철학입니다.
4. B-Tree: 뚱뚱하고 낮은 트리
B-Tree의 전략은 "높이(Height)를 줄이고 옆으로(Width) 퍼지자"입니다. 이진 트리는 자식이 2명이지만, B-Tree는 자식을 수천 명 가질 수 있습니다. (이것을 차수(Order) 또는 Fan-out이라고 합니다.)
마법 같은 숫자
노드 하나 크기를 디스크 블록 크기(보통 4KB 또는 16KB)에 딱 맞춥니다. 이 16KB 노드 하나에 데이터(키)를 수백 개 꽉꽉 채워 넣습니다. 그러면 트리의 높이가 기적적으로 낮아집니다.
- 데이터: 1억 개
- 이진 트리 높이: 약 27층 (디스크 I/O 27번 발생 -> 0.27초 소요)
- B-Tree 높이(차수 1000): 단 3층 ($1000^3 = 10억$). (디스크 I/O 3번 발생 -> 0.03초 소요)
결론: 압도적으로 빠릅니다. DB가 B-Tree를 쓰는 이유는 단 하나, Disk I/O 횟수를 줄이기 위해서입니다.
5. B-Tree vs B+Tree (핵심 차이)
사실 현대의 DB(MySQL InnoDB, Oracle)는 순수 B-Tree가 아니라 B+Tree를 씁니다. 이 미묘하지만 결정적인 차이를 알아야 "DB 좀 아네?" 소리를 듣습니다.
차이점 1 - 데이터는 어디에?
- B-Tree: 모든 노드(뿌리, 가지, 잎)에 실제 데이터(Value)를 함께 저장합니다.
- B+Tree: 오직 리프 노드(말단)에만 데이터를 저장합니다. 위쪽(브랜치) 노드들은 오직 "표지판(Key)" 역할만 합니다.
- 효과: 브랜치 노드가 가벼워집니다. 한 번에 더 많은 표지판을 메모리에 올릴 수 있습니다. (Cache Hit 증가).
차이점 2 - 범위 검색 (Range Scan)
- B-Tree: "20대에서 30대 유저 찾아줘"라고 하면, 트리를 오르락내리락(In-order Traversal)하며 비효율적으로 움직여야 합니다.
- B+Tree: 리프 노드끼리 Linked List로 연결되어 있습니다.
SELECT * FROM users WHERE age BETWEEN 20 AND 30- 20을 찾은 뒤(O(logN)), 그냥 옆으로(Linked List) 쭉 달리면 됩니다(O(K)). 범위 검색의 최강자입니다.
6. 클러스터드 인덱스 vs 논-클러스터드 인덱스
개발자가 꼭 알아야 할 실제 지식입니다.
1) 클러스터드 인덱스 (Clustered Index)
- 보통 Primary Key (PK)가 이 역할을 합니다.
- 특징: 실제 데이터 행(Row) 자체가 인덱스 순서대로 물리적으로 정렬되어 저장됩니다.
- 비유: 영어 사전. (
Apple다음에 바로Apricot내용이 나옴). - 성능: 범위 검색 시 끝판왕입니다. 디스크 헤드가 그냥 쭉 긁으면 되니까요.
- 단점: 테이블당 딱 1개만 만들 수 있습니다. (물리적 정렬은 하나밖에 못 하니까).
2) 논-클러스터드 인덱스 (Non-Clustered / Secondary Index)
- 우리가
CREATE INDEX로 만드는 일반 인덱스입니다. - 특징: 인덱스 페이지가 따로 존재하며, 리프 노드에는 "실제 데이터 주소(또는 PK)"가 들어있습니다.
- 비유: 책 뒤의 "찾아보기(색인)". ("단어: 124페이지"라고 적혀있음).
- 과정: 인덱스에서 찾음 -> 거기 적힌 주소(PK)를 보고 다시 클러스터드 인덱스를 뒤짐 (Look up). 두 번 일을 해야 합니다.
Tip: 그래서 커버링 인덱스(Covering Index)를 쓰면 성능이 좋아집니다. (인덱스 안에 필요한 데이터가 다 들어있어서, 실제 테이블을 안 뒤져도 되는 상태).
7. 경쟁자 - LSM Tree (Write가 압도적으로 많다면?)
B-Tree는 완벽해 보이지만, 쓰기(Write) 성능은 그저 그렇습니다. 데이터를 넣을 때마다 빈 공간 찾고, 정렬 유지하고, 노드 쪼개고(Split)... 디스크 헤드가 춤을 춥니다(Random I/O).
만약 카카오톡 로그나 주식 거래 내역처럼 엄청난 속도로 쌓이는 데이터라면? 이때는 LSM Tree (Log Structured Merge Tree)를 씁니다. (Cassandra, HBase, Kafka 등 NoSQL들이 사용).
- 원리: 일단 메모리에 씁니다. 메모리가 차면 디스크에 순차적으로(Sequential) 들이붓습니다. 정렬은 나중에 합병(Merge)하면서 맞춥니다.
- 장점: 쓰기 속도가 압도적입니다.
- 단점: 읽기 속도는 B-Tree보다 느립니다.
결론:
- 읽기/쓰기 밸런스가 중요하다 (RDBMS) -> B+Tree
- 쓰기가 압도적으로 중요하다 (Log, NoSQL) -> LSM Tree
8. 하드디스크의 물리적 한계와 WAL 제대로 파보기
왜 B-Tree가 이렇게까지 처절하게 디스크 I/O를 줄이려고 노력할까요? 디스크의 물리적 구조를 뜯어보면 눈물이 날 지경이기 때문입니다.
1) 회전 지연과 탐색 시간 (Rotational Latency & Seek Time)
하드디스크(HDD)는 LP판처럼 생긴 플래터(Platter)가 고속으로 회전하고, 헤드(Head)가 움직이며 데이터를 읽습니다.
- 탐색 시간(Seek Time): 헤드가 원하는 트랙(Track) 위치로 이동하는 시간. (물리적으로 팔이 움직여야 함).
- 회전 지연(Rotational Latency): 헤드는 도착했는데, 원하는 데이터가 내 발밑으로 돌아올 때까지 기다리는 시간.
이 두 가지 물리적 시간 때문에 랜덤 I/O는 끔찍하게 느립니다. B-Tree는 데이터를 한 페이지(Page, 16KB)에 몰아넣음으로써, 한 번 헤드가 움직였을 때 최대한 많은 정보를 긁어오게 설계된 것입니다.
2) WAL (Write Ahead Log)의 존재 이유
DB에 데이터를 INSERT 할 때, B-Tree의 구조를 바꾸는 건(노드 분할, 밸런싱) 시간이 걸립니다.
그렇다고 디스크에 쓸 때까지 기다리면 사용자가 답답해합니다.
그래서 DB는 꼼수를 씁니다.
- 일단 WAL(로그 파일)이라는 곳에 "나 이거 썼음!" 하고 순차적으로 기록만 합니다. (Append Only). 순차 쓰기라서 엄청 빠릅니다.
- 사용자에게는 "저장 완료!"라고 뻥을 칩니다.
- 실제 B-Tree 정리는 나중에 백그라운드에서 천천히 합니다. (Checkpoint). 만약 이때 전기가 나가면? 재부팅 할 때 WAL을 보고 복구하면 됩니다. 이 WAL 구조조차도 디스크의 랜덤 쓰기(Random Write)를 피하고 순차 쓰기(Sequential Write)를 하려는 눈물겨운 노력입니다.
3) SSD는 좀 낫지 않나요?
SSD는 모터가 없어서 탐색 시간이 없습니다. 그래서 HDD보다 랜덤 액세스가 훨씬 빠릅니다. 하지만 그럼에도 불구하고 RAM보다는 1,000배 느립니다. 그리고 SSD도 내부적으로 페이지(Page) 단위로 읽고 씁니다. 즉, 1바이트만 고치고 싶어도 4KB 전체를 썼다가 지워야 합니다. (이것을 Write Amplification이라고 합니다). 그래서 B-Tree처럼 데이터를 뭉쳐서 관리하는 전략은 SSD 시대에도 여전히, 아니 더욱 중요합니다.
9. 개발자가 자주 하는 실수: Leftmost Prefix Rule
B-Tree 인덱스를 만들었는데도 DB가 느리다면? 90%는 이 규칙을 몰라서입니다. B-Tree는 데이터를 "사전순"으로 정렬합니다.
1) 인덱스 컬럼 순서의 중요성
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)을 조건절에 넣지 않으면 인덱스는 무용지물입니다.
2) LIKE 검색의 함정
WHERE name LIKE 'Kim%'-> 인덱스 탐 (O) ("Kim"으로 시작하는 건 정렬되어 있으니까)WHERE name LIKE '%Kim'-> 인덱스 안 탐 (X) ("Kim"으로 끝나는 건 정렬과 상관없음)
검색엔진처럼 중간에 있는 단어를 찾고 싶다면 B-Tree로는 불가능합니다. 이때는 Elasticsearch 같은 역색인(Inverted Index) 기반 검색 엔진을 도입해야 합니다. 모든 도구에는 용도가 있는 법이니까요.
10. 분산 시스템에서의 인덱스 (Sharding)
데이터가 100억 개가 넘어가면 샤딩(Sharding)을 해야 합니다. 이때 B-Tree는 어떻게 될까요? 서버 10대에 데이터를 쪼개 넣으면, 인덱스도 10개로 쪼개집니다. (Local Index).
문제는 "전체 정렬"이 깨진다는 것입니다.
ORDER BY created_at을 하려면?
10대 서버에서 각각 정렬된 데이터를 가져와서, 애플리케이션 서버가 다시 합병 정렬(Merge Sort)을 해야 합니다. (Scatter-Gather).
이 과정이 너무 느리기 때문에, 대규모 분산 시스템에서는 조인(Join)과 정렬(Sort)을 최대한 배제하는 데이터 모델링을 합니다.
B-Tree의 한계를 넘어서는 순간, 당신은 시스템 아키텍트의 영역에 진입한 것입니다.
11. 최신 최적화 기법 - 인덱스 컨디션 푸시다운 (ICP)
MySQL 5.6부터 도입된 ICP (Index Condition Pushdown)라는 기법이 있습니다. 과거에는 인덱스에서 조건이 맞지 않으면 무조건 테이블로 가서 데이터를 가져온 후 검사를 했습니다. 하지만 ICP는 "인덱스에 있는 정보만으로도 안 된다는 걸 알 수 있다면, 굳이 테이블까지 가지 말자"는 최적화입니다.
예를 들어, ZIP_CODE LIKE '%99' (뒷자리 검색) 같은 조건은 인덱스 정렬을 쓸 수는 없지만,
인덱스 안에 ZIP_CODE 값이 저장되어 있으므로 "이 데이터는 99로 안 끝나네?"라고 판단하고 버릴 수 있습니다.
이로 인해 불필요한 디스크 읽기(Random I/O)를 획기적으로 줄일 수 있습니다.
DB 엔진은 지금도 계속 똑똑해지고 있습니다.
12. 요약 - DB 성능의 척추
- B-Tree: 디스크 I/O를 줄이기 위해 키를 낮추고 옆으로 퍼진 트리.
- B+Tree: 리프 노드에만 데이터를 담고 서로 연결해서 범위 검색을 최적화함. (거의 모든 RDBMS 표준).
- 인덱스 원리: 책 뒤의 색인과 같다. 없으면 전수 조사(Full Scan), 있으면 이진 탐색 수준(Index Seek).
- ** 트레이드오프**: 인덱스는 공짜 점심이 아니다. 조회는 빨라지지만, 삽입/수정/삭제는 느려진다. (색인도 고쳐야 하니까).