Indexing(1)

1. 기본 개념

데이터베이스 시스템의 index는 도서관에서 사용되는 책의 index와 같은 역할을 한다. 예를 들어, 주어진 ID를 가진 student 레코드를 검색하기 위해 데이터베이스 시스템은 index를 이용해 대응되는 레코드가 어느 디스크 블록에 있는지 찾은 후에 student 레코드를 얻기 위해 해당 블록을 가져온다.
학생 ID 목록을 정렬된 순서로 유지하는 것은 매우 큰 데이터베이스에서는 적합하지 않다. 정렬된 순서로 index를 유지하면 검색 시간을 줄일 수 있지만, 학생을 찾는 것이 여전히 시간을 소비하는 작업이며, index 자체가 매우 크기 때문이다. 따라서 이러한 방식 대신 더 복잡한 index 기술이 사용된다.

index의 종류

• 순서(Ordered) index : 값에 대해 정렬된 순서로 되어 있다.
• 해시(Hash) index : bucket의 범위 안에서 값이 일정하게 분배되어 있다. 값이 할당되는 bucket은 hash 함수에 의해 결정된다.

indexing 전에 고려해야 하는 것들

• 액세스 형태(Access type) : 액세스 형태는 특정한 속성의 값을 가진 레코드나 특정한 범위에 들어가는 속성의 값을 가지는 레코드를 찾은 것을 포함한다.
• 액세스 시간(Access time) : 특정한 데이터 항목이나 항목의 집합을 찾는 데 걸리는 시간
• 삽입 시간(Insertion time) : 새로운 데이터 항목을 삽입하는 데 걸리는 시간. 즉, 새로운 데이터 항목을 삽입하기 위한 정확한 위치를 찾는 데 걸리는 시간 + index 구조를 갱신하는 데 걸리는 시간
• 삭제 시간(Deletion time) : 데이터 항목을 삭제하는 데 걸리는 시간. 즉, 삭제될 항목을 찾는 데 걸리는 시간 + index 구조를 갱신하는 데 걸리는 시간
• 공간 부담(Space overhead) : index 구조에 의해 사용되는 부가적인 공간

search key

하나의 파일에 대해 하나 이상의 index를 필요로 하는 경우가 종종 있다. 예를 들어, 저자, 주제, 제목 등으로 책을 검색할 수 있다.
한 파일에서 레코드를 찾는 데 사용되는 속성이나 속성들의 집합을 검색 키(search key)라고 한다. 한 파일에 대해 여러 개의 index가 있다면, 검색 키도 여러 개가 있는 것이다.

2. 순서 index

파일 안에 있는 레코드에 대한 임의 접근(random access)을 빨리 하기 위해서 index 구조를 이용할 수 있다. 각 index 구조는 특정 search key와 관련이 있다. 순서 index는 search key의 값을 정렬된 순서로 저장하고, search key - search key 포함 레코드 사이의 연계를 만들어낸다.

도서관에 있는 책이 Dewey 십진수 같은 특정 속성에 따라 정렬되어 있듯이 index 파일의 레코드도 특정 속성에 의해 정렬된 순서로 저장될 수 있다. 레코드 포함 파일이 연속적인 순서로 되어 있다면 클러스터링(clustering) index는 그 파일을 연속적인 순서로 정의한 속성을 search key로 사용하는 index이다. 클러스터링 index는 primary index로도 불린다. 클러스터링 index의 search key는 primary key인 경우가 많지만 반드시 그럴 필요는 없다.

파일의 연속적인 순서와 다른 순서로 구성되는 search key의 index를 nonclustering index라고 부른다.

search key에 대해 primary index를 가지는 파일을 인덱스-순차 파일(index-sequential files)이라고 부른다. 아래 그림은 instructor 레코드의 순차 파일을 보여준다. search key로 사용된 교수 ID에 대해 그 순서에 따라 저장되어 있다.

1) 밀집 index & 희소 index

index 레코드, 즉 index entry는 (search key 값 + pointer)로 구성되어 있다.

여기서 포인터는 이것을 search key 값으로 가지는 한 개 이상의 레코드에 대한 포인터이다. 포인터는 (디스크 블록 식별자 + 블록 안에서 레코드를 구별하기 위한 블록 내부 offset)으로 구성되어 있다.

우리가 사용할 수 있는 순서 index는 두 가지 형태가 있다.

