5. 색인(Indices)

색인이란...?

: 데이터에 접근을 할 때 속도를 높이기 위한 도구.

ex.책 뒤의 pg에 대한 태그 <search-key(책 내 키워드), pointer(페이지 번호)>

 

- <search-key, pointer>: index 레코드

-> 이게 모이면 index 화일.

 

- 인덱스의 2종류:

1. Ordered index

: search-key가 정렬되어 있는 index.

 

2. Hash index

: search-key가 정렬되어 있지 않고 hash 함수를 통해 구분하는 index.

 

색인의 평가요소 5가지

1. 접근 타입 지원

: Exact match query(속성의 특정 값과 일치하는 터플을 검색하는 일치 질의 형태) VS. Range query(속성이 일정 범위에 속하는 터플을 검색하는 범위 질의 형태)

2. 접근 시간

3. 삽입 시간

4. 삭제 시간

5. 공간 오버헤드

 

Ordered Index(정렬 색인)

: 색인 레코드가 정렬되어 저장되는 색인 구조.

1. Primary Index(= clustered Index)

: 색인도 정렬되어 있고, 데이터도 색인에 따라 정렬되어 있는 구조. 데이터 화일 당 1개만 존재!

2. Secondary Index(= non-clustered Index)

: 색인은 정렬되어 있으나, 데이터는 정렬되지 않은 상태로 저장되는 구조. 데이터 화일 당 여러 비클러스터 색인이 존재!

 

Dense Index(밀집 색인)

: 모든 탐색키(search-key)에 대하여 index 엔트리가 색인에 존재하는 경우의 정렬 색인.

밀집 색인 예시1

밀집 색인 예시2

Sparse Index(희소 색인)

: 모든 탐색키(search-key)에 대한 색인 엔트리가 없는 정렬 색인.

희소 색인 예시

희소 색인은 밀집 색인에 비해

- 장점: 공간을 적게 차지하고 추가나 삭제에 대한 오버헤드가 적음.

- 단점: 검색 시에 더 많은 시간을 요구함.(인덱스 엔트리가 색인에 없으면 데이터 화일도 검색해야 하니까!)

 

하지만...!!

이런 단점 극복해야지?

희소색인을 블록에 속하는 레코드의 가장 적은 값으로 구성하면 검색시간이 느리다는 약점을 보완할 수 있음.(블록 내의 연산은 메인메모리 상에서의 연산이라 오버헤드가 적으니까...!)

 

Multilevel Index(다단계 색인)

: 색인 화일에 색인 엔트리가 많을 시에는 색인 화일을 대상으로 상위에 여러번 색인 구성이 가능함.



색인 갱신:삭제, 삽입 -> 이 부분 넘어감.

 

Secondary Index(이차 색인)

: 색인 레코드 순서대로 데이터 레코드 순서를 정렬하지 않은 색인. 동일 데이터 화일에 대하여 임의의 속성에 대하여 색인 개수 제한 없이 생성할 수 있음. 또한 이차 색인은 모두 탐색키 값이 정렬되지 않기에 반드시 밀집 색인 형태임.

이차 색인 예시

Primary Index VS. Secondary Index

- 색인을 갱신하는 것은 DB 변경 오버헤드를 야기함.(화일이 변경되면 화일의 모든 index도 갱신되어야 함.)

- 주 색인과 달리 이차 색인은 데이터 화일 전체 탐색을 하는 연산은 매우 비효율적임.(이차 색인은 전체 탐색 시 동일 데이터 블록을 1회 이상 검색할 수 도 있기 때문..!!)

 

 

B+ Tree Index

: 거의 대부분의 DBMS에서 사용하는 index 구조이며, 단점보다 장점이 많음. Balanced Tree(= 루트에서 리프 노드까지의 길이가 동일한 트리)임.

n=4인 경우의 B+트리.(pointer의 개수 또한 n이다.)

- Balanced Tree(= 루트에서 리프 노드까지의 길이가 동일한 트리)임.

-> 어떤건 빨리 찾고 어떤건 늦게 찾고 하는 문제가 발생 X

 

- root, leaf 노드를 제외한 각 노드들은 n/2 ~ n개의 포인터(=children)를 가짐.

 

- leaf 노드는 (n-1)/2 ~ n-1개의 value를 가짐.

 

- root가 leaf 노드가 아니면 최소 2개의 children을 갖고, leaf인 경우에는 0 혹은 n-1개의 value를 가짐.

 

B+ Tree 노드의 구조

- 주로 [P1, K1, P2, K2, ... Kn-1, Pn].

Kn: search-key value.

Pn:

1) non-leaf 노드이면, children에 대한 pointer

2) leaf 노드이면, record or bucket에 대한 pointer

 

- 노드 내의 search-key는 정렬되어 있음. -> K1<K2<K3<...<Kn-1

 

Leaf 노드

leaf 노드 예시

• Kn은 Pn의 값을 따라가면 데이터 화일에서 해당 값을 찾을 수 있는 방식
• Pn은 다음 leaf 노드(sibling node)를 가리킴. -> leaf 노드를 순차적으로 검색하는 것이 용이함.
• 일반적으로 pointer에는 RID(= PID + slot 넘버)가 들어가 있음.

Non-leaf 노드(=내부 노드)

: 리프노드에 대한 다단계 희소 색인을 구성한 것.

 

Pi: pointing하는 노드에 속하는 search-key 값

Ki: search-key

라고 할 때, 보통 Ki <= Pi+1 < Ki+1를 성립한다.

non-leaf 노드의 pointing 예시

B+Tree를 왜 쓰는 것일까...?

- B+Tree를 쓰면 상대적으로 짧은 level을 씀.

 

root 노드는 최소 2*[(n-1)/2]개의 값을 가짐

-> 다음 레벨은 2*[(n-1)/2]*(n/2)개의 값을 가짐

-> 그 다음 레벨은 2*[(n-1)/2]*(n/2)*(n/2)개의 값을 가짐

...

- 만약 데이터 화일 내에 K개의 search key-value가 있다면 tree 높이는 log[n/2](K)를 넘지 않음.

- 노드는 일반적으로 disk 블록의 크기와 같음.

 

B+Tree 삽입

<순서>

1. leaf 노드에 해당 search-key value가 있는지 확인.

2-1. 만약 search-key value가 있으면 특별한 연산 필요 X

2-2. 만약 search-key value가 없으면

2-2-1. 레코드를 데이터 파일에 추가

2-2-2. leaf 노드에 공간이 있다면 (key-value, pointer)값을 leaf 노드에 삽입

2-2-3. 공간이 없다면 노드를 split하고 새로운 엔트리를 생성

 

Adams 삽입 예시

Lamport 삽입 예시