인덱스

등장 배경

빠르게 원하고자 하는 데이터를 찾기 위해서 사용되었다.

 

개념

인덱스를 알아보기 전에 먼저, 인덱스의 내부 작동을 이해하기 위한 개념인 B-Tree (Balanced Tree)를 이해할 필요가 있다. 

 

B-Tree (Balanced Tree)

(자료구조적인 관점이 아니라 데이터베이스 관점에서 서술하겠습니다.)

 

'이것이 SQL Server다'에서 발췌한 사진입니다.

B-Tree의 특성

• 자식 노드의 개수가 2개이상인 트리
• 노드 내의 데이터가 1개 이상일수 있다.
• 노드의 데이터는 반드시 정렬된다.
• 리프 노드의 레벨은 모두 같아야 한다.
• 데이터 검색시 뛰어난 성능을 발휘하여 데이터베이스와 파일시스템에서 널리 사용된다.

 

SQL Server에서 노드라는 용어에 대응되는 단어가 'Page'이다. 페이지란 8 KByte 크기의 최소한의 저장 단위다.

위의 사진으로부터 B-Tree 구조를 알아보자.

B-Tree 구조는 데이터를 검색할 때 (SELECT 구문을 사용할 때) 아주 뛰어난 성능을 발휘한다.

예를 들어 'MMM'이라는 데이터를 검색한다고 가정할 때, B-Tree로 이루어지지 않다면

루트 페이지에서 리프 페이지를 모두 뒤져 'MMM'이라는 단어를 찾아야 하므로 8건의 데이터를

검색해야 한다. 

B-Tree 구조를 사용한다면, 우선 루트 페이지를 검색하게 된다. 모든 데이터는 정렬되어 있으므로

'AAA', 'FFF', 'LLL' 세 개를 읽으면 'MMM'은 'LLL' 다음에 나오므로 세 번째 리프 페이지로 이동하면 된다.

세번째 리프 페이지에서 'LLL', 'MMM' 두 개를 읽으니 찾고자 하는 'MMM'을 찾을 수 있다.

(지금은 레벨이 2단계를 예시로 들어서 차이가 거의 없지만, 레벨이 깊어질수록 차이는 기하급수적으로 난다)

 

데이터를 검색할 때 (SELECT) 효율적인 것은 확인했지만 데이터를 삽입/변경/삭제 시도 효율적일까?

먼저 삽입시 페이지들의 변화를 알아보자.

 

'이것이 SQL Server다'에서 발췌한 사진입니다.

 

'III'가 삽입되었을 때 다행히 2번째 리프 페이지에 빈 공간이 있어서 JJJ가 한 칸 이동한 후 그 자리에 III를 

삽입하는 간단한 작업만 일어났다. 하지만 이 상태에서 2번째 리프 페이지에 데이터가 추가되면 어떻게 될까?

 

'이것이 SQL Server다'에서 발췌한 사진입니다.

 

더 이상 두 번째 리프 페이지에 빈 공간이 없으므로 '페이지 분할'이 일어난다.

SQL Server는 우선 비어있는 페이지 하나를 확보한 후 두번째 리프 페이지의 데이터를 공평하게 나눈다.

방금 작업을 통해서 페이지를 확보한 후 페이지 분할 작업이 1회 일어나고 루트 페이지에도 새로 등록된

페이지의 제일 위 데이터인 III가 등록되었다. 한 데이터를 추가했을 뿐인데 여러 작업이 이루어진 것이다.

 

이번에는 'PPP'와 'QQQ'를 입력해보자.

 

'이것이 SQL Server다'에서 발췌한 사진입니다.

 

'PPP'는 그저 네 번째 리프 페이지에 추가됐을 뿐이다. 

'QQQ'가 추가될 때 많은 변화가 일어난다. 우선 네 번째 리프 페이지에는 빈칸이 없으므로 페이지 분할 작업이

일어난다. 리프 페이지가 5개가 되었으니 루트 페이지에 등록을 해야 하는데 루프 페이지도 가득 찼다!

