[데이터베이스시스템#10]인덱싱

1. 인덱스의 이해

- 데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 시작

- 인덱스의 탐색키를 이용해 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재

 

인덱스 : DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조

- 순서 : 특정 값에 대해 정렬된 순서 구조

- 해시 : 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정

 

인덱싱 : 인덱스를 구성하고 생성하는 작업

- 접근 시간 : 데이터를 찾는데 걸리는 시간

- 유지 비용 : 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용

- 공간 비용 : 인덱스 구조에 의해 사용되는 부가적인 공간 비용

 

2. 순서 인덱스

- 탐색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스

 

종류

- 밀집 : 모든 레코드에 대해 탐색키 값, 포인터 쌍을 유지

- 희소 : 인덱스의 엔트리가 일부의 탐색키 값만을 유지

- 다단계 : 내부 인덱스와 외부 인덱스로 구성, 인덱스 크기에 따른 검색 성능

 

3. B+-트리 인덱스

B+-트리의 구조

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

 

구성요소

- 인덱스 세트 : 루트 노드와 중간 노드로 구성

- 순차 세트 : 단말노드로 구성