All
인덱스의 개념
인덱스의 필요성
•
대량의 데이터에서 원하는 값을 빠르게 찾기 위해
•
모든 데이터를 처음부터 끝까지 순차 탐색하면 매우 비효율적
•
인덱스(index) 는 데이터를 빠르게 찾을 수 있도록 도와주는 부가적인 구조
인덱스의 정의
•
인덱스: 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 탐색키 + 포인터 구조
•
인덱싱(indexing): 인덱스를 구성하는 작업
인덱스 종류
순서 인덱스 (Ordered Index)
•
탐색키를 정렬된 순서대로 저장하는 인덱스
•
범위 탐색에 유리하고, 이진 탐색 적용 가능
해시 인덱스 (Hashed Index)
•
탐색키를 해시 함수로 처리해 버킷 주소를 계산
•
빠른 정확한 값 탐색에 적합하지만 범위 탐색에는 부적합
인덱스 평가기준
기준 | 설명 |
접근 시간 | 인덱스를 통해 데이터를 찾는 데 걸리는 시간 |
유지 비용 | 삽입/삭제 시 인덱스를 재구성하는 데 드는 비용 |
공간 비용 | 인덱스를 저장하는 데 필요한 추가 공간 |
인덱스 크기에 따른 검색 성능
•
인덱스 크기 > 메모리 크기: 저장된 블록을 여러번 나누어 읽어야 하기 때문에 디스크 I/O 비용증가
•
인덱스 크기 < 메모리 크기: 디스크 I/O 줄어 탐색시간 축소
인덱스 엔트리 구조
•
탐색키 값: 정렬 기준이 되는 데이터 값
•
포인터: 실제 레코드가 저장된 위치를 가리킴
인덱스 엔트리 구성
인덱스 구성 방식
밀집 인덱스 (Dense index)
•
모든 레코드에 대해 탐색키값 | 포인터 쌍(인덱스 엔트리) 유지
•
빠른 탐색 가능
•
단점: 레코드 수만큼 인덱스 크기가 커져 조회 성능 저하
희소 인덱스(Sparse index)
•
일부 레코드만 인덱스에 포함
•
검색 시 인덱스에서 근접한 블록까지 찾고, 그 블록 내에서 선형 탐색
•
장점: 공간 절약, 유지비용 낮음
다단계 인덱스
•
4KB 크기의 한 블록에 100개의 엔트리가 삽입될때, 1억개의 레코드에 대한 밀집 인덱스(천개의 블록 = 4GB 공간 필요)
•
인덱스의 크기가 너무 커서 메모리에 다 못 올라올 경우 인덱스 자체를 또 인덱싱하는 방식
•
내부 인덱스 + 외부 인덱스 구조
◦
외부 인덱스는 내부 인덱스를 가리킴 (희소)
◦
내부 인덱스는 실제 레코드를 가리킴 (보통 밀집)
•
B+ 트리 인덱스
•
루트노드로부터 모든 단말노드에 이르는 경로의 길이가 같은 높이 균형 트리
•
순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
•
상용 DBMS에서 널리 사용되는 대표적인 순서 인덱스
구성요소
•
인덱스 세트 (루트 노드 + 중간 노드)
◦
단말 노드에 도달하기 위한 경로 제공
◦
각 노드는 탐색키와 포인터들을 포함
◦
자식 포인터 수: 최소 ⌈n/2⌉ ~ 최대 n
•
순차 세트 (단말 노드들)
◦
실제 레코드를 가리키는 포인터 포함
◦
인접 노드끼리 링크로 연결되어 있어 범위 탐색이 효율적
◦
탐색키 수: 최소 ⌈(n - 1)/2⌉
B+ Tree 삽입/삭제
삽입/삭제 시 중요한 특징
•
항상 균형 유지 (균형 트리)
•
삽입은 분할(split) 로 해결
•
삭제는 병합(merge) 또는 재분배(redistribute) 로 처리
•
중간 노드는 탐색만, 실제 데이터는 단말 노드에만 존재
B+ Tree 삽입 과정
1.
단말 노드에 새로운 <탐색키, 포인터> 삽입
2.
키가 많아져 노드 용량 초과 시 → 노드 분할
3.
중간값을 부모 노드로 승격
4.
부모 노드도 넘치면 재귀적으로 분할 진행
5.
트리의 높이가 증가할 수도 있음
B+ Tree 삭제 과정
1.
삭제 대상 키를 단말 노드에서 제거
2.
제거 후 키 개수가 최소 기준보다 작으면:
•
형제 노드와 키 재분배 시도
•
불가능하면 병합(merge)
3.
병합 시 부모 노드에서 해당 키 제거
4.
재귀적으로 병합되며 높이 감소 가능