Indexing

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

개요

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

데이터베이스 시스템에서 파일에 대한 인덱싱은 어떤 youngwiki의 분류 문서와 거의 비슷한 방식으로 작동한다. 예를 들어 youngwiki에서 특정 주제에 대해 알고 싶다면, 분류 문서에 접근하여 해당 주제가 나타나는 문서를 찾고, 해당 문서를 읽어서 원하는 정보를 얻을 수 있다. 분류 문서에 나열된 단어들은 정렬된 순서로 되어 있어서 원하는 단어를 쉽게 찾을 수 있으며, 그 문서 크기가 작아 수고를 줄인다. 인덱싱도 이러한 원리를 사용한다. 예를 들어, 어떤 student 릴레이션 내에 존재하는 튜플에 대한 레코드를 특정 ID로 검색하려면, 인덱싱을 참조하여 해당 레코드가 있는 디스크 블록을 찾고, 그 디스크 블록을 가져와서 원하는 레코드를 얻을 수 있다.

Figure 1. Index entry

Figure 1은 인덱스를 저장하는 파일인 인덱스 파일(index file) 내에 존재하는 인덱스 항목(index entry)이 어떻게 구성되는지 보여준다. 검색값(search key) 어떤 파일에서 레코드를 검색하는 데 사용되는 속성 또는 속성들의 집합이다. 쉽게 말해서, 검색하는 값이 속하는 속성 또는 그 집합이다. 포인터(pointer)는 해당 값을 가지는 레코드가 원본 테이블에서 어디 있는지를 가리키는 포인터이다.

인덱싱의 기본적인 유형에는 아래의 두 가지가 있다:

1. 정렬 색인(Ordered indices): 검색키들을 정렬된 순서로 저장한다.
2. 해시 색인(Hash indices): 검색키들을 해시 함수(hash function)를 사용하여 bucket에 균등하게 분배한다.

Index Evaluation Standards

해당 문서에서는 여러 가지 인덱싱 기법들을 다루며, 각기 다른 장단점을 가진다. 이때 아래는 각 인덱싱 기법들을 평가하기 위해서 사용되는 평가 기준들이다:

• 접근 유형(Access types): 어떤 유형의 접근을 효율적으로 지원하는가?
  • 예를 들어, 특정 속성 값에 해당하는 레코드를 찾는 경우
  • 예를 들어, 속성 값이 특정 범위에 해당하는 레코드를 찾는 경우
• 접근 시간(Access time): 특정 데이터 항목이나 항목 집합을 찾는 데 걸리는 시간
• 삽입 시간(Insertion time): 새로운 데이터를 삽입하는 데 걸리는 시간
  • (삽입할 위치를 찾는 데 걸리는 시간) + (인덱싱을 갱신하는 데 걸리는 시간)
• 삭제 시간(Deletion time): 새로운 데이터를 삭제하는 데 걸리는 시간
  • (삭제할 항목을 찾는 데 걸리는 시간) + (인덱싱을 갱신하는 데 걸리는 시간)
• 공간 오버헤드(Space overhead): 색인 구조가 차지하는 추가적인 공간

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

Ordered Indices

파일 내 레코드에 빠르게 임의 접근(random access)하기 위해, 우리는 인덱스 구조(index structure)를 사용할 수 있다. 각 인덱싱 구조는 특정한 검색키에 연관되어 있다. 정렬 인덱스(ordered indices)들은 검색키들의 값을 정렬된 순서로 저장하며, 각 검색키와 그것을 포함하는 레코드들을 연결시킨다. 이때 인덱싱이 적용된 파일 내의 레코드들 자체도 어떤 정렬 순서로 저장될 수 있으며, 하나의 파일은 서로 다른 검색키들에 대해 여러 개의 인덱스를 가질 수 있다.

Figure 2. Sequential file for instructor records

파일이 검색키에 따라 순차적으로 정렬되어 있다고 가정하자. 클러스터링 인덱스(clustering index)는 해당 검색키를 기준으로 실제 레코드들이 디스크에 정렬되어 저장된 경우, 해당 검색키에 대해 만들어진 인덱스를 의미한다. 즉, 인덱스가 참조하는 검색 키의 순서와 파일 내 레코드의 저장 순서가 일치하는 경우이다. 이는 기본 인덱스(primary index)라고도 불리며, 보통 기본키(primary key)에 대한 인덱스로 사용된다. 이와 다르게, 파일의 순차적인 정렬 순서와 다른 순서를 지정하는 인덱스를 세컨더리 인덱스(secondary index) 또는 비클러스터링 인덱스(nonclustering index)라고 한다. Figure 2는 instructor 레코드의 순차 파일(sequential file)을 보여준다. 해당 예제에서 레코드들은 ID를 기준으로 정렬된 순서로 저장되어 있으며, ID 속성이 검색 키로 사용된다.