• 밀집(Dense) index : 밀집 index에서 index entry는 파일에 있는 모든 search key 값에 대해 나타난다.
  • 밀집 clustering index : index 레코드가 (search key 값 + 첫 번째 데이터 레코드에 대한 pointer)를 포함한다. 똑같은 search key 값을 가진 나머지 레코드들은 첫 번째 레코드 이후부터 연속적으로 저장된다. 이는 clustering index여서 레코드들이 동일한 search key로 정렬되었기 때문이다.
  • 밀집 nonclustering index : index 레코드가 (search key 값 + 모든 데이터 레코드에 대한 pointer 목록)을 포함한다.

• 희소(Sparse) index : 희소 index에서 index entry는 search key 값 중 몇 개만 나타난다. 희소 index는 index가 clustering index인 경우에만 사용할 수 있다. 레코드를 찾기 위해서는 찾고자 하는 search key 값보다 작거나 같은 것 중 가장 큰 값을 index entry에서 찾아야 한다. 그리고 그 pointer가 가리키는 레코드를 시작으로 원하는 레코드를 찾을 때까지 따라가면 된다.

그림 14.2와 14.3은 instructor 파일에 대한 밀집 index와 희소 index를 각각 보여준다. ID가 "22222"인 instructor의 레코드를 찾는다고 가정하자.

밀집 index를 사용하면 희망하는 레코드에 대한 포인터를 직접 따라간다. ID가 primary key이기 때문에 희망하는 레코드는 반드시 존재하며 검색이 완료된다.

희소 index를 사용하면 "22222"를 위한 index entry를 찾을 수 없다. "22222" 앞의 entry가 "10101"이기 때문에 이 포인터를 따라가고 희망하는 레코드를 찾을 때까지 연속적인 순서로 파일을 읽어나가면 된다.

아래 예시는 search key 값이 primary key가 아닌 경우이다. 그림 14.4는 search key가 dept_name인 instructor 파일에 대한 밀집 clustering index를 보여준다. 따라서 instructor 파일이 ID 대신 search key인 dept_name으로 정렬되어 있다.

여기서 역사학과 레코드를 찾을 때는 index entry에서 맞는 pointer를 찾고 그 pointer로 찾은 레코드부터 역사학과가 아닌 레코드가 나올 때까지 순차적으로 레코드를 얻으면 된다.

trade-off

앞에서 보았듯이 일반적으로 레코드의 위치를 정하기 위해서는, 즉 알맞은 pointer를 찾기 위해서는 희소 index보다 밀집 index를 사용하면 더 빠르다. 그러나 희소 index는 밀집 index보다 더 적은 공간을 필요로 해서 삽입과 삭제에 대한 유지 부담이 더 적다는 점이 있다.

시스템 디자이너는 access time과 space overhead 사이에서 조건에 맞게 잘 조합해야 한다. 좋은 절충안은 블록당 하나의 index entry를 가지는 희소 index를 만드는 것이다. 그 이유는 데이터베이스 요구를 처리하는 데 드는 비용 중 지배적인 것은 디스크에서 메인 메모리로 블록을 가져오는 데 걸리는 시간이기 때문이다. 일단 블록을 가져오면, 전체 블록을 훑어보는 데 걸리는 시간은 큰 문제가 아니다.

2) 다단계 index

index가 메인 메모리에 유지될 만큼 충분히 크기가 작다면, entry를 찾는 데 걸리는 검색 시간은 짧다. 하지만 전체 index가 메모리에 유지될 수 없을 만큼 크다면 필요할 때마다 index 블록을 디스크로부터 가져와야 한다. 그 다음에 index에서 entry를 찾기 위해 여러 개의 디스크 블록을 읽어야 한다.

binary search는 index 파일 내의 entry의 위치를 정하기 위해 사용될 수 있지만 여전히 비용이 많이 든다. index가 b개의 블록을 차지한다면, binary search는 log b 만큼이나 많은 블록을 읽어야 한다. 10000개 블록 index에서 binary search는 14개의 블록을 읽어야 한다. 한 개의 블록을 읽는 데 10ms가 걸리는 디스크 시스템에서는 검색하는 데 140ms가 걸린다. 이는 결국 1초에 단 7개의 index만 검색할 수 있는 정도인 것이다.

이런 문제를 해결하기 위해 index를 다른 순차 파일처럼 취급해서 그림 14.5처럼 내부 index라고 불리는 원래의 primary index에 대한 희소 외부 index를 구성한다.

레코드의 위치를 찾기 위해 먼저 외부 index 상에서 binary search를 이용해서 원하는 레코드보다 작거나 같은 search key 값 중에서 가장 큰 값을 가지는 레코드를 찾을 수 있다. 이때의 레코드 포인터는 내부 index 블록을 가리킨다. 이 포인터가 가리키는 블록을 스캔하여 원하는 레코드보다 작거나 같은 search key 값 중에서 가장 큰 값을 가지는 레코드를 찾는다. 이 레코드에 있는 포인터는 찾고자 하는 레코드를 포함하는 파일의 블록을 가리킨다.

