'인덱스(Index)', 즉 '색인(索引)'은 단어 등을 찾기쉽게 어느 곳에 있는지 특정 순서대로 정리해놓은 것 입니다. 인덱스가 있으면 처음부터 쭉 모든 부분을 찾아보는 대신 필요한 부분을 바로 찾을 수 있습니다.
데이터베이스에서 질의문을 사용하여 특정 데이터를 찾을 때, 데이터가 적은 경우에는 상관이없지만, 그 양이 방대하여 매우 많은 데이터에서 일일이 질의문을 만족하는 데이터를 찾을 경우에는 상당히 많은 시간이 필요할 것 입니다. 이런 경우에 인덱스를 활용하면 빠르게 필요한 데이터에 접근할 수 있습니다. 하지만 인덱스도 저장 공간을 차지하기때문에, 과도한 인덱스의 생성은 저장 공간을 불필요하게 차지하고, 성능을 오히려 떨어트릴 수 있습니다.
순서 인덱스(Ordered Index)
'순서 인덱스'는 '탐색키(search key : 수퍼키, 후보키 등의 키가 아닌, 파일에서 투플을 찾을 때 이용하는 컬럼)' 값을 기준으로 정렬된 '순차 파일(sequential file)'에서 특정 투플에 '임의 접근(random access)'을 가능하게합니다.
순서 인덱스는 '인덱스 엔트리(index entry)'를 가지는데, 인덱스 엔트리는 각 투플보다 용량이 작기때문에 탐색시 메모리에서 인덱스 엔트리를 활용하여 더 빠르게 탐색이 가능합니다. 인덱스 엔트리는 탐색키값과 포인터(Block ID와 Offset으로 구성)로 구성됩니다.
※ 클러스터형 인덱스(Clustered Index) : 사전처럼 전체 데이터가 순서대로 저장돼있는 인덱스로, 릴레이션 당 하나만 생성이 가능합니다. 기본키가 지정되었다면 자동으로 생성됩니다.
※ 보조 인덱스(Secondary Index) : 색인 부분이 따로 존재하는 책처럼 구성된 인덱스로, 릴레이션 당 여러개 생성이 가능합니다.
※ 밀집 인덱스(Dense Index) : 모든 탐색키가 인덱스 엔트리를 가집니다. 따라서 인덱스 엔트리의 포인터를 따라 전체 탐색을 할 수 있습니다.
※ 희소 인덱스(Sparse Index) : 일부 탐색키만 인덱스 엔트리를 가집니다. 따라서 인덱스 엔트리의 탐색키값에서 탐색하려는 값보다 작거나 같은 값 중 가장 큰 값을 찾은 후 값이 일치하면 탐색을 종료하고, 일치하지않으면 해당 값에서부터 순차적으로 투플을 읽어 일치하는 투플을 찾습니다.
※ 다단계 인덱스 : 밀집 인덱스와 희소 인덱스의 장점을 이용하여, 투플에 직접 대응되는 밀집 인덱스를 내부 인덱스로, 그 내부 인덱스에 대응되는 희소 인덱스를 외부 인덱스로 하여 다단계로 인덱스를 형성합니다. 따라서 다단계 인덱스는 2개 이상의 단계로 구성됩니다.
B+ 트리 인덱스
'B+ 트리'는 '루트 노드(root node)', '중간 노드(internal node)', '단말 노드(leaf node)'로 구성됩니다.
루트 노드는 최상위 노드이며, 단말 노드는 모든 탐색키 값이 정렬되어 연결 리스트 형태로 존재하는 '순차 세트(ordered set)'로 구성되어있습니다. 중간 노드는 이들을 제외한 그 사이에 위치한 모든 노드들이며, 루트 노드와 중간 노드를 묶어 '인덱스 세트(index set)'라고 합니다.
'B+ 트리 인덱스'는 이러한 B+ 트리를 활용한 인덱스이며, 상용 DBMS에서 가장 많이 사용되는 인덱스 중 하나입니다.
해시 인덱스(Hash Index)
'해시 함수(hash function)'는 탐색키를 버킷에 '매핑(mapping)' 시키는 함수로, 각 버킷(투플이 저장되는 저장 공간 단위)'에 거의 동일한 수의 투플을 분배시키는 것이 가장 이상적인 해시 함수입니다.
서로 다른 투플이 같은 버킷에 분배되는 것을 '충돌(collision)'이라고하고, 이때 같은 버킷에 분배된 투플을 '동거자(synonyms)'라고합니다.
버킷에 빈 공간이 없을 때 충돌이 생기면 '오버플로우(overflow)'가 발생하는데, 대안으로 다른 버킷을 따로 지정하거나, 다음 버킷에 저장되게하는 등의 조치가 필요합니다.
'해시 인덱스'는 이러한 해시 함수를 활용하여 인덱스 엔트리를 버킷에 저장하는 인덱스입니다.
비트맵 인덱스(Bitmap Index)
'비트맵 인덱스'는 성별, 성적처럼, 그 범위가 수(數)적으로 넓은 범위를 가지는 값이 아닌, 비교적 좁은 범위의 값을 가져, 중복이 많이 발생하는 컬럼에 효과적으로 사용할 수 있는 인덱스입니다.
예를 들어 성별이 남자인 투플을 대상으로 질의를 한다면, 남자인 투플은 '1'의 비트값을, 여자인 투플은 '0'의 비트값을 지정하는 식으로 '비트맵'을 생성하여 효율적으로 탐색할 수 있는 인덱스입니다.
