[Data Base] 인덱싱

인덱스가 필요한 이유

사용자가 데이터를 요청했을 때, 디스크와 메모리 사이에 IO를 (입출력을) 줄이는 기능이 있어야

사용자의 신뢰성과 만족성을 높인다.

 

인덱스의 개념

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

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

해당 블럭을 빠르게 적재한다.

 

인덱스

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

 

인덱싱

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

 

탐색키

한 파일에서 레코드를 찾기 위해 사용되는 컬럼이나 컬럼값의 집합

 

인덱스 엔트리

탐색키와 탐색키에 해당하는 레코드의 레코드 포인터의 쌍을 저장한 구조

 

다단계 인덱스

인덱스를 외부 인덱스와 내부 인덱스의 다단계 구조로 나누어 외부 인덱스에 희소하게 분포시켜

인덱스 파일의 크기를 적정하게 유지할 수 있는 인덱스

 

이진 탐색트리 

이진 트리의 일종으로 왼쪽은 부모 노드보다 작은 노드값, 오른쪽에는 부모 노드보다 큰 노드값을 위치시켜

특정 노드값을 빠르게 찾을 수 있도록 구조화한 트리

 

 인덱스의 종류

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

-해시 인덱스: 버킷의 범위 안에서 값의 균일한 

 

인덱스 평가 기준

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

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

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

 

순서인덱스

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

탐색키를 정렬하여 해당 탐색키와 탐색키에 대한 레코드와의 연계를 통하여 인덱스 생성 

(ex.백과사전) 

 

순서 인덱스의 종류

*밀집 인덱스

*최소 인덱스

*다단계 인덱스

 

순차 파일 

각각의 레코드가 키값으로 정렬되어 있다.

특정 레코드의 다음 레코드는 무엇인지 빠르게 접근할 수 있다.

 

인덱스 엔트리의 구조

각각의 레코드에 대한 빠른 접근을 할 수 있는 아주 작은 형태의 레이블(태그) 

크게 3가지로 구성되어 있다.

블럭 아이디: 해당 레코드가 어느 디스크에 저장되어 있는지

오프셋: 블럭 내부에서 해당되는 레코드가 어느정도 내부에 위치되어 있는지, 내부에서의 위치를 가리킨다.

 

오프셋 예시

김영희라는 사람을 예로 들면, 

2014001이라고 하는 학번이 탐색기가 되어 앞으로 들어가고

포인터는 곧바로 학생들의 데이터가 b1, b2 로 분류되어있는데, 김영희라는 학생은 B2 두번째 블럭에서 

오프셋이 하나의 블럭에서 30바이트 뒤에 김영희라는 사람의 레코드가 있다 라는걸 알려준다.

하나의 인덱스 엔트리는 각각의 레코드가 어떤 블럭에 있는지, 그 블럭의 처음 시작부터 몇바잉트가 떨어져있는지 위치정보를 가르킴으로써,

곧바로 접근할 수 있는 방법을 알려준다.

 

 

밀집 인덱스

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

밀집 인덱스 예시

이런 형태의 과목 테이블이 순차파일 형태로 구성되어있다.

만약, 위의 표에서 데이터 베이스 시스템에 대한  레코드를 알고싶다면

com31 에 해당되는 과목명은 무엇이지? 하면 

인덱스 엔트리가 io 의 블럭만큼 차근차근 메모리에 적재되어서

com31을 찾을때까지 넣었다 뺏다 할것인데, 이 com31이 메모리에 적재 되어서 

포인터를 가져오면 데이터베이스 시스템에 대한 블럭을 메모리에 적재하고, 

해당되는 정보를 곧바로 알려줄 수 있게된다.

 

 

희소 인덱스

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

 

희소 인덱스 예시

COM31 레코드를 적재하기 위해 데이터베이스 시스템을 찾아갈 수 있는 엔트리가 없기 때문에

다른 검색 과정을 거쳐 com31보다 작은 엔트리중에 가장 큰 것을 찾는다.

밀집과 반대로 희소 인덱스는 인덱스 엔트리가 몇개 없기때문에 사이즈가 작아서 인덱스를 찾는 비용이 적다.

모든 레코드가 인덱스 엔트리가 만들어져 있는게 아니라, 어떠한 인덱스를 갖고 인접한 인덱스를 따라가서

순차파일 내부에서 일부의 검색을 다시한번 해야하는 단점이 있다. 

 

다단계 인덱스의 필요

-4KB 크기의 한 블럭에 100개의 엔트리가 삽입될 때,

100,000,000 개의 레코드에 대한 순서 인덱스 

1,000,000개의 블럭 = 4GB의 공간 필요

어떠한 하나의 레코드를 찾기 위해서 메모리는 적재해야 하는데, 메모리에 충분한 공간이 없을 경우 다단계 인덱스가 필요하다. 

인덱스 크기에 따른 검색 성능

-인덱스 크기 < 메모리 크기

-인덱스 크기 > 메모리 크기 

다단계 인덱스는 밀집 인덱스의 또다른 밀집 인덱스로

밀집과 희소인덱스를 혼용한 구조다. 여기서 외부와 내부로 나뉘어진다 

 

-내부 인덱스와 외부 인덱스로 구성

-내부 인덱스는 1,000,000개의 블럭을 갖는 반면, 외부 인덱스는 100개의 블럭만 사용하여 작은 크기의 

외부 인덱스로 메모리에 적재 가능하다.