Sparse Index
Sparse Index는 인덱스 레코드가 모든 검색 키를 포함하지 않고, 일부 선택된 검색 키만 저장하는 방식이다.
검색 과정은 다음과 같다.
- 찾고자 하는 키 가 주어졌을 때, 먼저 보다 작은 값 중 가장 큰 검색 키를 인덱스에서 찾는다.
- 해당 위치에서부터 순차적으로 탐색을 진행하여 원하는 키를 찾는다.
이 방식은 Dense index와 비교했을 때 저장 공간이 적게 필요하고, 삽입 시 발생하는 오버헤드도 줄어든다는 장점이 있다. 반면, 검색 속도는 Dense index보다 더 오래 걸린다는 단점이 있다.
