Dense, Sparse, Multilevel Index

I. Dense, Sparse, Multilevel Index의 개요

가. Sorting이 되어 있다는 가정하에 적용 가능

나. Dense Index (밀집 인덱스)

   - 인덱스 레코드는 파일에 있는 모든 Search Key값에 대해 Index 구성

   - 인덱스 레코드는 Search Key값과 그 Search Key값의 첫번째 데이터 레코드에 대한 포인터 포함

   - 같은 Search Key를 가진 나머지 레코드들은 첫번째 레코드 이후부터 연속적 저장

   - 레코드 위치를 정할 때는 희소 인덱스보다 빠름

다. Sparse Index (희소 인덱스)

   - 인덱스 레코드는 Search Key 값에 대해 몇 개만 나타냄

   - 레코드를 위치 시키기 위해 찾고자 하는 검색 값보다 작거나 동일한 것 중 가장 큰 Search Key값을 가지는 인덱스 엔트리를 찾고 원하는 레코드를 찾을 때까지 포인터를 따라감

   - 밀집 인덱스보다 작은 공간 요구, 삽입 삭제에 대한 부담 적음

라. Multilevel Index (다 계층 인덱스)

   - 인덱스를 2단계 혹은 그 이상의 단계로 생성

   - 하나의 데이터 블록에 전체 인덱스가 포함될 때 까지 작업 진행