물리적 데이터베이스 설계에 대하여(3)

05.  단일 단계 인덱스란?

만일 파일에 대한 접근이 일괄 방식으로 순차 접근만 한다면 어떤 종류의 인덱스도 거의 불필요합니다. 인덱스 된 순차 파일은 인덱스를 통해서 임의의 레코드를 접근할 수 있는 파일입니다. 인덱스 자체가 파일을 의미하므로 '인덱스 파일'이라고 할 필요는 없습니다.

단일 단계 인덱스의 각 엔트리는

<탐색 키, 레코드에 대한 포인터>

로 이루어집니다. 엔트리들은 탐색 키 값의 오름차순으로 정렬됩니다. 인덱스는 DBMS가 파일 내의 특정 레코드들을 빠르게 찾을 수 있도록 하는 데이터 구조이므로 인덱스를 통하여 질의를 수행하면 응답 시간이 향상됩니다.

디스크 접근 시간이 주기억 장치 접근 시간에 비해서 매우 크고 대부분의 데이터베이스 응용에서 디스크 접근을 많이 요구하므로, 인덱스를 통해 디스크 접근 횟수를 줄이면 데이터베이스의 성능을 크게 향상시킬 수 있습니다.

인덱스를 통한 레코드 검색

인덱스는 데이터 파일과는 별도의 파일에 저장되기 때문에 임의 접근을 필요로 하는 응용에 적합합니다. 데이터 파일에 들어 있는 여러 애트리뷰트들 중에서 탐색 키에 해당하는 일부 애트리뷰트만 인덱스에 포함되기 때문에 인덱스의 크기는 데이터 파일의 크기에 비해 훨씬 작으며, 흔히 데이터 파일 크기의 10~20% 정도입니다. 또한 하나의 파일에 여러 개의 인덱스들을 정의할 수 있습니다.

EMPLOYEE 파일의 EMPNO 에 정의된 인덱스

인덱스가 정의된 필드를 탐색 키라고 부릅니다. 탐색 키의 값들은 후보 키처럼 각 투플마다 반드시 고유하지는 않습니다. 즉 후보 키와 달리 두 개 이상의 투플들이 동일한 탐색 키 값을 가질 수 있습니다. 탐색 키라는 용어에 포함된 '키'를 지금까지 사용해온 '키'와 혼동하면 안 됩니다. 키를 구성하는 애트리뷰트뿐만 아니라 어떤 애트리뷰트도 탐색 키로 사용될 수 있습니다.

인덱스가 데이터 파일보다 크기가 작으므로 인덱스를 순차적으로 찾는 시간은 데이터 파일을 순차적으로 탐색하는 시간보다 적게 걸립니다. 더욱이 인덱스의 엔트리들은 탐색 키 값의 오름차순으로 저장되어 있으므로 이진 탐색을 이용할 수도 있습니다. 이진 탐색을 이용하면 탐색 시간이 훨씬 적게 소요됩니다.

인덱스를 사용하면 한 파일에서 특정 레코드를 찾기 위해서 모든 레코드들을 탐색할 필요가 없으므로 특히 파일이 매우 클 경우에 유용합니다. 인덱스 전체를 주기억 장치에 유지할 수 있을 때 특히 인덱스가 성능에 도움이 되기 때문입니다. 어떤 레코드를 찾는 질의도 한 번의 디스크 접근만 필요로 합니다. 인덱스 유형은 크게 단일 단계 인덱스와 다단계 인덱스로 구분하며 B+-트리 인덱스는 관계 DBMS에서 가장 널리 사용되는 다단계 인덱스 구조입니다.

▶︎ 기본 인덱스(primary index)

탐색 키가 데이터 파일의 기본 키인 인덱스를 기본 인덱스라고 부릅니다. 레코드들은 기본 키의 값에 따라 클러스터링 됩니다. 기본 인덱스는 기본 키의 값에 따라 정렬된 데이터 파일에 대해 정의되며 기본 인덱스는 희소 인덱스로 유지할 수 있습니다. 희소 인덱스는 데이터 파일을 구성하는 각 블록마다 하나의 탐색 키 값이 인덱스 엔트리에 포함됩니다. 일반적으로 각 인덱스 엔트리는 블록 내의 첫 번째 레코드의 키 값(블록 앵커(block anchor)라고 부름)을 갖습니다.

