인덱스는 데이터베이스에서 효율적인 질의 처리를 위한 중요한 요소다. 인덱스가 없다면 질의에 필요한 몇 개의 레코드를 찾기 위해 테이블 전체를 스캔해야 한다. 인덱스는 기본적으로 두 가지 종류가 존재한다.

순서 인덱스(ordered index): 값에 대해 정렬된 순서로 되어 있다.
해시 인덱스(hash index): 버켓의 범위 안에서 값이 일정하게 분배로 되어 있다. 값이 할당되는 버켓은 해시 함수에 의해 결정된다.

인덱스 성능은 다음과 같은 요소로 평가된다.

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

순서 인덱스(ordered index)

순서 인덱스는 검색 키값을 정렬된 순서로 저장하고, 검색 키와 검색 키를 포함하는 레코드를 연계시킨다. 클러스터링 인덱스(clustering index)는 검색키를 기준으로 파일을 물리적으로 정렬한다. 클러스터링 인덱스는 primary index라고도 불린다. Clustering index의 검색키로 pk가 많이 사용되지만 필수는 아니다. 파일 순서와 다른 순서로 구성되는 검색 키의 인덱스를 비클러스터링 인덱스(nonclustering index) 또는 보조 인덱스(secondary index)라고 한다. 검색 키에 대해 clustering index를 가지는 파일을 인덱스 순차 파일(index-sequential file)이라 부른다. 이는 데이터베이스 시스템에서 사용된 가장 오래된 인덱스 구조 중 하나다.

Dense index, Sparse index

인덱스 레코드는 검색키 값과 포인터로 구성되어 있다. 포인터는 검색키에 대응되는 한 개 이상의 레코드에 대한 포인터다. 이 포인터는 디스크 블록 식별자와 블록 내에서 레코드 식별을 위한 디스크 블록 내의 오프셋으로 구성되어 있다. 순서 인덱스에는 두 가지 종류가 있다.

dense index: dense index의 index record에는 모든 검색키가 존재한다. Dense clustering index에 index record는 다음 항목을 포함한다.
- 검색키
- 검색키에 대응되는 첫 번째 레코드 값의 포인터.
  - clustering index라서 두 번째부터는 연속적으로 저장한다. dense secondary index는 같은 검색키를 가진 모든 레코드 목록을 저장한다.

dese clustering index

sparse index: 일부 검색 키만 index record로 가지고 있다. 오직 clustering index에서만 사용 가능하다. index record 구조는 dense index와 같다. 레코드를 찾을 때 찾고자 하는 검색키 보다 작거나 같으면서 가장 큰 검색키에 해당하는 index record를 찾는다. 그 후 해당 레코드를 시작으로 원하는 레코드를 찾을 때까지 포인터를 따라간다.

sparse clustering index 일반적으로 dense index가 sparse index보다 레코드 위치를 특정하는 속도가 빠르다. 그러나 sparse index는 dense index에 비해 더 적은 공간이 필요해서 삽입, 삭제 시에 비용이 적다는 이점이 있다. 최적화를 위한 접근 시간과 공간 부담 사이의 좋은 절충안은 블록 하나의 index record를 가지는 sparse index를 만드는 것이다. 데이터베이스 연산 중 디스크에서 메인 메모리로 블록을 가져오는 연산이 가장 비싸다. 반면 가져온 블록을 탐색하는 비용은 적다. 따라서 sparse index를 이런 식으로 사용하면 원하는 레코드가 위치한 블록을 메인 메모리에 위치시킬 수 있다.

다계층 인덱스 (multilevel index)

1,000,000개의 레코드를 가진 테이블에 dense index를 구축한다고 해보자. 이때, 인덱스 엔티티는 4KB 블록 하나에 100개씩 들어간다 가정한다. 그러면 인덱스는 10,000개의 블록을 차지한다. 레코드 수가 더 늘어나 100,000,000개가 된다면 인덱스는 4GB 공간을 차지한다. 이와 같이 인덱스가 비대해지면 DB는 인덱스 엔트리를 찾기 위해 여러 개의 디스크 블록을 읽어야 한다. 이진 검색으로 인덱스 파일 내의 엔트리 위치를 정한다면 log2(b)(b는 인덱스가 차지하는 블록 개수)가 필요하다. 읽어야 할 블록이 인접하지 않다면, 각 블록을 읽기 위해 random I/O가 필요하다. 만약 10,000개의 블록으로 구성된 인덱스를 사용한다면 총 14개의 블록을 읽어야 한다. 블록 한 번을 읽는데 10ms가 소요된다면 총 140ms, 즉 초당 7개의 인덱스만 읽을 수 있다. 또 한, 이진 검색은 오버플로 블록엔 해당이 안 되므로, 오버플로 블록이 존재한다면 더 많은 시간이 소요된다. 2-way sparse index 이 문제를 해결하기 위해 위와 같이 인덱스를 다른 순차 파일 처럼 취급한다. Outer index는 원래 인덱스인 inner index에 대한 sparse index이다. Outer index는 항상 정렬된 상태이다. 다계층 인덱스가 동작하는 방식은 다음과 같다.

