책의 목차를 보면 특정 내용을 보기 위해서 어느 페이지로 가야하는지 적혀있다.
데이터베이스의 인덱스는 기본적으로 이러한 목차와 비슷한 역할을 수행한다.
이러한 인덱스를 자세하게 논하기 위해서는, 데이터베이스에서 릴레이션을 저장하는 파일의 구조를 단순하게나마 알고있어야 한다.
위의 이미지가 기본적인 파일의 구조이다. 하나의 파일은 특정 크기의 블록들로 나뉘어져 있고, 하나의 릴레이션에 해당하는 레코드들이 하나의 파일에 저장된다. 그리고 파일의 시작부분에는 파일 헤더가 쓰여지는데, 이는 파일의 메타데이터를 저장하는 구간이다. 이러한 형태로 파일 데이터가 시스템의 디스크에 쓰여진다.
그렇다면 인덱스란 무엇인가?
인덱스의 정의는 다음과 같다.
탐색 키를 가진 레코드의 빠른 검색을 위해 <탐색키, 레코드 포인터>의 쌍을 관리하는 구조
그림으로 표현하면 다음과 같다.
레코드들을 포함한 블록이 하나의 파일에 쓰여졌듯이, 인덱스 또한 별도의 자료구조에 저장되어 별개의 파일로 쓰여진다. 즉, 인덱스를 거쳐서 실제 레코드의 데이터를 조회하려면 최소 2회 디스크의 블록에 접근해야 한다.
다만, 인덱스는 키값과 레코드의 메모리 주소만 저장하므로 실제 데이터 파일에 비해 그 크기가 훨씬 작다.
이제 인덱스의 종류에 대해 알아보자.
1. 기본 인덱스
우선 기본 인덱스이다. 이 인덱스는 탐색 키가 릴레이션의 기본 키인 인덱스를 뜻한다. 참고로, 탐색 키는 릴레이션에서 인덱스가 정의된 필드를 의미한다. 탐색키는 각 튜플마다 반드시 고유하지는 않다.
기본 인덱스는 기본 키의 값에 따라 정렬된 데이터 파일에 대해 정의될 수 있으며, 흔히 희소 인덱스의 형태를 가진다. (희소 인덱스에 대해서는 후술한다.)
2. 클러스터링 인덱스
클러스터링 인덱스 또한 탐색 키에 의해 정렬된 데이터 파일에 대해 정의된다.
클러스터링 인덱스는 개별적인 탐색 키마다 고유한 인덱스 엔트리를 가진다. (인덱스 엔트리란, 각 키 값마다 생성된 인덱스 레코드를 의미한다.)
범위 질의에 유용한데, 우선 범위의 시작값을 인덱스 엔트리에서 찾고, 그 시작 인덱스 엔트리를 차례차례 따라가면서 범위에 해당하는 값들을 찾을때 데이터 블록 참조 횟수가 최소화되기 때문이다.
다단계 인덱스를 구축할 경우, 보통 B+tree 자료구조를 이용하는데 이 과정에서 클러스터링 인덱스를 사용할 경우 데이터 블록 참조 횟수가 더욱 줄어들 수 있다. 이는 후술한다.
3. 보조 인덱스
한 파일은 기껏해야 하나의 탐색 키에 대해서만 정렬될 수 있다.
그런데, 앞서 살펴보았던 클러스터링 인덱스, 기본 인덱스와는 다르게, 보조 인덱스는 탐색 키 값에 따라 정렬되지 않은 데이터 파일에 대해서도 정의될 수 있다.
따라서 보조 인덱스는 보통 밀집 인덱스이므로, 기본 인덱스나 클러스터링 인덱스 처럼 희소 인덱스를 사용할 때보다 특정 레코드를 검색하기 위해 더 많은 데이터 블록 접근이 발생할 수 있다. 데이터 파일의 레코드들이 정렬되어 있지 않기때문에, 같이 검색될 확률이 높은 레코드들이 서로 멀리 떨어져있는 블록에 저장될 수 있기 때문이다. (밀집 인덱스일 경우 하나의 레코드마다 하나의 인덱스 엔트리가 생성된다.)
4. 희소 인덱스 vs 밀집 인덱스
희소 인덱스는 각 데이터 블록 마다 루트 앵커 (데이터 블록에 최초로 존재하는 레코드의 탐색 키 값)에 해당하는 하나의 레코드에 대해서 인덱스 엔트리를 포함하는 인덱스이다.
반면에 밀집 인덱스는 하나의 레코드마다 하나의 인덱스 엔트리를 대응시켜 포함한다.
데이터 블록의 크기가 하나의 레코드 크기보다 훨씬 큰 보통의 경우에는 희소 인덱스 엔트리 수가 밀집 인덱스 엔트리 수에 비해 훨씬 적다.
희소 인덱스는 대부분의 질의에서 밀집 인덱스에 비해 유리하나, count와 같이 실제 데이터가 저장된 레코드를 참조할 필요가 없는 경우, 밀집 인덱스의 인덱스 레코드만 조회하고도 결과를 낼 수 있으므로, 이런 경우에는 밀집 인덱스가 유리하다.
마무리
여기까지 단일 단계 인덱스를 알아보았다.
아차. 단일 단계 인덱스가 무엇인지를 서술하지 않았다.
단일 단계 인덱스는 말 그대로 인덱스가 하나의 계층으로만 이루어진 경우를 뜻한다.
인덱스 자체가 매우 클 경우에는 그 인덱스를 탐색하는데에도 많은 시간이 걸릴 수 있는데, 이 경우 다단계 인덱스를 생성하여 인덱스를 여러 계층으로 쪼갤 수 있다.
다음 게시글에서 다단계 인덱스에 대해 알아보도록 한다.
