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

인덱스의 이해

인덱스의 개념

데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 시작
- 인덱스 : DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 지원하는 데이터와 관련된 부가적인 구조
- 인덱싱 : 인덱스를 구성하고 생성하는 작업
인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재
- 탐색키 : 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

인덱스 기반의 검색 과정

인덱스가 없을 경우 정보가 담긴 레코드를 디스크에서 메모리로 가져옴
인덱스가 있을 경우 인덱스 블럭만 메모리로 옮겨옴
인덱스가 일치하는 해당 블럭만 메모리로 가져옴

단계상으로는 한 절차가 늘어났다고 생각할 수 있지만, 실제로는 속도면에서 굉장히 효율적이어짐. 인덱스만 메모리에 올리기 때문에 많은 양을 메모리에 올릴 수 있고 검색도 빨라짐

인덱스의 종류

인덱스의 종류
- 순서 인덱스 : 특정 값에 대해 정렬된 순서 구조
- 해시 인덱스 : 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정
인덱스의 평가기준
- 접근 시간 : 데이터를 찾는 데 걸리는 시간
- 유지 비용 : 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
- 공간 비용 : 인덱스 구조에 의해 사용되는 부가적인 공간 비용

순서 인덱스

탐색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 구성한 인덱스
- 탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통하여 인덱스 생성
순서 인덱스의 종류
- 밀집 인덱스
- 희소 인덱스
- 다단계 인덱스
인덱스 엔트리의 구조

탐색키 값	포인터
	블럭 ID	오프셋

밀집인덱스
- 모든 레코드에 대해 [ 탐색키 값 / 포인터 ] 쌍을 유지
희소 인덱스
- 인덱스의 엔트리가 일부의 탐색키 값만을 유지
다단계 인덱스의 필요
- 밀집 인덱스는 인덱스를 저장하기 위해 많은 용량 필요
- 인덱스를 사용하는것만으로 부담이 될 수 있음
다단계 인덱스
- 내부 인덱스와 외부 인덱스로 구성
  - 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블럭을 지칭
  - 포인터가 가리키는 블럭을 스캔하여 원하는 레코드보다 작거나 같은 탐색키 값중에 가장 큰 값을 가지는 레코드를 탐색
- 내부 인덱스는 1,000,000개의 블럭을 갖는다 해도 외부 인덱스는 100개의 블럭만 사용하여 작은 키기의 외부 인덱스로 메모리에 적재 가능

B+- 트리 인덱스

루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
- 순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
- 상용 DBMS에서도 널리 사용되는 대표적인 순서 인덱스

구성요소

인덱스 세트 : 루트노드와 중간노드로 구성
- 단말노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
- n/2 ~ n개 사이의 개수를 자식으로 소유
순차 세트 : 단말노드로 구성
- 모든 노드가 순차적으로 서로 연결
- 단말 노드는 적어도 (n-1)/2개의 탐색키를 포함
- 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공
레코드 삽입, 삭제 시 B+- 트리 수정
- 레코드 삽입
  - 노드에서 유지해야 할 탐색키와 포인터 수 증가로 인해 노드를 분할해야 하는 경우가 발생
- 레코드 삭제
  - 노드에서 유지해야 할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분배 또는 병합해야 하는 경우가 발생
- 높이 균형 유지
  - 노드가 분할되거나 병합되면서 높이의 균형이 맞지않는 경우가 발생