순서 인덱스

# 클러스터링 인덱스(Clustering Index; Clustered Index)

- 파일의 데이터 레코드들이 특정 검색 키를 기준으로 순서화되어 있을 경우

- 그 순서화에 사용된 검색키에 해당하는 인덱스

- 주 인덱스(Primary Index)

- 오직 한 가지 인덱스만 만들 수 있음 (기회 한 번)

- 새로운 레코드 삽입될 때 물리적 순서 유지 못함 => 성능 떨어짐

- 검색 대상이 적을 때도 많을 때도 사용

- 범위 검색(between, >, <) 헤드 한 번 움직임(물리적으로 인접)

- 해당 데이터 레코드 많이 나오는 경우 사용

 

 

# 비클러스터링 인덱스(NonClustering Index; NonClustered Index)

- 파일의 순서화에 관여하지 않은 검색키에 해당하는 인덱스

- 2차 인덱스(Secondary Index)

- 범위 검색(헤드 계속 움직임)

- 가능하면 = 사용

- 검색 대상이 매우 적을 때 사용

- key값 분산도가 매우 높을 때 사용

- 포인터는 레코드들을 직접 가리키지 않고 포인터를 포함하는 버켓 가리킴

- 삽입 : 인덱스 엔트리에 새로운 데이터 레코드에 대한 포인터 추가

- 삭제 : 삭제된 데이터 레코드에 해당하였던 포인터 삭제

 

 

# 밀집 인덱스(Dense index)

- 파일에 있는 모든 검색 키 값이 인덱스 엔트리에 존재(빠름, 공간 부담)

- 삽입과 삭제시 부담

 

# 밀집 클러스터링 인덱스

- 검색 키 값과 그 검색 키 값의 첫 번째 데이터 레코드에 대한 포인터를 포함

- 똑같은 검색 키 값을 가진 레코드들은 이후 연속적으로 저장

 

# 밀집 비클러스터링 인덱스

- 인덱스의 검색키가 데이터 파일의 순서화에 참여한 검색키 값과 무관

- 포인터는 동일한 검색키를 가지는 모든 데이터 레코드들에 대한 포인터 목록을 확보

 

 

# 희소 인덱스(Sparse index)

- 인덱스 엔트리의 검색키 값은 파일의 해당 검색키 값의 일부만 있음(느림, 공간 부담 적음)

- 클러스터링 인덱스만 가능(검색 키로 정렬되어 저장될 때)

- 각 인덱스 엔트리의 포인터는 해당 검색키를 가지는 첫 번째 데이터 레코드를 가리킴

- 삽입과 삭제시 부담 적음

원하는 레코드를 찾는 방법 :

1. 주어진 검색키보다 작거나 같은 것 중 가장 큰 검색키 값을 가지는 인덱스 엔트리를 찾음

2. 해당 인덱스 엔트리가 가리키는 레코드를 시작으로 레코드를 찾을 때까지 순차적으로 검색

   블록당 하나의 인덱스 엔트리를 가지는 희소 인덱스 구성

 

 

# 다단계 인덱스(Multilevel Index)

- 주인덱스가 너무 큰 경우 :

  주기억장치에 전체 인덱스 엔트리를 적재할 수 없음

  디스크로부터 블록 단위로 입출력을 하여야 함

- 이진 검색은 인덱스가 b개 블록이면 [log2(b)] 만큼 블록 읽어야 함. 오버 플로우 블록이 사용되면 이진 검색 불가능.

  많은 디스크 입출력을 요구함

- 해결책 : 다단계 인덱스

- 주인덱스는 순차 파일로 디스크에 저장

- 원래의 주인덱스(내부 인덱스)에 대하여 희소 인덱스(외부 인덱스)를 구성

- 외부 인덱스도 너무 클 경우  또 다른 단계의 인덱스를 구성

- 두 개 이상의 단계를 가지는 인덱스

- disk I/O 줄여가며 접근

- B+ 트리 인덱스