Index
Index는 데이터 조회를 빠르게 하기 위한 방법이다.
- Index file : Search-key + Pointer 로 구성되어 있다
- Seach-key : 레코드를 찾기 위한 값으로 해당 데이터의 attribute 또는 set of attributes(복합키) 이다
- pointer : search-key에 해당하는 실제 데이터를 가르키는 값이다. 단순히 주소값이기 때문에 기존 데이터 파일 보다 인덱스 파일을 더 작게 유지 할 수 있다
인덱스는 여러 종류가 있다
Ordered Index
Index의 Search-key가 정렬되어 있는 경우 Ordered Index 이다
- Search-key가 정렬되어 있기 때문에 Range 쿼리를 하는 경우 빠르게 데이터를 조회 할 수 있다
- Exact 쿼리의 경우 빠르긴 하지만 Hash Index와 비교했을 때 더 느리다
- Hash Index는 Hash 함수로 바로 데이터에 접근 할 수 있고 Ordered Index는 Search-key를 이용하여 위치를 탐색해야 하기 때문이다
Clustering, NonClustering Index
- Search-key의 정렬 순서와 실제 데이터 File의 정렬 순서가 동일한 경우를 Clustering Index라 한다
- 반대로 동일하지 않으면 NonClustering Index이다
- Clustering Index가 성능이 더 좋다
- Range 쿼리를 생각해 보면 File 역시 정렬 순서가 동일하기 때문에 Disk I/O가 더 적게 일어 난다, Nonclustering의 경우 최악의 경우 결과 레코드 수 만큼 I/O가 발생 할 수 있다
- 그러나 테이블의 정렬 순서는 고정되어 있기 때문에 Clustering Index는 하나 밖에 만들지 못한다
- Clusteing Index의 경우 Seach-key에 해당하는 데이터가 여러개 있어도 정렬 순서가 동일하기 때문에 가장 먼저 위치한 데이터만 가르키면 모두 찾을 수 있다
- 그러나, NonClustering의 경우 Search-key에 해당하는 데이터가 여러개 있으면 여러 Pointer가 필요하다 따라서 인덱스는 bucket을 가르키고 bucket안에는 해당 key를 갖는 모든 레코드를 가르키는 Pointer 들이 존재한다
Dense, Sparse Index
- Dense Index는 모든 Search-key에 대한 Index가 존재하는 것을 의미한다
- Sparse Index는 일부 Search-key에 대한 Index만 존재하는 것을 의미한다
- Sparse Index는 Desnse Index 보다 Space를 아낄 수 있다
- Sparse Index는 Search-key보다 작은 Index 값 중 가장 큰 값을 찾아 해당 Pointer에서 시작하여 순서대로 탐색한다
- 즉, 데이터가 Search-key와 동일하게 정렬되어 있는 경우에만 사용하다 (Clustering Index)
- 인덱스로 레코드를 찾은뒤 탐색을 해야하기 때문에 Dense 보다는 조금 느릴 수 있다
- 그러나 만약, sparse index를 Block의 크기 만큼 설정하면 DISK I/O를 Dense Index와 동일하게 할 수 있다
Index를 사용하면 데이터 조회를 빠르게 할 수 있다 하지만, Index File을 추가로 생성하는 것이기 때문에 추가적인 Space Overhead가 발생한다
또한, 데이터를 삽입/삭제 시 Index도 삽입/삭제 해야하기 때문에 추가적인 Overhead가 발생한다
Multilevel Index
- Index 파일도 너무 커서 Memory에 모두 올릴 수 없는 경우 조회 비용이 커질 수 있다
- 이럴 때 Multilevel Index를 활용할 수 있다
- 기존 Index 파일에 대한 Index를 또 생성하는데 Sparse Index로 생성하여 더 작게 만든다
- 그래도 파일이 크다면 계속해서 레벨을 추가해 줄 수 있다
