[데이터베이스 시스템] 인덱스

인덱스

• 데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 기법
• DMBS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조
• 인덱싱 : 인덱스를 구성하고 생성하는 작업
• 탐색키 : 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

인덱스의 평가 기준

• 접근 시간 : 사용자가 원하는 데이터를 찾는 데 걸리는 시간
• 유지 비용 : 데이터 삽입 및 삭제 연산으로 인한 인덱스 구조 갱신 비용
• 공간 비용 : 인덱스 구조에 사용되는 부가적인 공간 비용

인덱스의 종류

• 순서 인덱스 : 탐색키값에 대해 정렬된 순서 구조
• 해시 인덱스 : 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수에 의해 어떤 값이 어떤 버킷에 할당되는지 결정

순서 인덱스

• 탐색키값으로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 임의 접근이 가능
• 탐색키를 정렬하여 저장하고 해당 레코드와 연계시킨다.
• 클러스터드 인덱스 : 인덱스의 순서와 레코드가 저장된 순서가 동일한 인덱스

밀집 인덱스

• 인덱스 엔트리 : <탐색키값, 포인터> 쌍으로 구성
  • 포인터는 식별자와 오프셋으로 구성
• 모든 탐색키값에 대해 인덱스 엔트리를 생성한다.

희소 인덱스

• 일부의 탐색키값에 대해서만 인덱스 엔트리를 생성한다.

다단계 인덱스

• 밀집 인덱스와 희소 인덱스의 장단점을 결합
• 여러 단계에 걸쳐 인덱스를 구성
• 내부 인덱스는 밀집 인덱스로, 외부 인덱스는 희소 인덱스로 구성

B+- 트리 인덱스

• 이진 탐색 트리 형태
• 루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리

B+- 트리의 구성

• 루트는 0,2 또는 [차수/2]에서 차수 사이의 자식 노드를 갖는다.
• 루트와 단말노드를 제외한 중간노드는 최소 [차수/2]에서 차수 사이의 자식 노드를 갖는다.
• 모든 단말 노드는 같은 레벨에 있다.
• 단말 노드가 아닌 노드에 있는 탐색키값의 수는 그 노드의 자식 노드 수보다 하나 적다.
• 단말 노드는 적어도 [(차수-1)/2]개의 탐색키값을 포함해야 한다.

B+- 트리의 레코드 삽입

• 새로운 탐색키값을 저장해야 할 노드에 빈 공간이 남아 있으면 빈 공간에 삽입한다.
• 공간이 없다면 노드를 분할한다. [차수/2]개의 키는 기존 노드에 두고, 나머지 키는 새로 만들어진 형제 노드에 넣는다.

• 위 예시에서 COM24를 삽입하는 경우 삽입 대상 노드에 저장한 공간이 없으므로 노드를 분할한다.
• COM12를 하나의 단말 노드로 구성
• COM24와 COM31이 하나의 단말 노드로 구성