6. Index

2019 Sep 23 in Study on Database

Overview

Index는 수 많은 데이터 중에서 원하는 자료를 빠르고 효율적으로 검색하기 위해 사용하는 방법이다.

구성

데이터의 위치(주소)를 관리, 기억하는 인덱스 파일과 실제 데이터를 기억하는 데이터 파일로 구성

데이터를 검색할 때는 먼저 인덱스 파일에서 데이터의 주소를 찾음
데이터 파일에서 인덱스 파일에서 찾은 주소의 데이터 검색

인덱스 구조

B-트리(Balanced Tree)

검색의 효율을 높이기 위해 자료의 구조를 균형 있는 트리 구조로 나타내는 방법

B-트리에서 하나의 노드에는 여러 개의 자료를 기억할 수 있음

한 노드의 데이터들은 오름차순 정렬되어 있음

node

P1 : data1보다 작은 값을 갖는 하위 노드의 주소
P2 : data1과 data2의 중간 값을 갖는 하위 노드의 주소
P3 : data2보다 큰 값을 갖는 하위 노드 주소

B-트리의 특징

차수가 m일 때, 루트 노드와 리프 노드를 제외한 모든 노드는 최소 m/2개, 최대 m개의 서브트리를 갖음
모든 단말 노드는 같은 레벨에 있음
루트 노드는 단말 노드가 아닌 이상 적어도 두 개의 서브 트리를 갖음
한 노드 안에 있는 키 값들은 오름차순으로 구성
검색은 루트 노드에서 시작

B\(^{+}\)-트리

B트리의 변형으로 인덱스 세트와 순차 세트로 구성
인덱스 세트는 단말 노드를 찾기 위한 인덱스를 제공, 순차 세트는 단말 노드로만 구성
순차 세트의 단말 노드에는 모든 키 값이 다시 나타나도록 하여 단말 노드만으로 순차검색 가능

인덱스 기타 유형

클러스터드 인덱스(Clustered Index)
- 테이블에서 하나의 속성을 기준으로 정렬시킨 후, 테이블을 재구성하여 인덱스를 만드는 방법
- 테이블의 물리적 순서와 인덱스 순서가 동일
- 하나의 테이블에는 하나의 인덱스만 만들 수 있음
넌 클러스터드 인덱스(Non Clustered Index)
- 테이블을 재구성하지 않고 데이터 주소를 이용하여 인덱스를 만들어 주소값을 이용하여 검색
- 하나의 테이블에 여러 개의 인덱스를 만들 수 있음
- 인덱스 구조보다 다소 복잡해질 수 있음