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

인덱스의 이해

인덱스의 개념

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

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

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

탐색키 : 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

 

인덱스 기반의 검색 과정

기존에는 디스크에서 메모리에 모든 컬럼을 올린다면 인덱스를 이용한다면 메모리에는 인덱스만을 올리고 필요할 때 추가 컬럼을 가져오는 방식을 이용 => 인덱스가 컬럼의 집합보다 크기가 작기 때문에 가능

 

인덱스의 종류

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

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

 

인덱스의 평가기준 

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

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

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

 

 

클러스터드 인덱스(clustered index) : 인덱스의 순서와 레코드가 저장된 순서가 동일한 인덱스

인덱스 엔트리(index entry) : 각각의 레코드를 빠르게 접근하기 위한 별도의 레이블, 이를 이용해서 인덱스 작업함

인덱스 엔트르의의 구조 

순서 인덱스

순서 인덱스의 특징

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

 

순서 인덱스의 종류

밀집 인덱스(Dense Index) : 모든 레코드에 대해 탐색키/ 포인터 쌍을 유지 

희소 인덱스(Sparse Index) :  인덱스의 엔트리가 일부 레코드에서만 유지

 

다단계 인덱스(multi-level index) : 블럭의 수가 매우 많아지면 인덱스를 사용하는 것 만으로 I/O 작업이 매우 많아지기에 생긴 인덱스로 인덱스의 인덱스가 있는 것이다. (밀집과 희소 인덱스가 합쳐진 것)

 

내부 인덱스와 외부 인덱스로 구성이 나눠지는데, 외부 인덱스를 내부 인덱스보다 더 희소한 인덱스로 구성하여 엔트리 포인터가 내부 인덱스 블럭을 지칭

B+ 트리 인덱스 

= 이진 탐색 트리(binary search tree) + 다단계 인덱스(multi-level index) 

B+ 트리 인덱스의  특징

- 루트, 중간, 단말 노드로 이루어져있으며 특이점은, 단말 노드가 리스트처럼 형제의 포인터를 지님

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

- 상용 DBMS에 널리 사용되는 대표적인 순서 인덱스

 

B+ 트리 인덱스의 용어

- 팬 아웃 (fanout) : 특정 노드의 하위 노드의 개수 

- 인덱스 세트 (index set) : 루트 노드와 중간 노드로 구성, 단말 노드에 있는 탐색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적, n/2 ~ n 개 사이의 개수를 자식으로 소유

- 순차 세트 (sequential set) : 단말 노드들로 구성되었으며, 모든 노드는 순치적으로 서로를 연결,  단말 노드는 적어도 (n-1)/2개의 탐색키를 포함, 탐색키에 대한 실제 레코드를 지칭하는 포인터를 제공

 

B+ 트리 인덱스의 단말노드

단말 노드만이 실제 레코드를 지칭하는 포인터를 제공

B+ 트리 인덱스의 전체 트리 재 구조화가 필요한 상황 => 순서를 유지해야 하므로 재 구조화를 통한  추가 비용이 발생

레코드 삽입 : 노드에서 유지해야 할 탐색키와 포인터 수 증가로 인해 노드를 분할해야(공간이 없을 경우) 하는 경우 발생

레코드 삭제 : 노드에서 유지해야할 탐색키 값과 포인터 수 감소로 형제 노드와 키를 재분배 또는 병합해야 하는 경우 발생

높이 균형 유지 : 노드가 분할, 병합되면서 높이의 균형이 맞지 않는 경우가 발생

 

B+트리 인덱스를 그려보고 싶다면 아래 사이트를 이용해보는 것을 추천드립니다.

https://www.cs.usfca.edu/~galles/visualization/BTree.html