따라서 루트 페이지도 다시 페이지 분할을 해야 한다. 그리고 루트 페이지가 있던 곳은 중간 노드를 가리키는

페이지로 구성된다.

따라서, 'QQQ' 하나를 입력하기 위해서 3개의 새로운 페이지가 할당되고 2회의 페이지 분할이 일어난 것이다.

 

요약하자면 B-Tree를 이용하면 데이터 탐색은 빠르나 나머지 작업 (특히 삽입)이 느려지는 것을 알 수 있었다.

 

인덱스의 종류

인덱스는 크게 두 가지로 나뉜다. 클러스터형 인덱스 (Clustered-Index)와 비클 러스터형 인덱스 (NonClustered-Index)로

나누어지는데 두 인덱스의 특징과 차이점을 알아보자.

 

클러스터형 인덱스 특징

• 인덱스 자체의 리프 페이지가 데이터와 같다
• B-Tree 구조로 이루어져 있어서 검색은 빠르지만 나머지 작업은 비클 러스터형 인덱스보다 느리다
• 클러스터형 인덱스는 생성 시 다시 정렬된다
• 테이블에 한 개만 생성 가능하다

비클 러스터형 인덱스 특징

• 데이터 페이지를 건드리지 않고, 별도의 장소 인덱스 페이지를 생성한다.
• 리프 페이지에 인덱스로 구성한 열 정렬한다.
• 위치 포인터 (ROW ID)를 생성하여 '페이지 번호 + #오프셋' 형태로 기록된다.
• 단일 질의에서는 클러스터형 인덱스와 별 차이가 없지만, 범위 질의에서는 클러스터형 인덱스보다 느리다.
• 테이블에 여러 개 생성할 수 있다.

'이것이 SQL Server다'에서 발췌한 사진입니다. (비클러스터형 인덱스 내부 구조)

두 인덱스를 혼용하는 경우

일반적으로 한 테이블에 두 인덱스가 혼합되어 사용되는 경우가 더 많다.

두 인덱스가 혼합된다면 어떤 방식으로 인덱스가 구성될까?

 

`이것이 SQL Server다'에서 발췌한 사진입니다.

클러스터형 인덱스 같은 경우에는 혼합하지 않았던 경우와 일치한다. 

비클 러스터형 인덱스는 다른 형태를 취하고 있는데 기존의 '데이터 페이지의 번호 + #오프셋' 형태로

구성되어야 할 리프 페이지가 클러스터형의 인덱스의 키 값을 가지게 된 것이다.

 

왜 이렇게 구성한 것일까?

그 이유는 데이터가 삽입될 때 기존의 '데이터 페이지의 번호 + #오프셋' 형태를 취했을 때

클러스터형 인덱스의 리프 페이지가 재구성이 되어서 '데이터 페이지의 번호 + #오프셋'이 

대폭 변경되기 때문에, 이러한 치명적인 단점을 발생시키지 않기 위해서 위와 같은 구조를

취하게 된 것이다.

 

언제 인덱스를 사용해야 할까?

물론 최신 버전의 SQL Server는 인덱스를 사용했을 때가 사용하지 않았을 때보다 처리 속도가 늦다면

알아서 인덱스 없이 처리하도록 설정되어 있다. 하지만 그렇다고 해서 원래의 목적인 처리 속도를 빠르게

만드는 역할을 제대로 하고 있지 못하다면 성능 향상을 기대할 수 없으므로 다음과 같이 상황에 따라

인덱스를 적절히 달아주자.

 

• SELECT문은 잦고 INSER/UPDATE/DELETE는 거의 사용되지 않을 때
• 데이터의 중복도가 높은 열에는 사용하지 말자.
  • 다른 말로 선택도가 나쁜 열
• 외래 키가 사용되는 열
  • 외래 키는 자동으로 인덱스를 생성해 주지 않는다.
• JOIN에 자주 사용되는 열