인덱싱
- 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있또록 지원하는 데이터와 관련된 부가적인 구조
- 인덱싱: 인덱스를 구성하고 생성하는 작업
인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재함
탐색키
파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합
인덱싱의 종류
- 인덱스의 종류
- 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
- 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정
- 인덱스의 평가기준
- 접근 시간: 데이터를 찾는 데 걸리는 시간
- 유지 비용: 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
- 공간 비용: 인덱스 구조에 의해 사용되는 부가적인 공간 비용
순서 인덱스
순서 인덱스의 특징
탐색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스
(탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통하여 인덱스 생성)
인덱스 엔트리
각각의 레코드에 대한 빠른 접근을 할 수 있는 아주 작은 형태의 레이블 또는 태그
인덱스 엔트리는 탐색키 값, 포인터로 이루어져 있다.포인터는 블럭ID, 오프셋을 속성으로 가지고 있다.
- 순서 인덱스의 종류
- 밀집 인덱스
- 희소 인덱스
- 다단계 인덱스
밀집 인덱스
모든 레코드에 대해 인덱스 엔트리를 가지고 있는 인덱스를 말한다.
희소 인덱스
인덱스의 엔트리가 일부의 탐색키 값만을 유지하는 인덱스
탐색하고자 하는 인덱스가 인덱스 엔트리에 없다면 탐색하려는 인덱스보다 작은 인덱스부터 탐색해나간다.
다단계 인덱스
내부 인덱스와 외부 인덱스로 구성되어 있는 인덱스 (내부 > 외부)
- 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블럭을 지칭
- 탐색하려는 레코드가 외부 인덱스에 없다면 포인터가 가리키는 블럭을 스캔하여 내부 인덱스를 희소 인덱스와 동일하게 탐색
B+ 트리
루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
- 순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
- 상용 DBMS에서도 널리 사용되는 대표적인 순서 인덱스
B+트리의 구성 요소
- 인덱스 세트: 루트노드와 중간노드로 구성
- 단말노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용함
- [n/2] ~ n 사이의 개수를 자식으로 소유
- 순차 세트: 단말노드로 구성
- 모든 노드가 순차적으로 서로 연결
- 단말 노드는 적어도
[(n-1) / 2]개의 탐색키를 포함 - 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공