희소 인덱스

희소 인덱스(Sparse Index, 비밀집 인덱스)는 데이터 파일의 모든 탐색 키 값이 아니라 일부 값, 보통 데이터 블록마다 하나의 값에 대해서만 인덱스 엔트리를 두는 순서 인덱스이다.

개요

순서 인덱스는 엔트리를 어떻게 두느냐에 따라 밀집 인덱스와 희소 인덱스로 나뉜다. 밀집 인덱스는 파일에 나오는 탐색 키 값마다 엔트리가 하나씩 있고, 희소 인덱스는 그 가운데 일부만 엔트리로 둔다. 희소 인덱스로 레코드를 찾으려면 찾는 값 K 보다 작거나 같은 값 가운데 가장 큰 엔트리를 인덱스에서 고른 뒤, 그 엔트리가 가리키는 위치부터 데이터 파일을 순차로 읽어 내려간다. 이 방법은 데이터 파일이 그 탐색 키 순서로 정렬되어 있을 때만 성립한다. 엔트리가 빠진 값의 레코드가 엔트리가 있는 값 바로 뒤에 놓여 있다는 보장이 정렬에서 나오기 때문이다.

한 파일에 몇 개까지 둘 수 있는가

데이터 파일은 물리적으로 한 가지 순서로만 정렬될 수 있다. 희소 인덱스는 그 정렬 키에 대해서만 만들 수 있으므로 한 데이터 파일은 희소 인덱스를 최대 한 개 가진다. 정렬 순서와 다른 속성에 대한 인덱스, 곧 보조 인덱스(비클러스터링 인덱스)는 레코드가 흩어져 있어 건너뛸 수 없으므로 반드시 밀집이어야 한다. 따라서 한 파일이 가질 수 있는 조합은 "희소 인덱스 하나(정렬 키) + 밀집 인덱스 여러 개(그 밖의 키)"이다. "밀집 인덱스 하나와 희소 인덱스 여럿"이라는 조합은 성립하지 않는다.

Elmasri·Navathe 의 분류로 보면 정렬 키 필드에 만드는 기본 인덱스(primary index)와 정렬된 비키 필드에 만드는 클러스터링 인덱스가 희소 인덱스의 예이다. 기본 인덱스는 데이터 블록마다 블록의 첫 레코드(앵커 레코드) 값으로 엔트리를 하나 둔다.

장단점

• 엔트리 수가 블록 수 정도로 적어 공간이 적게 들고, 삽입·삭제 때 고칠 엔트리도 적다.
• 엔트리를 찾은 뒤 블록 안을 다시 훑어야 하므로 레코드 하나를 찾는 속도는 대체로 밀집 인덱스보다 느리다.
• 블록 단위로 엔트리를 두면 디스크 접근 단위와 맞아떨어져 실제로 손해가 적다. 그래서 클러스터링 인덱스는 블록당 한 엔트리의 희소 인덱스로 두는 것이 일반적이다.
• 인덱스 파일 자체가 커지면 그 위에 다시 희소 인덱스를 얹어 다단계 인덱스를 만든다. 위 단계는 모두 희소 인덱스이다.

밀집 인덱스와 구별하기

구분	희소 인덱스	밀집 인덱스
엔트리	일부 값(보통 블록당 하나)	모든 탐색 키 값마다
데이터 파일 정렬	탐색 키 순서로 정렬되어 있어야 한다	상관없다
한 파일당 개수	최대 한 개(정렬 키)	여러 개 가능
공간·갱신 부담	작다	크다
검색	엔트리 찾은 뒤 순차 탐색	엔트리가 레코드를 바로 가리킨다
해당 인덱스	기본 인덱스, 클러스터링 인덱스, 다단계 인덱스의 위 단계	보조 인덱스

같이 보기

• 밀집 인덱스
• 다단계 인덱스
• 클러스터링 인덱스
• 데이터베이스 인덱스
• 색인 순차 파일