Dense and Sparse Indices

하나의 인덱스 항목(index entry) 또는 인덱스 레코드(index record)는 figure 1과 같이 검색키 값과, 그 값을 검색키 값으로 가지는 하나 이상의 레코드에 대한 포인터들로 구성된다. 레코드에 대한 포인터는 디스크 블록에 대한 식별자(identifier)와 해당 블록 내에서 레코드를 식별할 수 있는 오프셋(offset)으로 구성된다. 이때 정렬 인덱스의 유형은 크게 두가지로 구분된다:

• 조밀 인덱스(Dense index): 파일 내의 모든 검색 키 값에 대해 인덱스 항목이 존재한다.
  • 조밀 클러스터링 인덱스에서는 인덱스 레코드가 검색키 값을 포함하고 있으며, 해당 검색키 값을 가지는 첫 번째 데이터 레코드에 대한 포인터를 포함한다. 같은 검색 키 값을 가지는 나머지 레코드들은 같은 검색 키에 따라 정렬되어 있기 때문에 첫 번째 레코드 이후로 순차적으로 저장되어 있다.
  • 조밀 비클러스터링 인덱스는 같은 검색 키 값을 가지는 모든 레코드에 대한 포인터 목록을 저장한다.
• 희소 인덱스(Sparse index): 인덱스 항목이 검색키의 일부 값에 대해서만 존재한다.
  • 희소 인덱스는 릴레이션이 검색키 값 기준으로 정렬되어 있을 때만, 즉 해당 인덱스가 클러스터링 인덱스일 때만 사용할 수 있다.
  • 레코드를 찾기 위해서는, 찾고자 하는 검색 키 값보다 작거나 같은 값 중에서 가장 큰 검색 키 값을 가진 인덱스 항목을 찾는다. 그런 다음, 그 인덱스 항목이 가리키는 레코드에서 시작해서, 파일 내에서 포인터를 따라가며 원하는 레코드를 찾을 때까지 순차적으로 읽는다.

• 
  Figure 3. Dense index
• 
  Figure 4. Sparse index
• 
  Figure 5. Dense index with dept_name

Figure 3와 Figure 4는 각각 instructor 파일에 대한 조밀 인덱스와 희소 인덱스를 보여준다. 예를 들어, ID가 “22222”인 instructor의 레코드를 찾고자 한다고 하자. Figure 3의 조밀 인덱스를 사용하는 경우, 해당 레코드로 바로 연결되는 포인터를 따라가서 원하는 레코드를 직접 찾을 수 있다. Figure 4의 희소 인덱스를 사용하는 경우에는 “22222”에 대한 인덱스 항목은 존재하지 않는다. 이 경우, “22222”보다 작은 인덱스 항목 중 가장 마지막 값인 “10101”을 찾고, 그 포인터를 따라간다. 그런 다음 instructor 파일을 순차적으로 읽으면서 원하는 레코드를 찾는다.

또 다른 예시로, 검색 키 값이 기본키가 아니라고 가정하자. Figure 5는 검색 키가 name인 instructor 파일에 대한 조밀 클러스터링 인덱스를 보여준다. 이 경우 instructor 파일은 ID가 아닌 dept_name을 기준으로 정렬되어 있으므로, dept_name에 대한 인덱스는 클러스터링 인덱스가 된다. History 학과에 해당하는 레코드를 찾는다고 가정하면, 포인터를 따라가 첫 번째 History 레코드를 직접 찾는다. 해당 레코드를 처리하고, 그 레코드에 있는 포인터를 따라가서 History가 아닌 다른 학과 레코드가 나타날 때까지 다음 레코드를 찾는다.

위와 같이, 일반적으로 조밀 인덱스가 있을 때가 희소 인덱스보다 레코드를 더 빠르게 찾을 수 있다. 그러나 희소 인덱스는 더 적은 공간을 사용하거나, 삽입 및 삭제 시 유지 관리 비용이 더 적다는 장점이 있다. 따라서 접근 시간(access time)과 공간 오버헤드(space overhead) 사이에서 시스템 설계자가 균형(trade-off)을 선택해야 한다.