[Indexing]Overview

search에 대한 효율적인 처리를 위해서 search를 위한 tool이 필요하다. dbms search--> search tool --->file

 

subtopics

basic concept

simple index

b+ tree index

b+ tree variations

static hashing

dynamic hashing

bitmap index

 

basic concept

indexing: key가 있고 그 조건을 만족시키는 정보를 찾아낼 때 indexing을 통해 속도를 높인다. 대표적인 것이 책의 index 부분이다. 책 뒤에 있는 색인 부분이 simple index이다. <search-key, pointer(address)> 구조이다.

 

두 가지 index

ordered indices

hash indices

 

evaluation metric

-access type

1.exact match query : name ='홍길동' 같은 것, id = '20131234'

2.range query : age > 20 , 해쉬는 range query를 지원하지 않는다.

-access time : 제일 관심있는 비용

-insertion time

-deletion time

-space overhead

 

 

ordered index

-primary index: index파일의 키 값이 파일의 sorted된 것으로 이루어진 것. 학생 id로 정렬된 파일에 대해 id를 key로 하여 index 파일을 만듦. primary key를 사용하는 것이 기준이 아니다. 

위의 데이터 파일은 id를 기준으로 정렬되어 있다. 따라서 id를 사용해서 index를 만들면 primary index, 나머지를 사용하면 secondary index가 된다. 

 

-secondary index: index파일의 키 값이 sorted key로 이루어지지 않은 것. 학생 id로 정렬된 파일에 대해 id가 아닌 것을 key로 하여 index 파일을 만듦. 

 

위 데이터 파일은 학과를 기준으로 정렬되어 있다. 따라서 학과를 key로 해서 만들면 primary index, 나머지를 사용해서 만들면 secondary index가 된다.

 

 

dense index vs sparse index

dense index

index의 키 값이 data file의 모두 등장하지 않는 경우.

dense index

desne index

 

sparse index

sparse index

file의 key의 순서와 index file의 key 순서가 같으므로 primary index이다. pid=104를 찾으려고 할 때 104보다 작은 것 중에서 가장 큰 101부터 탐색하게 된다. sparse index 경우에는 반드시 primary index여야 한다. 파일이 key에 대해서 정렬되어 있어야만 sparse index를 통해 찾을 수 있다.

 

data block에서 가장 작은 key값들로 sparse index를 만든 경우이다.