DB 인덱스 — B+Tree부터 복합 인덱스 설계까지
책에서 원하는 내용을 찾는 방법은 두 가지다. 처음부터 한 장씩 넘기거나, 뒤쪽 색인에서 페이지 번호를 찾아 바로 펼치거나. 데이터베이스에서 데이터를 찾는 방법도 똑같다. 인덱스는 책의 색인처럼 데이터의 위치 정보를 미리 정리해둔 자료구조다.
인덱스가 없을 때 vs 있을 때
인덱스가 없는 테이블에서 특정 데이터를 찾으려면 처음부터 끝까지 모든 행을 확인해야 한다. 데이터가 100만 건이면 100만 번 확인한다. 이를 Full Table Scan이라고 한다.
인덱스가 있으면 B+Tree 탐색을 한다. B+Tree는 항상 정렬된 상태를 유지하는 트리 자료구조로, 루트 노드에서 시작해 절반씩 범위를 좁혀 내려간다. 데이터가 100만 건이어도 약 20번의 비교로 원하는 위치에 도달할 수 있다 (O(log n)).
B+Tree — RDBMS가 실제로 쓰는 자료구조
흔히 인덱스를 "B-Tree를 쓴다"고 말하지만, 실제 RDBMS는 B+Tree를 사용한다. B-Tree에서 딱 한 가지가 다르다.
B-Tree는 모든 노드에 실제 데이터가 저장된다. B+Tree는 내부 노드에 탐색 키만 두고, 실제 데이터는 맨 아래 리프 노드에만 저장한다. 그리고 리프 노드끼리 다음 노드의 주소를 가리키는 포인터로 연결되어 있다.
B-Tree:
[10|데이터]
/ \
[5|데이터] [15|데이터]
B+Tree:
[10]
/ \
[5] [15]
↓
[5|데이터] → [10|데이터] → [15|데이터]이 구조가 범위 검색에서 차이를 만든다. BETWEEN 20 AND 30을 조회할 때 B-Tree는 20을 찾은 뒤 21을 찾으러 트리를 다시 올라갔다 내려와야 한다. B+Tree는 20이 있는 리프 노드에 도달한 뒤 포인터를 따라 21, 22... 30까지 순서대로 이동하면 된다. 트리를 재탐색할 필요가 없다.
B+Tree vs Hash Index
인덱스를 저장하는 방식은 B+Tree만 있는 게 아니다.
B+Tree 노드에는 실제 컬럼 값이 정렬된 상태로 저장된다. 정렬된 상태를 유지하기 때문에 아래 쿼리들이 모두 가능하다.
WHERE age = 25 -- 등호 검색
WHERE age BETWEEN 20 AND 30 -- 범위 검색
WHERE name LIKE '김%' -- 앞부분 일치 검색Hash Index는 컬럼 값을 해시 함수로 변환해 버킷에 저장한다. 정확히 같은 값을 찾을 때는 O(1)로 B-Tree보다 빠르지만 범위 검색이 불가능하다. 20의 해시값과 21의 해시값은 완전히 다른 값이라 연속성이 없기 때문이다.
WHERE age = 25 -- Hash: O(1) / B-Tree: O(log n)
WHERE age BETWEEN 20 AND 30 -- Hash: 불가 (Full Scan) / B-Tree: 가능
WHERE name LIKE '김%' -- Hash: 불가 / B-Tree: 가능
WHERE name LIKE '%김' -- Hash: 불가 / B-Tree: 불가 (앞이 와일드카드)LIKE '%김'은 B-Tree도 적용이 안 된다. B-Tree는 앞부분이 고정되어야 탐색 시작점을 찾을 수 있기 때문이다.
인덱스가 있어도 느린 경우
인덱스를 걸었다고 항상 인덱스를 타는 건 아니다.
카디널리티가 낮을 때
카디널리티는 컬럼의 중복도다. 성별(남/여)처럼 값의 종류가 적으면 카디널리티가 낮다.
인덱스로 '남'을 찾으면 전체의 50%가 결과로 나온다. 이 50만 건 각각의 주소로 이동해서 실제 데이터를 가져오는 것보다, 처음부터 끝까지 순서대로 읽는 Full Scan이 더 빠를 수 있다.
디스크는 순서대로 읽는 것(Sequential I/O)이 여기저기 랜덤하게 읽는 것(Random I/O)보다 훨씬 빠르기 때문이다. DB는 통계 정보를 바탕으로 "이 쿼리는 결과가 너무 많이 나오겠다"고 판단하면 자동으로 Full Scan을 선택한다.
컬럼에 함수나 연산을 적용했을 때
WHERE age + 1 = 26 -- 인덱스 X
WHERE YEAR(created_at) = 2024 -- 인덱스 XB+Tree에는 age 원본 값이 정렬된 상태로 저장되어 있다. age + 1 = 26이라고 쓰면 "B+Tree에서 어디서부터 탐색해야 하지?"를 알 수 없다. 모든 행에 연산을 적용해보고 결과가 26인지 확인해야 하니까 Full Scan이 된다.
해결 방법은 연산을 반대편으로 옮기는 것이다. 컬럼 자체는 건드리지 않아야 한다.
WHERE age = 25 -- 인덱스 O
WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31' -- 인덱스 O복합 인덱스
여러 컬럼을 묶어서 하나의 인덱스를 만드는 방식이다.
선두 컬럼 규칙
(city, age)로 복합 인덱스를 걸었을 때 B-Tree 안에는 이렇게 저장된다.
(부산, 20)
(부산, 25)
(서울, 20)
(서울, 25)
(서울, 30)
(대구, 25)city 기준으로 먼저 정렬되고, 그 안에서 age가 정렬된다. age=25인 값은 부산/서울/대구에 흩어져 있어 B-Tree에서 연속된 위치에 없다.
WHERE city = '서울' AND age = 25 -- 인덱스 O
WHERE city = '서울' -- 인덱스 O (선두 컬럼으로만 탐색 가능)
WHERE age = 25 -- 인덱스 X (선두 컬럼 없이는 탐색 불가)복합 인덱스 컬럼 순서 결정 기준
1. 쿼리 패턴 우선
어떤 컬럼이 조건에 자주 등장하는지가 가장 중요하다. WHERE gender = ? 단독 쿼리가 많다면 gender가 선두에 와야 인덱스를 탈 수 있다.
2. 카디널리티
쿼리 패턴이 비슷하다면 카디널리티가 높은 컬럼을 선두에 놓는다. 첫 번째 컬럼에서 많이 걸러낼수록 뒤에서 탐색할 범위가 줄어든다.
(gender, city): gender = '남' → 전체 50% → 그 안에서 city 탐색
(city, gender): city = '서울' → 전체 10% → 그 안에서 gender 탐색
→ city가 선두인 게 첫 단계에서 더 많이 걸러짐Clustered vs Non-Clustered Index
B-Tree 안에서 실제 데이터를 어떻게 저장하느냐의 차이다.
Non-Clustered Index
인덱스 노드에 컬럼 값과 실제 데이터 위치(주소)가 저장된다. 탐색하면 주소를 찾고, 그 주소로 이동해서 실제 데이터를 가져온다.
인덱스 노드: (김철수, 주소: 페이지 5, 슬롯 3)
(김민수, 주소: 페이지 12, 슬롯 7)
...
→ 주소로 이동해서 실제 행 데이터 읽음여러 개 만들 수 있다.
Clustered Index
인덱스 노드에 컬럼 값과 함께 실제 데이터 자체가 저장된다. 인덱스를 찾으면 데이터를 바로 읽을 수 있어 추가 I/O가 없다.
테이블당 1개만 존재할 수 있다. 데이터 자체가 이 순서대로 물리적으로 저장되기 때문이다.
MySQL InnoDB는 PK를 자동으로 Clustered Index로 만든다. PK 순서대로 실제 데이터가 디스크에 배치된다.
UUID vs Auto Increment PK
Clustered Index는 PK 순서대로 데이터를 물리적으로 저장하기 때문에 PK 선택이 성능에 영향을 준다.
Auto Increment
새 데이터가 항상 가장 큰 값이므로 맨 뒤에 붙는다. 디스크에 순서대로 추가되는 순차 쓰기다.
UUID (랜덤 값)
새 데이터의 PK가 기존 값들 사이 어딘가에 위치한다. 이미 저장된 페이지 중간에 끼워 넣어야 하는데, 자리가 없으면 페이지를 둘로 쪼개야 한다. 이를 페이지 분할(Page Split)이라고 한다.
Auto Increment:
[1][2][3][4][5] → 6 추가 → [1][2][3][4][5][6]
UUID:
[3][7][12][15] → 9 추가
→ [3][7] | [9][12][15] (페이지 분할 발생)페이지 분할이 잦으면 디스크 단편화가 생기고 쓰기/읽기 성능이 함께 나빠진다.
DB별 인덱스 자료구조
NoSQL이라고 해서 모두 해시 기반인 건 아니다. 각 DB가 풀려는 문제에 맞는 자료구조를 선택한다.
| DB | 자료구조 | 특징 |
|---|---|---|
| MySQL, PostgreSQL | B-Tree | 범용, 범위 검색 가능 |
| Redis | 해시 | 키-값, O(1) 접근, 범위 검색 불가 |
| MongoDB | B-Tree | 문서 DB, 범위 검색 필요 |
| Cassandra | LSM-Tree | 쓰기 최적화 |
| Elasticsearch | 역인덱스 | 전문(Full-Text) 검색 최적화 |
Redis가 해시를 쓰는 건 캐시/세션 용도로 "정확한 키로 빠르게 꺼내오는 것"이 목적이기 때문이다. 범위 탐색이 필요한 DB들은 B+Tree 계열을 쓴다.
인덱스는 공짜가 아니다
인덱스를 걸면 조회가 빨라지는 대신 쓰기 작업마다 B+Tree를 갱신해야 하는 비용이 생긴다.
INSERT는 새 행뿐만 아니라 인덱스에도 항목을 추가해야 한다. 해당 노드에 자리가 있으면 바로 추가되지만, 노드가 꽉 찬 경우엔 페이지 분할이 발생한다.
DELETE는 실제 데이터는 지워지지만 인덱스에서 즉시 제거하지 않는다. 대신 "사용 불가" 표시만 해두고, 백그라운드의 Purge 스레드가 나중에 실제로 정리한다. 대량 DELETE 직후 인덱스 크기가 줄어들지 않아 보이는 이유다.
UPDATE는 인덱스가 걸린 컬럼이 변경될 때 기존 항목을 사용 불가 처리하고 새 값으로 항목을 다시 추가한다. DELETE + INSERT 비용이 합산된다.
UPDATE users SET name = '김민수' WHERE name = '김철수';
-- '김철수' 인덱스 항목 → 사용 불가 처리
-- '김민수' 인덱스 항목 → 새로 추가저장 공간도 별도로 필요하다. 인덱스는 테이블 크기의 약 10% 정도를 추가로 차지한다.
인덱스는 아래 조건을 고려해서 선택적으로 걸어야 한다. INSERT/UPDATE/DELETE가 잦은 컬럼에 인덱스를 남발하면 쓰기 성능이 오히려 나빠지고, 사용하지 않는 인덱스가 쌓이면 불필요한 공간과 갱신 비용만 계속 발생한다.
- 카디널리티가 높은 컬럼
- WHERE, JOIN, ORDER BY에 자주 등장하는 컬럼
- 쓰기 작업보다 읽기 작업이 훨씬 많은 컬럼