Outer index에서 이진 검색을 사용해 원하는 레코드보다 작거나 같은 검색 키값 중 가장 큰 값을 가지는 레코드를 찾는다
Outer index에서 찾은 레코드가 가리키는 innter index block에 접근한다.
Innter index block을 스캔해 원하는 레코드보다 작거나 같은 검색 키값 중 가장 큰 값을 가지를 레코드를 찾는다.
찾은 레코드의 포인터가 원하는 레코를 포함하는 파일 블록을 가리킨다.

만약 outer index 역시 많은 공간을 차지해 메모리에 상주시킬 수 없다면, 또 다른 단계의 인덱스를 생성할 수 있다. 이런 식으로 두 개 이상의 단계를 가지는 인덱스를 다계층 인덱스라 한다. 다계층 인덱스는 메모리 인덱스에서 사용되는 이진 트리 같은 트리 구조와 밀접한 관련이 있다.

인덱스 갱신

사용되는 모든 인덱스는 어떤 레코드가 삽입, 삭제, 업데이트될 때마다 갱신되어야 한다. 레코드 갱신은 이전 레코드를 삭제하고 새로운 레코드 값이 삽입되는 방식으로 동작하며, 인덱스도 이에 따라 삭제되고 새로운 인덱스가 삽입된다. 즉, 인덱스에 대한 삽입과 삭제만 고려하면 된다. 다계층 인덱스가 아닌 인덱스의 갱신 알고리즘은 다음과 같다.

삽입

시스템은 삽입되는 레코드 검색 키값을 이용해 찾기를 수행한 뒤 다음과 같은 과정을 거친다.

dense index:
- 검색 키값이 인덱스에 없다면 시스템은 정당한 위치에 검색 키 값을 가지는 인덱스 엔트리를 삽입한다.
- 검색 키값이 존재한다면
  - 만약 인덱스 엔트리가 똑같은 키값을 가지는 모든 레코드를 가리키는 포인터를 저장하고 있다면 시스템은 인덱스 엔트리에 새로운 레코드에 대한 포인터를 추가한다.
  - 그렇지 않다면 인덱스 엔트리는 검색 키값을 가지는 첫 번째 레코드에 대한 포인터만 저장하고 있다. 따라서 시스템은 똑같은 검색 키값을 가지는 다른 레코드 뒤에 삽입된 레코드를 놓는다.
sparse index:
- 인덱스가 각 블록에 대한 엔트리를 저장한다고 가정한다.
- 시스템이 새로운 블록은 만든다면, 새로운 블록에 나타나는 첫 번째 검색 키 값을 인덱스에 삽입한다.
- 새로운 레코드가 블록 안에 있는 가장 작은 검색 키 값이면 시스템은 그 블록을 가리키고 있는 인덱스 엔트리를 갱신한다.
- 위 경우에 해당되지 않으면 인덱스를 바꾸지 않는다.
  삭제
  
  삭제할 레코드를 찾고 다음과 같은 과정을 거친다.
dense index:
- 삭제된 인덱스가 특정한 검색 키 값을 가지는 유일한 레코드라면 시스템은 인덱스부터 이와 대응되는 인덱스 엔트리를 삭제한다.
- 그렇지 않다면
  - 만약 인덱스 엔트리가 똑같은 검색 키 값을 가지는 모든 레코드를 가리키는 포인터를 저장한다면 시스템은 인덱스 레코드로부터 삭제된 레코드에 대한 포인터를 삭제한다.
  - 그렇지 않다면 인덱스 엔트리는 검색 키 값을 가지는 첫 번째 레코드에 대한 포인터만 저장하고 있다. 만약 삭제된 레코드가 검색 키 값을 가지는 첫 번째 레코드였다면 시스템은 인덱스 엔트리가 다음 레코드를 가리키게 갱신한다.