이 예제에서 외부 index는 오직 100개의 블록을 사용한다고 하자. 이때 외부 index가 이미 메인 메모리에 있다면 다단계의 index를 사용하면 binary search에서 14번 index 블록을 읽은 것과 달리 오직 한 index 블록만 읽는다. 결과적으로 초당 14번의 index 검색을 할 수 있다.

만일 파일이 매우 크다면 외부 index도 너무 커져서 메인 메모리에 다 넣을 수가 없다. 이런 경우에는 또 다른 단계의 index를 생성할 수 있다. 즉, 필요한 만큼 여러 번 반복할 수 있고 이처럼 2개 이상의 단계를 가지는 index를 다단계(multilevel) index라고 한다. 다단계 index로 레코드를 찾는 것은 binary search로 레코드를 찾는 것보다 상당히 적은 입출력 연산을 필요로 한다.

3) index 갱신

사용되는 index의 형태와 상관없이 모든 index는 어떤 레코드가 파일에 삽입되거나 파일로부터 삭제될 때마다 갱신되어야 한다. 또한 레코드가 갱신된 경우에는 갱신에 영향을 받는 search key를 소유한 모든 index가 갱신되어야 한다. 예를 들어, 교수의 소속 학과가 변경되었으면 instructor 의 dept_name 속성에 대한 index 역시 갱신되어야 한다.

삽입

시스템은 삽입되는 레코드의 search key 값을 사용해서 찾기를 수행한다. 그 이후 동작은 index가 밀집이냐 희소냐에 달려있다.

• 밀집 index
  1. search key 값이 index에 없다면 시스템은 index의 적당한 위치에 search key 값을 가지는 index entry를 삽입한다.
  2. search key 값이 index에 있다면 다음 동작을 따른다.
     a. 만약 index entry가 똑같은 search key 값을 가지는 모든 레코드를 가리키는 포인터를 저장하고 있다면 시스템은 index entry에 새로운 레코드에 대한 포인터를 추가한다.
     b. 그렇지 않다면 index entry는 search key 값을 가지는 첫 번째 레코드에 대한 포인터만 저장하고 있다. 따라서 시스템은 똑같은 search key 값을 가지는 다른 레코드들 뒤에 삽입될 레코드를 놓는다.
• 희소 index
  index가 각 블록에 대한 entry를 저장한다고 가정한다.
  1. 시스템이 새로운 블록을 생성하는 경우: 새로운 블록에 나타나는 첫 번째 search key 값을 index에 삽입한다.
  2. 시스템이 새로운 레코드만을 삽입하는 경우
     a. 새로운 레코드가 그 블록 내에서 가장 작은 search key 값이라면 그 블록을 가리키는 index entry를 갱신한다.
     b. 그렇지 않다면 index를 바꿀 필요가 없다.

삭제

레코드를 삭제하기 위해 시스템은 먼저 삭제될 레코드를 찾는다. 그 다음 동작은 index가 밀집이냐 희소냐에 달려있다.

• 밀집 index
  1. 삭제된 index가 특정한 search key 값을 가지는 유일한 레코드라면 시스템은 이에 대응되는 index entry를 삭제한다.
  2. 그렇지 않다면 다음 동작을 따른다.
     a. 만약 index entry가 똑같은 search key 값을 가지는 모든 레코드를 가리키는 포인터를 저장하고 있다면 시스템은 index 레코드로부터 삭제된 레코드에 대한 포인터를 삭제한다.
     b. 그렇지 않다면, 삭제된 레코드가 search key 값을 가지는 첫 번째 레코드였을 경우 시스템은 index entry가 다음 레코드를 가리키도록 포인터를 갱신한다.
• 희소 index
  1. index가 삭제된 레코드의 search key 값을 가지는 index entry를 포함하고 있지 않다면 index에 대해 해야할 것은 없다.
  2. 그렇지 않다면 다음 동작을 따른다.
     a. 삭제된 레코드가 그 search key를 가지는 유일한 레코드였다면 시스템은 대응되는 index 레코드를 다음 search key 값을 위한 index 레코드로 교체한다. 다음 search key 값이 이미 index entry에 있다면 이 entry는 교체되는 대신 삭제된다.
     b. 그렇지 않다면 index 레코드가 똑같은 search key 값을 가지는 다음 레코드를 가리키도록 갱신한다.

참고

Database System Concepts 11장