반응형
데이터베이스 — 인덱스 구조 완전 정리
DB 성능을 높이는 가장 강력한 무기는 “인덱스”다.
인덱스를 이해하면 검색 속도, 범위 조회, 조인 성능, 대용량 처리까지 한 번에 잡을 수 있다.
이번 차시는 바로 그 인덱스의 모든 종류와 트리·해싱 구조를 총정리하는 파트다.
1. 인덱스의 개념 — 왜 필요한가?
인덱스는 테이블에 빠르게 접근할 수 있도록 만드는 별도의 자료 구조이다.
쉽게 말하면 책의 목차다.
- 인덱스가 있으면 → 원하는 페이지로 점프
- 인덱스 없으면 → 책을 처음부터 훑어야 함 (Full Scan)
장점
- 검색 속도 대폭 향상
- 정렬된 상태 유지 → 범위 조회 빠름
- 조인 성능 향상
단점
- 인덱스 유지 비용 → 삽입/삭제/갱신 시 오버헤드
- 인덱스 공간 차지
- 인덱스가 너무 많으면 오히려 성능 저하
2. 파일 조직 방법(4가지)
학습 마무리 내용과 동일.
(1) 엔트리 순차 파일
들어오는 순서대로 저장. 정렬 없음.
(2) 키 순차 파일
특정 키 값 기준으로 정렬하며 저장.
(3) 인덱스 파일
키 + 주소로 구성된 인덱스를 이용해 찾아가는 방식.
(4) 직접 파일(Hash File)
해싱 함수를 이용해 바로 주소 계산하여 접근.
3. 인덱스 종류 — 밀집 vs 희소 / 정적 vs 동적
(1) 밀집 인덱스(Dense Index)
- 모든 레코드의 키 값을 가지고 있음
- 빠르다, 하지만 인덱스 크기가 크다
(파일 전체 크기 ≈ 인덱스 크기)
(2) 희소 인덱스(Sparse Index)
- 일부 키만 가지고 있음
- 파일이 정렬되어 있어야 사용 가능
- 인덱스 크기가 작고 효율적
- 검색은 “해당 키보다 작은 가장 큰 인덱스를 찾고 → 이후 순차 검색”
(3) 정적 인덱스
- 인덱스 구조 자체는 변하지 않음
- 공간 부족 시 오버플로우 블록 필요
- 예: ISAM 구조
(4) 동적 인덱스
- 공간이 차면 자동으로 분할(split)
- 남으면 병합(merge)
- 대표: B 트리, B+트리, B*트리
4. B 트리 계열 — DB 인덱스의 핵심
(1) B 트리(B-Tree)
B 트리는 균형을 맞추는 Balanced Tree 개념.
핵심 특징
- 모든 리프 노드는 동일한 레벨
- 한 노드 안의 키는 오름차순 정렬
- 각 노드는 최소 절반 이상 차 있어야 한다
- 삽입 시 공간 부족 → 노드 split
- 삭제 시 공간 부족 → merge 또는 재분배
(B트리는 파일에서 “반 이상 차야 한다, 오름차순 정렬”이라고 명확히 기재)
(2) B* 트리(B-Star Tree)
B 트리의 확장형.
특징
- 각 노드가 최소 2/3 이상 채워져야 함
- split 전에 형제 노드와 먼저 재분배하여 공간 효율 극대화
- 전체 트리가 더 낮아짐 → 검색 속도 증가
(3) B+ 트리(B Plus Tree)
현대 DBMS에서 가장 널리 사용되는 인덱스 구조.
구조
- 인덱스 세트(Index Set)
- 순차 세트(Leaf Set) → 모든 키가 여기에 저장됨
- 리프 노드들이 연결 리스트 형태로 연결 → 범위검색 최강
장점
- 리프에 모든 레코드를 저장하므로 일관된 검색 성능
- 순차 구간 검색에 최적화
- 트리 높이가 낮아짐
5. 비트맵 인덱스(BitMap Index)
특징
- 0/1(비트)로 구성된 인덱스
- 컬럼 값의 종류(카디널리티)가 매우 적을 때 유리
예: 성별, 지역 코드, YES/NO 등 - 대규모 분석용 시스템(DW, OLAP)에 잘 맞음
장점
- AND, OR 연산이 메모리에서 비트 연산으로 즉시 수행 → 압도적 속도
단점
- 값이 자주 바뀌는 트랜잭션 시스템(OLTP)에서는 비효율적
- 비트맵 수정 비용이 큼
6. R 트리(R-Tree) — 공간(Spatial) 데이터를 위한 인덱스
위치·영역·지도 데이터를 위해 만들어진 트리.
특징
- 사각형(MBR, Minimum Bounding Rectangle) 단위로 공간을 묶음
- 겹침(overlap)이 발생할 수 있음
- B 트리 기반의 균형 트리이지만 저장 방식이 공간 특화
확장형
- R 트리
- R* 트리 (성능 개선)
- R+ 트리 (노드 중복 허용, 겹침 최소화)
공간 쿼리(“반경 5km 내의 카페 찾기”)를 빠르게 처리할 수 있는 대표 인덱스다.
7. 해싱(Hashing) — 직접 파일(Direct File)
인덱스를 만들지 않고, 해싱 함수로 바로 주소를 계산해서 접근하는 구조.
(1) 해싱 함수 종류
- 제산법(Division Method)
- 곱셈법(Multiplication Method)
- 중간 제곱(Mid-Square Method)
- Folding(접기)
- 숫자 재배열법 등
(2) 해시 충돌 해결 방법
충돌(Collision) = 서로 다른 키 값이 같은 주소로 매핑된 상황.
1) 개방 주소법(Open Addressing)
- 선형 탐사(Linear Probing)
- 제곱 탐사(Quadratic Probing)
- 이중 해싱(Double Hashing)
2) 분리 연결법(Seperate Chaining)
- 같은 해시 주소가 나오면 연결 리스트 형태로 계속 저장
3) 버킷(Bucket) 방식
- 여러 데이터를 한 칸에 넣는 구조
해싱은 정확히 한 번의 접근으로 데이터를 찾기 때문에 매우 빠르지만,
범위 검색이나 정렬은 불가능하다.
8. 전체 요약 —
- 파일 조직 방법: 엔트리 순차 / 키 순차 / 인덱스 / 직접 파일
- B 트리는 반 이상 차야 하며 오름차순 정렬, 리프는 같은 레벨
- B* 트리는 최소 2/3 채워짐, B+는 인덱스/순차 세트로 구성
- 비트맵 인덱스는 0/1 기반으로 분석용 시스템에 적합
- R 트리는 공간 데이터 인덱스
- 해싱은 주소 계산 방식, 충돌 해결 필수
단어장 — 핵심 개념 암기
인덱스(索引) / index
- 한자: 찾을 索, 끌어낼 引
- 영어 어원: index — 라틴어 indicare(가리키다)
밀집(密集) / dense
- 한자: 빽빽할 密, 모일 集
- 영어 dense — 라틴어 densus(빽빽한)
희소(稀疏) / sparse
- 한자: 드물 稀, 성글 疏
- 영어 sparse — 라틴어 sparsus(흩뿌린)
군형트리(均衡樹) / balanced tree
- 한자: 고를 均, 평형 衡, 나무 樹
- balance — 라틴어 bilanx(두 접시 저울)
비트맵(ㅡ) / bitmap
- bit(binary digit) + map(배치·구조)
공간자료(空間資料) / spatial data
- 한자: 빌 空, 사이 間, 자료 資料
- spatial — 라틴어 spatium(공간)
해싱(ㅡ) / hashing
- hash — 프랑스어 hacher(잘게 자르다) → 조각을 섞는 이미지에서 유래
반응형