[DataBase] Indexing

https://www.db-book.com/

Database System Concepts - 7th edition

< 인터넷에 제공되어있는 Avi Silberschatz 외 2인, Database System Concepts - 7th edition, McGraw-Hill, 2019 에 관한 자료를 참조 >

 

 

Index

• Basic Concepts
• Ordered Indices
• B+ Tree Index Files
• B Tree Index Files
• Hashing

 

 

Basic Concepts

 인덱싱 방법은 원하는 데이터에 대한 접근속도를 높이기 위해 고안되었다.

예를 들어, 일반 도서를 생각해보자. 도서의 목차를 통해 원하는 정보가 담겨있는 페이지로 바로 찾아갈 수 있게 된다.

 

인덱싱 기법은

• Search Key 를 통해 파일의 레코드들을 탐색한다.
  • 이는 하나의 속성 혹은 그들의 집합으로 이루어져있다.
• Index file 이라는 추가 자료구조를 필요로한다.
  • 이는 (search key, pointer) 쌍으로 구성되어있다. 이들을 index entry 라고 부른다.
  • 인덱스 파일은 전형적으로 원래 파일보다 작아야 한다.
• Ordered indices
  • 인덱스의 search key들은 정렬된 채로 저장되어있다.
• Hash indices
  • search key들은 해시 함수를 사용하여 Bucket 전역에 걸쳐 균일하게 분산되어있다.

 

 

Index Evaluation Metrics

 인덱싱 기법 평가 측정기준에 대한 설명이다.

• Access types
  • 인덱스들은 구체화된 범위의 값으로 존재해야 한다.
• Access time
  • 특정 데이터를 찾을 때 걸리는 시간이다.
• Insertion time
  • 새로운 데이터의 삽입 시간 + 인덱스 구조 변경 시간을 의미한다.
• Deletion time
  • 데이터의 삭제 시간 + 인덱스 구조 변경 시간을 의미한다.
• Space overhead
  • 인덱스 구조가 차지하는 추가 공간을 의미한다.

 

 

Ordered Indices

 순서화된 인덱스에서, 인덱스 개체들은 search key 값의 정렬에 따라 저장되어있다.

 

• Primary index
  • 순서적으로 구조화된 파일에서, 레코드들을 유일하게 구분할 수 있는 search key이다. 릴레이션의 PK와 같은 역할을 한다. 파일의 순차적 순서를 지정하는 역할을 한다. 
  • Clustering index라고도 불린다.
• Secondary index
  • 검색 키가 파일의 순차적 순서와는 다른 순서를 지정하는 인덱스이다.
  • non-clustering index라고도 불린다.
• Index-sequential file
  • 검색 키가 Primary index인 파일을 의미한다.

 

Dense Index Files

 Index entry들이 모든 실제 search-key 값과 대응하는 인덱스를 의미한다.

하나의 인덱스 엔트리가 여러 레코드값과 대응 가능할 때, 인덱스 엔트리는 해당 범위에서 가장 상단의 레코드와만 대응한다.

 

Sparse Index Files

 Index File이 일부 탐색 키만 가지는 것을 의미한다.

각 블록 내에서 순차적으로 접근한다.

 

이는 Dense Indices에 비해,

• 삽입 / 삭제 비용이 낮다.
• 그러나 느리다.

 

Dense 와 Sparse를 적절히 혼용해, 파일을 블로고하 하고 index file이 블록화된 구역의 첫 레코드를 가리키게 하면,

블록 접근을 최소화 하며 인덱스파일이 차지하는 공간을 줄인다.

 

 

Secondary Indices Example

 search key가 아닌 속성도 secondary indice로 사용 가능하다.

그러나 항상 dense index가 되어야 한다.

 

2차 인덱스 를 사용하는 이유는 다음과 같다.

• primary index의 구조에서 다른 key를 사용한 query에 대해, 그 다른 키로 secondary index를 만들었다면 연산이 더 빠르다.
  • 그러나 이는 데이터베이스 수정에 overhead, 추자적인 부분을 부과한다.
    • 레코드가 수정되거나 삭제되면, 릴레이션의 모든 인덱스도 업데이트되어야 한다.
    • 레코드가 업데이트 되면, 업데이트 된 속성에 있는 인덱스도 업데이트되어야 한다.
• Drawback:
  • primary index를 사용한 순차적 탐색은 효과적이나, 자기 디스크 상 2차 인덱스 구조에서는 비싸다.

 

 

Multilevel index

디스크 용량은 크고 메모리는 작아서 이를 사용한다.

 

outer index와 inner index로 구분한다.

• outer index
  • basic index에 대해 희소 index여야 한다.
• inner index
  • basic index file이다.

outer index의 size를 줄여 main memory가 담을 수 있게 하는 것이 목표이나, 여전히 크다면 더 많은 단계의 인덱스를 만들어도 된다.

 

 

 

B+ Tree Index Files

 연속형 인덱스의 단점

• 파일이 커질 수록 overflow block이 많이 발생한다.
• 주기적으로 전체 파일을 재구성해야 한다.

 

B+ tree index file의 장점

• 엔트리 삽입과 삭제에 대해, 자동적으로 재구성이 이루어진다.
• 성능을 유지하기 위한 전체 파일 재구성이 필요하지 않다.

그러나 삽입/삭제 연산에 대해 추가 공간이 필요하다는 단점이 있는데, 장점이 단점을 능가하므로 주로 사용한다.