[데이터베이스] 인덱스 개념

1. 인덱스(index)

사전에서 APPLE의 뜻을 찾고자 할 때 두 가지의 방법을 사용할 수 있다.

첫번째는 처음부터 하나하나씩 단어를 훑으면서 찾는 방법

두번째는 사전 옆에 붙어있는 A -> P ->.. 순서로 찾는 방법

둘 중에 탐색하는 속도는 두 번쨰의 경우가 더욱 빠르게 탐색이 가능하다.

이처럼 인덱스는 데이터 베이스에서 데이터 탐색 속도를 향상시켜주는 자료 구조이다.

만일 Search Key가 Primary Key를 포함한다면 Primary Index라고 하며, Unique Key를 포함한다면 

Unique Index라고 한다.

2. Clustered vs Unclustered Index

Clustered index와 Unclustered Index의 큰 차이점은 Sorting의 여부이다.

Clustered index는 Date Record가 Key 값을 기반으로 정렬하여 정렬하여 저장한다.

따라서 여러 개가 있으면 데이터 정렬의 순서가 꼬이므로 단 하나만 생성할 수 있다.

또한 정렬이 되어있는 특징 덕분에 전반적으로 불러오기 속도를 엄청나게 향상시키는 효과가 있다.

반면 Unclustered index의 경우 Date Record의 정렬을 하지 않고 저장한다. 

그리고 index 테이블에는 논리적으로 정렬하고 데이터가 있는 페이지 번호와 위치를 표기한다.

따라서 index 테이블은 논리적 정렬을 위해 여러 개가 존재해도 무관하고 덕분에 파일의 크기도 증가한다.

3. Hash-Based Index

해시 인덱스는 검색하고자하는 값을 해시함수에 입력한 후 그 결과와 Bucket의 내용과 비교하여

해당 데이터 레코드의 위치를 찾을 수 있는 인덱스 기법이다. 이 기법의 장점은 Equality 연산에는 좋은 성능을 보인다는 점, 그리고 해시 함수를 특징상 입력 값에 비해 출력 값의 크기는 줄여 Bucket에 저장한다는 점이다. 반면에 단점은 범위를 탐색하는 경우에 매우 비효율적인 성능을 보여준다는 점이다. 

4. B+ Tree Index

B+ Trees는 관계형 데이터 베이스에서 가장 일반적으로 사용되는 인덱스이다.

자료구조때 이진 트리처럼 가운데 키 값과 작거나 같으면 왼쪽 크면 오른쪽으로 트리를 구성한다.

다만 다른 점은 Leaf 노드 간 이동이 가능하다는 점이다. 

Leaf 단계에서 데이터 엔트리들이 포함되어 있기 때문에 B+ Tree의 성능은 트리의 깊이에 의하여 좌우된다.

범위 탐색의 경우에는 Root에서 시작하여 최소 경계값을 찾고 다음 리프 노드로 넘어가는 방식으로 연산을 수행한다. 삽입의 경우에는 필요에 따라 부모 노드가 조정될 수 있다. 마지막 리프 노드가 꽉 차있다면 다시 쪼개서 트리구조를 유지하기 떄문이다.