각 릴레이션마다 최대한 한 개의 기본 인덱스를 가질 수 있으며 데이터 파일의 레코드들은 저장하는 블록마다 두 개의 레코드가 들어가 있습니다. 이에 반해서 인덱스 엔트리들을 저장하고 있는 블록마다 네 개의 엔트리들이 들어가 있습니다. 실제의 경우에는 데이터 블록당 레코드 수와 인덱스 블록당 엔트리 수는 훨씬 더 차이가 납니다.

▶︎ 클러스터링 인덱스(clustering index)

클러스터링 인덱스는 탐색 키 값에 따라 정렬된 데이터 파일에 대해 정의됩니다. 각 데이터 블록 대신에 각각 상이한 키 값마다 하나의 인덱스 엔트리가 인덱스에 포함되어 그 탐색 키 값을 갖는 첫 번째 레코드의 주소(또는 레코드가 들어 있는 블록의 주소)를 가리킵니다. 클러스터링 인덱스는 범위 질의에 유용합니다. 범위의 시작 값에 해당하는 인덱스 엔트리를 먼저 찾은 후 클러스터링 인덱스에서는 인접한 탐색 키 값을 갖는 레코드들이 디스크에서 가깝게 저장되어 있으므로 범위에 속하는 인덱스 엔트리들을 따라가면서 레코드들을 검색할 때 디스크에서 읽어오는 블록 수가 최소화됩니다. 어떤 인덱스 엔트리에서 참조되는 데이터 블록을 읽어오면 그 데이터 블록에 들어 있는 대부분의 레코드들은 범위를 만족합니다.

▶︎ 보조 인덱스(secondary index)

한 파일은 기껏해야 한 가지 필드들의 조합에 대해서만 정렬될 수 있습니다. 즉 EMPLOYEE파일을 EMPNO에 대해서 정렬하는 동시에 TITLE에 대해서도 정렬할 수 없습니다. 만일 EMPLOYEE파일이 EMPNO 애트리뷰트의 값이 증가하는 순으로 정렬되어 있는데, TITLE을 WHERE절에 사용하여 레코드들을 검색하기 위해서는 TITLE에 대해 인덱스를 정의해야 합니다. 보조 인덱스는 탐색 키 값에 따라 정렬되지 않은 데이터 파일에 대해 정의됩니다. 하지만 인덱스에서 탐색 키 값들은 물론 정렬되어 있습니다. 흔히 한 릴레이션에 여러 개의 인덱스를 정의해야 할 필요성이 있습니다. 보조 인덱스는 기본 인덱스처럼 레코드를 빠르게 찾는다는 동일한 목적을 달성합니다. 보조 인덱스는 일반적으로 밀접 인덱스이므로 같은 수의 레코드들을 접근할 때 보조 인덱스를 통하면 기본 인덱스를 통하는 경우보다 디스크 접근 횟수가 증가할 수 있습니다. 또한 기본 인덱스를 사용한 순차 접근은 효율적이지만 보조 인덱스를 사용한 순차 접근은 비효율적입니다. 각 레코드를 접근하기 위해서는 디스크에서 블록을 읽어올 필요가 있습니다.

▶︎ 희소 인덱스(sparse index)

희소 인덱스는 일부 키 값에 대해서만 인덱스에 엔트리를 유지하는 인덱스를 말합니다. 일반적으로 각 블록마다 한 개의 탐색 키 값이 인덱스 엔트리에 포함됩니다.

▶︎ 밀집 인덱스(dense index)

밀집 인덱스는 각 레코드의 키 값에 대해서 인덱스에 엔트리를 유지하는 인덱스를 말합니다.

 

 

 

[IT 공부하기/데이터베이스] - 물리적 데이터베이스 설계에 대하여(4)

물리적 데이터베이스 설계에 대하여(4)