Indexing

Indexing이 뭔가요?

 위 사진과 같이 다른 테이블, 엔트리로 빠르게 안내해주는 보조 접근 방식이라 생각하면 된다. 이로 인해 원하는 데이터에 빠르고 효율적이게 접근이 가능하다.

 이러한 Index는 Single-Level과 Multi-Level Indexes로 나눌 수 있다.

Single-Level Indexes

 Single-Level Indexes의 Index Table에는 Index value와 해당 Disk block을 가리키는 Pointer가 있다. 이때 Index value들은 정렬되어 있고, 당연하지만 원래 데이터 파일보다 작다는 특징이 있다. Single-Level Indexes는 Primary Indexes, Clustering Indexes, Secondary Indexes로 나눠진다.

Primary Indexes

 Primary Indexes는 Unique한 키인 Primary key로 이루어진 Index file을 가지고 있다. 위 Index file에서 볼 수 있듯이 Primary key value는 정렬되어 있고 이에 따라 원하는 Entry를 쉽게 찾을 수 있다.

 인덱스는 Dense 혹은 Sparce(non-dense)하게 구성할 수 있다. Dense는 모든 key value에 링크를 거는 방식이고, sparce는 몇몇 value에만 링크를 거는 방식이다. 위 그림은 sparce하게 구성되어 있는데, 인덱스 항목의 수가 적고 크기도 작으므로 데이터 파일에 직접 접근하는 방식보다 적은 블록 접근으로 binary search를 수행가능하다.

Clustering Indexes

 Clustering Indexes는 Primary Indexes와 다르게 non-key를 기준으로 정렬한 것으로, key가 아니기 때문에 중복이 가능하다는 특징이 있다. 이에 따라 Index file은 non-dense, 즉 sparce 하다.

 하지만 데이터 삽입, 삭제 시 약간의 문제점이 발생한다.

 데이터 삽입 전 distinct value들에 대해 저장 block을 예약하고 사용하는데, 만약 해당 블록이 다 차면 어떻해야 할까? 위 그림에서 3, 6번 데이터처럼 overflow-block을 사용하여 해결할 수 있다. Block pointer로 다음 블록으로 링크만 걸어주는 것이다.

Secondary Indexes

 Secondary Indexes는 key, non-key 둘다 가능하다. 그런데 대체 왜 사용하는걸까? 데이터 파일은 최대 하나의 정렬을 가질 수 있다. 이는 Primary, Clustering Indexes는 테이블당 최대 하나 혹은 둘다 사용하지 않아야 한다는 것을 뜻한다. 이때 Secondary Indexes가 사용된다. 왜냐하면 같은 data file에 대해 많은 secondary indexes들이 만들어질 수 있기 때문이다.

위 테이블을 보면 이미 학생들이 id에 대해 정렬이 되어 있지만 사실 이름으로 찾는 것이 더 효율적일 수 있기 때문에 Secondary Indexes, 즉 보조 색인을 사용하여 탐색을 구현해놓은 것이다.