인덱싱

인덱스

인덱스의 개념

1. 데이터 검색에서 발생하는 비효율적인 데이터 입출력 문제를 해결하기 위한 목적으로 시작
2. 인덱스의 탐색키를 이용하여 해당 레코드가 저장된 블럭을 디스크 저장장치 또는 메모리에서 파악하여 해당 블럭을 빠르게 적재

인덱스 방식의 장점

레코드 블록을 메모리에 적재하는 것보다 인덱스 블록을 메모리에 적재하는 것이 사이즈가 작고 더 많은 레코드들을 올려놓을 수 있어 검색할 때 효율적이다.

인덱스의 종류

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

인덱스의 평가기준

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

순서 인덱스

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

• 밀집 인덱스: 모든 레코드에 대해 [탐색키 값, 포인터] 쌍을 유지
• 희소 인덱스: 인덱스의 엔트리가 일부의 탐색키 값만을 유지
• 다단계 인덱스: 단계에 걸쳐 인덱스를 구성 (내부 인덱스, 외부 인덱스)

B+-트리의 구조

• 루트 노드로 부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
• 인덱스 세트: 루트노드와 중간노드로 구성
• 순차 세트: 단말노드로 구성
• 레코드의 삽입, 삭제시 트리 수정
  • 레코드 삽입: 노드에서 유지해야 할 탐색키와 포인터 수 증가로 인해 노드를 분할해야 하는 경우가 발생
  • 레코드 삭제: 노드에서 유지해야 할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분배 또는 병합해야 하는 경우가 발생
  • 높이 균형 유지: 노드가 분할되거나 병합되면서 높이의 균형이 맞지않는 경우가 발생