[DB] Index

 

인덱스

 

데이터베이스 분야에 있어서 테이블에 대한 동작의 속도를 높여주는 자료구조.

고속의 검색 동작 뿐만 아니라 레코드 접근과 관련 효율적인 순서 매김 동작에 대한 기초를 한다.

RDBS에서는 인덱스는 테이블 부분에 대한 하나의 사본이다.

 

고속 접근, 시스템 부하를 줄이기 위해서 인덱스가 사용되지만 추가적인 저장공간, 인덱스 관리를 위한 추가 작업이 요구된다.

 

External-memory model을 통해 인덱스의 성능을 확인할 수 있다.

 

인덱스의 구성

Search Key 

file 안의 record를 찾기 위한 요소의 집합

 

Index File 

형식의 Index entries로 구성.

 

---

Ordered Index

Search Key의 값으로 정렬되어있는 인덱스.

 

Primary Index ( clustering index)

파일의 특정한 순서를 구체화 하는 search key.

 

primary index로 순서과 구체화 된 파일을 Index-sequential file이라 한다.

 

Secondary Index (non-clustering index)

primary index로 구체화된 순서와 다른 순서를 정하기 위한 인덱스.

 

 

Multilevel Index

만약 primary index에 대한 파일(dense index, sparse index)가 main memory에 적합하지 않다면 Multilevel Index 를 사용할 수 있다.

primary index file을 디스크에 저장하고(Inner Index), 그 file에 대한 sparse index(Outer Index)를 메모리에 올려서 사용한다.

 

---

Hash Index

Key(Index record), Value(record Address)의 형식으로 Hash Table 기반으로 저장된 Index.

 

 

- 동등 비교 검색에 최적화. 범위를 검색하거나 정렬을 위해서는 적합하지 않음.

 

- InnoDB의 버퍼 풀에서 빠른 레코드 검색을 위한 Adaptive Hash Index로 사용, 몇몇 DBMS에서는 JOIN에 사용.

 

- 주로 메모리 기반 데이터베이스에서 사용

 

 

---

B+ tree Index

파일이 커질수록 성능이 떨어지고, 많은 Overflow block이 생기는 index-sequential, hash index file 대신 사용하는 Index file data structure이다.

 

시중 대부분의 RDBS는 B+ tree를 사용하고있으며 변형 형태인 B-tree, B-*tree 또한 많이 사용된다.

 

 

B+ tree는 다음 조건을 만족하는 Rooted-tree 형태이다.

• root - leaf의 모든 경로는 같은 길이를 가진다.
• root와 leaf가 아닌 모든 노드는 ceil(n/2), n 사이의 자식을 가진다.
• leaf는 ceil((n-1)/2), n-1 사이의 값들을 가진다.
• root가 leaf가 아니라면, 이것은 적어도 2명의 자식들을 가진다.

 

 

B+ tree Node

 

P : non-leaf node는 자식을 가리키는 포인터, leaf node는 record의 pointer 또는 bockets of records를 가리킨다.

K : search-key value를 가리키며 K1 < Kn-1의 순으로 정렬되어있다.

 

Leaf Node

각각의 P는 데이터의 실제 주소를 가리키고, Leaf node의 마지막 포인터는 다음 leaf node를 가리킨다.

 

Non-leaf Node

모든 Non-leaf nodes는 leaf node에 대한 multi-level sparse index이다.

Pi가 가리키는 leaf node는 Ki보다 search key가 항상 작다.