데이터베이스 인덱싱 기술적 원리

서론: 인덱스의 기술적 배경과 I/O 병목 해결

데이터베이스 시스템의 발전 과정은 CPU와 저장 장치(Disk) 간의 처리 속도 차이를 해결하기 위한 과정이다. 중앙 처리 장치(CPU)는 나노초(ns) 단위로 데이터를 처리하지만, 디스크 I/O는 물리적 한계로 인해 밀리초(ms)나 마이크로초(µs) 단위의 지연 시간이 발생한다. 이 ‘I/O Gap’은 시스템 전체 성능의 주요 병목 지점이며, 인덱스(Index)는 이를 보완하는 소프트웨어적 해결책이다.

백엔드 개발자에게 인덱스란 단순한 속도 향상 도구를 넘어, 자료 구조를 활용해 데이터 검색 비용을 선형 시간(O(N))에서 로그 시간(O(log N))으로 줄이는 장치다. 인덱스는 디스크의 최소 읽기 단위인 페이지(Page) 접근을 최소화하도록 설계된 포인터 체계다. 이는 읽기 성능을 높이는 대신, 쓰기 성능 저하와 저장 공간 추가 점유라는 비용을 지불하는 트레이드오프(Trade-off) 관계에 있다.

이에 데이터베이스는 디스크 I/O 효율을 극대화하기 위해 B-Tree 계열의 자료 구조를 핵심적으로 사용한다.

인덱스 자료 구조: B-Tree와 B+Tree

데이터베이스 인덱스는 디스크 I/O 횟수를 줄이기 위해 트리의 높이(Height)를 낮게 유지하는 구조를 사용한다.

B-Tree: 균형 유지 구조

B-Tree는 모든 리프 노드(Leaf Node)가 동일한 깊이를 유지하는 다차원 트리다.

• 특징: 최악의 상황에서도 O(log N)의 탐색 성능을 보장한다. 각 노드는 키(Key)와 실제 데이터 위치(Value/Pointer), 자식 노드 포인터를 모두 가진다.
• 구조적 효율: 분기율(Fan-out)이 높아 대용량 데이터에서도 트리의 깊이가 보통 3~4 레벨로 유지된다. 이는 단 몇 번의 디스크 접근만으로 원하는 데이터를 찾을 수 있음을 의미한다.
• 제약: 내부 노드에 데이터까지 저장하므로, 고정된 페이지 크기 내에 저장할 수 있는 키의 개수가 적다. 이는 트리의 높이를 높이는 원인이 된다.

B+Tree: 디스크 최적화 구조

대부분의 현대 DBMS는 B-Tree를 개선한 B+Tree를 사용한다.

• 데이터 저장 위치 최적화: 루트와 내부 노드에는 키와 포인터만 저장하고, 실제 데이터(또는 데이터 포인터)는 리프 노드에만 저장한다. 이로 인해 한 페이지에 더 많은 키를 담을 수 있어 분기율이 높아지고 트리의 높이는 낮아진다.
• 리프 노드 연결(Linked List): 모든 리프 노드가 연결 리스트로 이어져 있다. 범위 검색 시 트리를 다시 올라갔다 내려올 필요 없이, 시작점에서 리프 노드를 따라 순차적으로 읽기(Sequential Scan)만 하면 되므로 범위 쿼리 성능이 우수하다.

B+Tree가 인덱스의 표준으로 자리 잡았으나, 실제 엔진 레벨에서의 구현은 상이하다. MySQL과 PostgreSQL은 이 자료 구조를 각기 다른 아키텍처 방식으로 해석하여 적용하고 있다.

DBMS 아키텍처별 인덱스 구현

MySQL InnoDB: 클러스터드 인덱스 아키텍처

InnoDB는 데이터와 인덱스가 결합된 Index-Organized Table(IOT) 구조다.

• 클러스터드 인덱스: 테이블당 1개(주로 PK)만 존재하며, 리프 노드에 실제 행(Row) 데이터가 직접 저장된다. PK 기반 검색과 범위 검색에 매우 빠르다.
• 세컨더리 인덱스: PK 이외의 인덱스다. 리프 노드에 실제 데이터 주소 대신 PK 값을 저장한다.
• 이중 조회(Double Look-up): 세컨더리 인덱스로 검색 시, PK를 먼저 찾고 다시 PK 인덱스를 탐색하여 데이터를 가져온다.

