Indexing 문서 원본 보기

상위 문서: [[데이터베이스 시스템]]

==개요==
많은 쿼리는 파일 내에 있는 레코드(records)들의 일부분만을 참조한다. 예를 들어, “Physics 학과의 모든 강사를 찾아라”와 같은 쿼리는 instructor 또는 student 레코드의 일부만을 참조한다. 따라서 시스템이 instructor 릴레이션의 모든 튜플을 읽으면서 dept_name 값이 “Physics”인지 확인하는 것은 비효율적이다. 이상적으로는, 시스템이 이러한 레코드들을 직접 찾아낼 수 있어야 하며, 이를 구현하기 위해 인덱싱(Indexing)이라는 개념이 사용된다.

데이터베이스 시스템에서 파일에 대한 인덱싱은 어떤 youngwiki의 [[:분류:데이터베이스 시스템|분류 문서]]와 거의 비슷한 방식으로 작동한다. 예를 들어 youngwiki에서 특정 주제에 대해 알고 싶다면,<ref>검색창은 사용하지 않는다고 가정하자.</ref> 분류 문서에 접근하여 해당 주제가 나타나는 문서를 찾고, 해당 문서를 읽어서 원하는 정보를 얻을 수 있다. 분류 문서에 나열된 단어들은 정렬된 순서로 되어 있어서 원하는 단어를 쉽게 찾을 수 있으며, 그 문서 크기가 작아 수고를 줄인다. 인덱싱도 이러한 원리를 사용한다. 예를 들어, 어떤 student 릴레이션 내에 존재하는 튜플에  대한 레코드를 특정 ID로 검색하려면, 인덱싱을 참조하여 해당 레코드가 있는 디스크 블록을 찾고, 그 디스크 블록을 가져와서 원하는 레코드를 얻을 수 있다. 
[[파일:Index entry.png|섬네일|200x200픽셀|Figure 1. Index entry]]
Figure 1은 인덱스를 저장하는 파일인 인덱스 파일(index file) 내에 존재하는 인덱스 항목(index entry)이 어떻게 구성되는지 보여준다. 검색값(search key) 어떤 파일에서 레코드를 검색하는 데 사용되는 속성 또는 속성들의 집합이다. 쉽게 말해서, 검색하는 값이 속하는 속성 또는 그 집합이다. 포인터(pointer)는 해당 값을 가지는 레코드가 원본 테이블에서 어디 있는지를 가리키는 포인터이다.

인덱싱의 기본적인 유형에는 아래의 두 가지가 있다: 
# 정렬 색인(Ordered indices): 검색키들을 정렬된 순서로 저장한다.
# 해시 색인(Hash indices): 검색키들을 해시 함수(hash function)를 사용하여 bucket에 균등하게 분배한다.

해당 문서에서는 여러 가지 인덱싱 기법들을 다루며, 각기 다른 장단점을 가진다. 이때 아래는 각 인덱싱 기법들을 평가하기 위해서 사용되는 평가 기준들이다:
* 접근 유형(Access types): 어떤 유형의 접근을 효율적으로 지원하는가?
** 예를 들어, 특정 속성 값에 해당하는 레코드를 찾는 경우
** 예를 들어, 속성 값이 특정 범위에 해당하는 레코드를 찾는 경우
* 접근 시간(Access time): 특정 데이터 항목이나 항목 집합을 찾는 데 걸리는 시간
* 삽입 시간(Insertion time): 새로운 데이터를 삽입하는 데 걸리는 시간
** (삽입할 위치를 찾는 데 걸리는 시간) + (인덱싱을 갱신하는 데 걸리는 시간)
* 삭제 시간(Deletion time): 새로운 데이터를 삭제하는 데 걸리는 시간
** (삭제할 항목을 찾는 데 걸리는 시간) + (인덱싱을 갱신하는 데 걸리는 시간)
* 공간 오버헤드(Space overhead): 색인 구조가 차지하는 추가적인 공간

인덱싱은 데이터베이스에서 질의를 효율적으로 처리하기 위해 매우 중요하다. 인덱싱이 없다면, 모든 쿼리는 쿼리에서 사용하는 모든 릴레이션의 전체 내용을 읽게 되며, 단 몇 개의 레코드만을 가져오는 쿼리에 대해서도 필요한 것보다 많은 비용이 소모된다.

==각주==
[[분류:데이터베이스 시스템]]