인덱스 구조 (B+Tree)
데이터베이스가 빠르게 데이터를 찾는 비밀, B+Tree 인덱스의 구조와 동작 원리를 시각화로 학습합니다.
인덱스 종류
가장 범용적인 인덱스. 정렬된 데이터 저장.
해시 함수 기반. 동등 비교에 최적화.
지리/공간 데이터용. PostGIS와 함께 사용.
인덱스 비교
| 특성 | B+Tree | Hash | GiST |
|---|---|---|---|
| 검색 복잡도 | O(log N) | O(1) | O(log N) |
| 범위 검색 | O | X | O |
| 정렬 | O | X | X |
| 공간 검색 | X | X | O |
| PostgreSQL 기본값 | O | X | X |
B+Tree란?
모든 리프 노드가 같은 깊이에 있습니다. 어떤 데이터를 찾든 동일한 시간이 걸립니다.
리프 노드들이 순서대로 연결되어 있습니다.범위 검색 시 순차적으로 스캔할 수 있습니다.
내부 노드는 탐색용 키만, 실제 데이터는 리프 노드에만 저장됩니다.디스크 I/O를 최소화합니다.
동작 원리
루트에서 시작해 키를 비교하며 자식 노드로 이동합니다. 리프 노드에 도달하면 원하는 데이터를 찾습니다.
적절한 리프를 찾아 키를 삽입합니다. 노드가 가득 차면 분할(Split)하고 중간 키를 부모로 올립니다.
시작 키의 리프 노드를 찾은 후, 연결된 리프 노드를 따라 순차 스캔합니다.
인덱스 실습 (PostgreSQL)
실제 PostgreSQL 데이터베이스에서 인덱스를 직접 다뤄보세요. 데이터를 추가/삭제하면서 B+Tree 구조가 어떻게 변하는지 관찰하고, EXPLAIN ANALYZE로 인덱스 사용 여부를 확인할 수 있습니다.
클러스터링 인덱스 vs 비클러스터링 인덱스
테이블 데이터 자체가 인덱스 순서로 물리적으로 정렬됩니다.
인덱스와 데이터가 분리되어 저장됩니다.
PostgreSQL은 힙 테이블 (Heap Table) 사용
PostgreSQL은 기본적으로 모든 인덱스가 비클러스터링입니다. 데이터는 힙(Heap)에 삽입 순서대로 저장되고, 인덱스는 힙의 위치(TID)를 가리킵니다.CLUSTER 명령으로 한 번 정렬할 수 있지만 유지되지 않습니다.
인덱스 사용 가이드
인덱스 설계 팁
1. 선택도(Selectivity) 확인
중복이 적은 컬럼일수록 인덱스 효율이 높습니다.
SELECT COUNT(DISTINCT col) / COUNT(*) FROM table;2. 복합 인덱스 순서
WHERE 절 조건 순서와 선택도를 고려하세요.
CREATE INDEX idx ON t(a, b, c); -- a 필수3. 커버링 인덱스
SELECT 컬럼이 인덱스에 포함되면 테이블 접근 불필요.
CREATE INDEX idx ON t(a) INCLUDE (b, c);4. EXPLAIN으로 검증
인덱스가 실제로 사용되는지 항상 확인하세요.
EXPLAIN ANALYZE SELECT * FROM t WHERE a = 1;