Database Indexing

Index란?

Index란 데이터베이스에서 원하는 데이터에 빠르게 접근하기 위해 별도로 데이터의 위치를 기록한 자료구조이다.

 

Index file(or index entry)은 search-key와 pointer로 구성되어 있으며, 일반적인 파일보다 훨씬 작은 크기를 갖는다.

search-key에는 탐색할 파일의 key 값들이 저장되어 있으며, 빠른 탐색을 위해 정렬 혹은 hashing 되어 있다.

이 때, 특정한 순서로 정렬되어 있을 경우 ordered index, hash function을 통해 접근할 경우 hash index라고 한다.

pointer에는 해당 key 값을 갖는 데이터의 주소값이 저장된다.

 

index의 구조는 크게 primary index와 secondary index로 나뉘며,

데이터의 위치를 기록하는 방법에 따라 dense index, sparse index, multilevel index 등으로 나뉜다.

 

그럼 각각의 구조와 종류들에 대해 자세히 알아보자.

 

 

 

Primary Index

primary index(or clustered index)는 실제 데이터의 정렬 순서와 search-key의 정렬 순서가 같은 index를 말한다.

 

Dense Index

dense index는 primary index 중에서도 데이터의 모든 값이 search-key와 대응되는 index를 말한다.

 

위 그림에서 왼쪽은 index, 오른쪽은 실제 데이터이다.

실제 데이터의 모든 id 값이 index 파일의 search-key와 대응되어 있는 것을 볼 수 있다.

 

하지만 꼭 모든 tuple과 index entry가 하나씩 대응하는 것은 아니다.

 

위와 같이 id 값이 아닌 department 값을 통해 indexing을 한 경우 모든 tuple이 index entry에 대응되지 않는다.

하지만 데이터의 모든 department 값이 index 파일의 search-key와 대응되므로 dense index가 맞다.

 

 

Sparse Index

sparse index는 dense index와 다르게 실제 데이터의 일부 값만 search-key로 저장하는 index이다.

따라서 search-key가 순차적으로 정렬되어 있을 때만 사용 가능하다.

 

실제 데이터의 일부만 저장하기 때문에 dense index에 비해 적은 저장 공간을 필요로 한다.

하지만 dense index에 비해 탐색 시간이 길다는 단점이 있다.

 

 

Multilevel Index

dense index와 sparse index의 단점을 보완하여 만든 index 구조이다.

 

sparse index로 outer index를 구성하고, dense index로 inner index를 구성하여,

outer index에서는 pointer로 inner index를 가리키고, inner index는 실제 데이터의 위치를 가리키게 된다.

 

아주 많은 양의 데이터를 탐색할 때, dense index를 사용하면 시간은 빠르지만 메모리가 부족하고,

sparse index를 사용하면 메모리는 적게 들지만 탐색 시간이 오래 걸린다.

 

이 때, multilevel index를 사용하면 dense index보다 적은 메모리에, sparse index보다 빠른 시간에 탐색이 가능하다.

 

 

 

Secondary Index

secondary index(or unclustered index)는 실제 데이터의 정렬 순서와 search-key의 정렬 순서가 다른 index를 말한다.

 

secondary index는 기본적으로 정렬 순서가 다르기 때문에 dense index로만 구현이 가능하다.

 

또한, 각각의 data entry의 pointer는 실제 데이터 주소를 저장하는 bucket을 가리킨다.

 

secondary index는 primary index에 비해 특정 조건에서 빠른 탐색을 가능하게 하지만,

데이터 삽입이나, 순차적 탐색에서 매 record 마다 새 block을 할당해야 해 많은 메모리와 시간이 필요하다.