1. "DB가 느려요"의 90%는 인덱스 문제
개발 초기, 게시판 목록 조회가 3초나 걸려서 커뮤니티에서 혼난 적이 있습니다.
"야, 너 created_at 컬럼에 인덱스 안 걸었지?"
"네? 그게 뭐죠?"
인덱스(Index)는 책의 '목차'와 같습니다. 목차가 없는 두꺼운 전공 서적에서 "트랜잭션"이라는 단어를 찾으려면 첫 페이지부터 끝까지 다 훑어야 합니다. 이를 DB 용어로는 Full Table Scan이라고 합니다. 전체 데이터를 다 읽어야 하므로 데이터가 많아질수록 속도는 정비례해서 느려집니다(O(N)).
하지만 목차(인덱스)가 있다면, 'ㅌ' 항목으로 가서 순식간에 몇 페이지에 있는지 알 수 있습니다. 이것이 Index Scan입니다. 데이터가 100만 건이 있어도 단 몇 번의 이동만으로 원하는 데이터를 찾을 수 있습니다(O(log N)).
데이터베이스 튜닝의 시작과 끝은 인덱스입니다. 그리고 그 인덱스의 핵심에는 B-Tree (Balanced Tree)라는 자료구조가 숨어 있습니다. 오늘은 왜 수많은 DB가 해시맵(HashMap)이나 이진 탐색 트리(BST) 대신 B-Tree를 선택했는지 깊이 파봤습니다.
2. 왜 하필 B-Tree일까? (ft. 디스크 I/O)
우리는 자료구조 시간에 다양한 트리를 배웁니다.
- BST (Binary Search Tree): 왼쪽은 작게, 오른쪽은 크게. 운 나쁘면 한쪽으로 치우쳐서(Skewed) 리스트처럼 변합니다. 탐색 시간이 O(N)까지 늘어날 수 있습니다.
- Red-Black Tree, AVL Tree: 균형을 맞춰줍니다. O(log N). 메모리 안에서는 아주 훌륭합니다.
하지만 데이터베이스는 디스크(Disk)에 저장됩니다. 디스크 I/O는 메모리 접근보다 10만 배 이상 느립니다. 그래서 DB 성능의 핵심은 CPU 연산 횟수를 줄이는 것이 아니라, "디스크 블록(Page)을 읽는 횟수를 줄이는 것"입니다.
2.1. 페이지(Page)와 블록(Block)
데이터베이스는 데이터를 읽을 때 1바이트씩 읽지 않습니다. 페이지(Page)라고 부르는 단위(보통 16KB)로 뭉텅이로 읽어옵니다. 디스크에서 한 번 읽어오는 비용이 비싸기 때문에, 한 번 갈 때 최대한 많이 가져오는 것이 유리합니다.
2.2. B-Tree의 마법 - "높이를 줄여라"
B-Tree는 자식을 2개가 아니라 수백 개(M개) 가질 수 있는 '뚱뚱한 트리'입니다. 하나의 노드(페이지) 안에 수백 개의 키 데이터를 꽉꽉 채워 넣습니다. 자식이 많다는 건 나무가 옆으로 넓어진다는 뜻이고, 반대로 높이(Height)는 매우 낮아진다는 뜻입니다.
- 이진 트리로 100만 개 데이터를 저장하면 높이가 약 20입니다. 최악의 경우 디스크를 20번 읽어야 합니다.
- B-Tree (차수가 100인 경우)로 100만 개를 저장하면 높이가 3~4면 충분합니다. 디스크를 3번만 읽으면 데이터를 찾을 수 있습니다.
결론: 디스크 접근 횟수를 획기적으로 줄이기 위해 B-Tree를 씁니다.
3. B-Tree vs Hash Index
"해시 테이블(Hash Table)은 검색이 O(1)이니까 더 빠른 거 아닌가요?"
맞습니다. 딱 하나만 찾을 때는 해시가 짱입니다 (WHERE id = 123).
하지만 MySQL을 비롯한 대부분의 RDBMS는 B-Tree를 메인으로 씁니다. 왜일까요?
3.1. 범위 검색 (Range Scan)의 문제
우리는 쿼리를 짤 때 부동항(>, <)을 자주 사용합니다.
SELECT * FROM users WHERE age > 20 AND age < 30;
해시 함수는 입력값이 비슷해도 완전히 다른 해시값을 내놓습니다. 20과 21이 전혀 다른 메모리 주소에 저장됩니다.
즉, 정렬되어 있지 않기 때문에, 20부터 30까지 순서대로 읽을 수가 없습니다.
반면 B-Tree는 데이터가 항상 정렬된 상태를 유지합니다.
그래서 20을 딱 찾은 다음, 거기서부터 오른쪽으로 쭉 읽기만 하면 됩니다(Sequential Access).
대부분의 DB 쿼리는 범위 검색이나 정렬(ORDER BY)을 포함하므로, B-Tree(정확히는 B+Tree)가 압도적으로 유리합니다.
4. 인덱스를 타지 않는 나쁜 쿼리들 (Anti-Patterns)
인덱스를 만들어 뒀다고 해서 DB가 무조건 쓰는 건 아닙니다. 개발자가 쿼리를 잘못 짜면 목차를 무시하고 처음부터 끝까지 다 읽습니다.
-
함수로 가공한 경우 (좌변 가공 금지):
-- Bad (Full Scan): 인덱스 컬럼을 가공하면 인덱스를 못 씁니다. SELECT * FROM users WHERE YEAR(created_at) = 2024; -- Good (Index Scan): 우변을 가공하세요. SELECT * FROM users WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01';인덱스는
created_at원본 값 기준으로 정렬되어 있습니다.YEAR()함수를 씌우면 그 정렬 규칙이 깨지므로 인덱스를 못 씁니다. -
부정 연산자 (
!=,<>): "아닌 것"을 찾으려면 결국 전체를 다 확인해봐야 할 때가 많습니다. 인덱스는 "맞는 것(=)"을 찾는 데 최적화되어 있습니다. 데이터 분포에 따라 다르지만, 보통 풀 스캔을 합니다. -
LIKE '%keyword' (Leading Wildcard): 문자열 인덱스는 앞글자부터 정렬됩니다.
LIKE 'apple%'은 'a'로 시작하는 부분을 찾으면 되지만,LIKE '%apple'은 "apple"로 끝나는 단어를 찾아야 하므로 정렬을 이용할 수 없습니다. 국어사전에서 "로 끝나는 단어"를 찾는 것과 같습니다. -
OR 연산자 사용:
WHERE col1 = A OR col2 = B에서col1에만 인덱스가 있다면, DB는 어차피col2때문에 테이블 전체를 뒤져야 합니다. (MySQL 5.0 이상에서는 Index Merge를 통해 개선되긴 했지만 여전히 비효율적일 수 있습니다).
5. Clustered vs Non-Clustered Index
이 두 용어는 자주 부딪히는 문제이기도 하고, 실제 성능 최적화에 결정적인 영향을 줍니다.
5.1. Clustered Index (클러스터형 인덱스)
- 비유:
영어 사전. - 사전은 내용 자체가 알파벳 순서(인덱스)로 정렬되어 있습니다.
- 데이터(행) 자체가 인덱스 키 순서대로 디스크에 저장됩니다. (= 물리적 정렬)
- 물리적으로 정렬해야 하므로, 테이블당 오직 하나만 존재할 수 있습니다.
- MySQL InnoDB에서는 Primary Key(PK)가 자동으로 클러스터형 인덱스가 됩니다.
- 장점: 검색 속도가 가장 빠릅니다. 특히 범위 검색에 강력합니다.
- 단점: 데이터를 입력/수정할 때마다 물리적인 위치를 조정해야 하므로 쓰기 속도가 느립니다.
5.2. Non-Clustered Index (보조 인덱스)
- 비유:
전공 서적 뒤편의 색인(Index). - 책 내용은 목차 순서(페이지 순서)로 있고, 뒤편에 별도로 "키워드: 페이지번호" 맵이 있습니다.
- 인덱스 리프 노드에는 데이터 자체가 아니라, 데이터가 있는 곳의 주소(PK 값)가 들어있습니다.
- 테이블당 여러 개 만들 수 있습니다.
- 동작: 인덱스 검색 -> PK 획득 -> PK로 클러스터형 인덱스 검색 -> 데이터 획득. (두 번 찾아야 함).
6. 복합 인덱스와 커버링 인덱스 자세히 살펴보기
6.1. 복합 인덱스 (Composite Index)
인덱스는 한 컬럼에만 걸 수 있는 게 아닙니다. (지역, 나이) 처럼 여러 컬럼을 묶을 수 있습니다.
중요한 건 순서입니다.
- 인덱스:
(A, B) - 가능:
WHERE A=1,WHERE A=1 AND B=2 - 불가능:
WHERE B=2(A 없이 B만으로는 정렬되어 있지 않음). 이를 Leftmost Prefix(좌측 접두사) 규칙이라고 합니다.
6.2. 커버링 인덱스 (Covering Index)
쿼리가 요구하는 모든 컬럼이 인덱스 안에 다 포함되어 있는 경우입니다.
-- 인덱스: (user_id, email)
SELECT email FROM users WHERE user_id = 123;
이 쿼리는 실제 데이터 테이블(디스크)까지 갈 필요가 없습니다. 인덱스(목차)만 보고 email을 찾아서 바로 반환할 수 있습니다.
이 경우 Non-Clustered Index의 단점(두 번 찾기)이 사라져 엄청나게 빨라집니다. 쿼리 튜닝의 핵심 기법 중 하나입니다.
7. 실행 계획 확인하기 (EXPLAIN)
내 쿼리가 인덱스를 잘 타는지 확인하려면 EXPLAIN 명령어를 써야 합니다.
EXPLAIN SELECT * FROM users WHERE email = 'ratia@example.com';
- type:
ALL이면 풀 스캔(망함),ref나range,const면 인덱스를 탄 것입니다. - key: 실제로 사용된 인덱스 이름이 나옵니다.
- rows: 쿼리를 수행하기 위해 조사한 행의 수입니다. 작을수록 좋습니다.
8. 마무리 - 인덱스는 공짜가 아니다
인덱스는 마법의 지팡이가 아닙니다. 쓰기 성능을 희생해서 읽기 성능을 높이는 트레이드오프(Trade-off) 기술입니다.
데이터를 INSERT, UPDATE, DELETE 할 때마다 인덱스(목차)도 갱신해야 합니다. B-Tree 균형을 맞추는 작업(Split, Merge)은 꽤 비쌉니다.
그래서 무턱대고 인덱스를 많이 거는 건 "쓰기 속도를 늦추는 지름길"입니다.
꼭 필요한 컬럼에만, 특히 카디널리티(Cardinality, 중복도가 낮은)가 높은 컬럼에 거는 것이 정석입니다.
성별 컬럼처럼 "남/여" 두 가지 값만 있는 경우(중복도가 높음) 인덱스를 걸어도 효과가 거의 없습니다. (어차피 절반을 읽어야 하니까요).