PostgreSQL: 힙(Heap) 테이블 아키텍처

데이터 파일과 인덱스 파일을 독립적으로 관리한다.

• TID(Tuple Identifier): 데이터는 정렬되지 않은 힙 영역에 저장되며, 각 행은 물리적 위치 정보인 TID를 가진다.
• 인덱스 구조: 모든 인덱스는 리프 노드에 TID를 저장한다.
• 데이터 접근: 인덱스에서 TID를 얻으면 힙 페이지에 직접 접근한다. 이중 조회가 없어 단건 조회에 효율적일 수 있으나, 데이터 업데이트 시 위치가 변하면 관련 인덱스를 모두 갱신해야 하는 부담이 있다.

각 DBMS의 아키텍처 특성을 파악했다면, 다음으로 이를 활용해 쿼리 성능을 극대화할 수 있는 인덱스 설계 전략을 수립해야 한다.

인덱스 설계 및 최적화 전략

복합 인덱스와 최좌측 접두사(Leftmost Prefix)

(A, B, C) 순서의 인덱스는 A를 기준으로 먼저 정렬된 후 B, C 순으로 정렬된다. 따라서 WHERE 절에 A 조건이 없으면 인덱스를 정상적으로 활용할 수 없다.

커버링 인덱스(Covering Index)

쿼리에 필요한 모든 컬럼이 인덱스 자체에 포함된 경우다. 실제 테이블 데이터를 읽으러 갈 필요가 없으므로 I/O 비용이 대폭 감소한다.

카디널리티와 선택도

• 선택도: 전체 중 특정 조건이 걸러내는 비율(10~15% 이하 권장).
• 카디널리티: 고유한 값의 개수. 중복도가 낮은(카디널리티가 높은) 컬럼일수록 인덱스 효율이 극대화된다.

인덱스는 읽기 성능을 보장하는 대신, 데이터 변경 시에는 필연적으로 쓰기 오버헤드가 발생한다. 이러한 트레이드오프를 관리하기 위해 내부적으로 다양한 쓰기 최적화 메커니즘이 동작한다.

쓰기 부하와 내부 메커니즘

페이지 분할(Page Splitting)

무작위 UUID(v4)처럼 정렬되지 않은 값을 PK로 삽입하면, B+Tree 중간에 데이터를 끼워 넣어야 한다. 이때 페이지 공간이 부족하면 페이지를 나누는 ‘페이지 분할’이 발생하며, 이는 디스크 쓰기 부하와 인덱스 파편화를 유발한다. (UUID v7 등 정렬 가능한 키 권장)

최적화 기술 (Change Buffer & HOT)

• Change Buffer (MySQL): 쓰기 작업 시 인덱스 페이지를 즉시 업데이트하지 않고 메모리에 임시 기록하여 디스크 랜덤 쓰기를 줄인다.
• HOT (PostgreSQL): 인덱스 컬럼이 수정되지 않는 업데이트의 경우, 인덱스 변경 없이 힙 페이지 내에서만 데이터를 관리하여 쓰기 증폭을 억제한다.

설계한 인덱스와 최적화 기법이 의도대로 동작하는지는 데이터베이스의 실행 계획(Explain)을 분석하여 객관적으로 검증할 수 있다.

실행 계획(Explain) 분석 지표

MySQL 지표

• type: const, ref, range 순으로 효율적이며, ALL(Full Scan)은 개선이 필요하다.
• Extra: Using filesort나 Using temporary는 메모리/디스크 추가 부하를 의미하므로 주의해야 한다.

PostgreSQL 지표

• Buffers: shared hit을 통해 메모리 캐시 활용도를, read를 통해 물리 디스크 접근량을 파악한다.
• Scan Types: Index Scan, Bitmap Index Scan 등의 방식을 확인한다.

결론

인덱스는 데이터베이스의 I/O 비용을 관리하기 위한 핵심적인 공학적 도구다. B+Tree 구조를 바탕으로 각 DBMS가 채택한 아키텍처(Clustered vs Heap)를 이해하면 더욱 정교한 성능 튜닝이 가능하다. 백엔드 개발자는 데이터의 분포와 쿼리 패턴을 분석하여 효율적인 인덱스를 설계하고, 정기적으로 실행 계획을 점검하여 시스템 성능을 유지해야 한다.