sparse index:
- 인덱스가 삭제된 레코드의 검색 키 값을 가지는 인텍스 엔트리를 포함하지 않는다면 아무런 작업도 하지 않는다.
- 그렇지 않다면
  - 만약 삭제된 레코드가 그 검색 키를 가지는 유일한 레코드라면, 시스템은 대응되는 인덱스 레코드를 다음 검색 검색 키를 위한 인덱스 레코드로 교체한다.
    - 다음 검색 키 값이 이미 인덱스 엔트리에 있다면 삭제된다.
  - 그렇지 않다면 검색 키 값을 위한 인덱스 엔트리는 삭제 대상인 레코드를 가리키고 있다. 따라서, 시스템은 인덱스 레코드가 똑같은 검색 키 값을 가지는 다음 레코드를 가리키게 갱신한다.

다계층 인덱스에선 위와 같은 과정은 가장 낮은 단계부터 실행하기를 반복하면서 인덱스를 갱신한다. 상위 단계의 인덱스 입장에서 하위 단계 인덱스는 그저 레코드를 담고 있는 파일이기 때문이다.

Secondary index

Secondary index는 모든 검색 키 값과 모든 레코드에 대한 포인터를 가지는 인덱스 엔트리로 된 dense index 여야한다. 검색 키에 대한 secondary index는 연속적인 값에 의해 가리켜지는 레코드가 연속적으로 저장되어 있지 않기 때문이다. 레코드는 secondary index에 대한 검색 키가 아닌 clustering index의 검색 키에 의해 순서대로 저장된다. 테이블에 동일한 검색 키 값을 가지는 레코드가 두 개 이상 존재한다면, 이런 검색 키를 비고유 검색 키(nonunique search key)라 한다. 비고유 검색 키에 대한 secondary index는 레코드를 직접 가리키는 대신 인덱스에 있는 각 포인터는 그 파일에 대한 포인터를 담는 버켓을 가리킨다. 이 방법은 다음과 같은 단점을 지닌다

random I/O 작업이 필요한 간접 참조로 인해 인덱스 접근 시간이 더 오래 걸린다.
키에 중복의 거의 없다면 버켓으로 인해 공간 낭비가 발생한다.

Secondary index는 clustering index의 검색 키가 아닌 다른 키를 사용하는 쿼리 성능을 향상시킨다. 그러나 secondary index는 DB 변경 시 부하를 가중시킨다. 따라서 검색만을 위한 쿼리와 데이터 변경의 빈도에 대한 평가에 기초해 올바른 secondary index를 결정해야 한다.

다중 키상의 인덱스(composite search key)

이전까지 설명에선 검색 키는 하나의 속성만 가졌다. 그러나 검색 키는 한 개 이상의 속성을 가질 수도 있다. 두 개 이상의 속성을 가지는 검색 키를 복합 검색 키(composite search key)라고 한다. 복합 검색 키 인덱스 구조는 다른 인덱스 구조와 같다. 유일한 차이점은 속성이 목록으로 되어 있다는 것이다. 목록으로 된 검색 키 순서는 사전적 순서(lexicographic ordering)이다.

플래시 저장 장치에서 인덱싱

표준 B+-tree index는 플래시 기반 SSD에서도 사용 가능하며 준수한 갱신 성능을 보여준다. 또 한, 디스크에 비해 크게 향상된 검색 성능을 제공한다. Random I/O 작업에서 SSD는 자기 디스크 보다 훨씬 빠르다. 디스크 Random input 소요 시간은 5~10ms 인것에 비해, SSD는 20~100μs가 소요된다. 다만, 플래시 저장 장치는 쓰기 작업이 복잡하다. 플래시 저장 장치는 디스크와 달리 물리적으로 데이터에 대한 in-place 갱신을 허용하지 않는다. 모든 갱신 작업은 해당 페이지의 복사, 쓰기에 의해 수행된다. 즉, 우선 갱신 대상인 페이지가 존재하는 블록에 속한 페이지들을 새로운 블록에 복사한다. 그 후 블록 전체를 새로 쓴다. 이 때, 한 개의 블록을 지우는 데 2~5ms가 소요되고 새로운 페이지 쓰기에는 20~100ms가 소요된다. 플래시 페이지 크기는 디스크 블록 크기보다 작기 때문에 B+-tree의 노드 크기가 디스크를 사용할 때보다 작다. 만약 노드 크기가 페이지 크기보다 크다면, 노드 갱신 시 여러번의 페이지 쓰기가 발생한다. 이런 이유 때문에 트리 높이가 증가하고, 데이터 접근에 더 많은 I/O 연산이 필요하다. 그러나 플래시 저장 장치는 random output이 디스크에 비해 훨씬 빠르기 때문에 높이 증가가 성능에 크게 미치진 않는다.

DB indexing