[2] 인덱스 구조

이 글은 [친절한 SQL 튜닝] 을 학습하고 정리한 글입니다.

 

인덱스 튜닝에 대해 살펴보기 이전에, 인덱스 구조를 통해 핵심 원리를 짚고 넘어갑시다.

인덱스는, 해당 자료를 찾기 편하게끔 데이터와 개별된 구조를 만들어 놓은 것입니다.

 

데이터베이스 테이블에서 데이터를 찾는 방법은 1. 테이블 전체를 스캔하거나 2. 인덱스를 이용하는 방법

위 두가지밖에 없기 때문에, 인덱스는 SQL 튜닝에서 가장 먼저 학습해야 할 부분입니다. 

 

인덱스 튜닝의 핵심 요소

인덱스는 큰 테이블에서 소량 데이터를 검색할 때 사용합니다.

일반적인 Online Transaction Processing 시스템에서는 소량 데이터를 주로 검색하므로

인덱스 튜닝이 매우 중요합니다.

 

인덱스 튜닝의 핵심은 크게 두가지로 나뉘는데

첫번째는 인덱스 스캔 과정의 비효율을 줄이는 것이고

두번째는 테이블 액세스 횟수를 줄이는 것입니다.

 

인덱스가 여러개가 달려있는 경우, 인덱스가 정렬된 순서에 따라 그 결과가 다른데

항상 Cardinality 가 높은 순에서 낮은 순으로 구성을 하는 것이 성능이 뛰어납니다.

Cardinality가 높은 순으로 구성을 한다는 것의 의미는 결국

여러 기준에 대해서 데이터를 탐색할 때

더 작은 집합을 추려낼 수 있는 순서로 구성하겠다 라는 의미이기 때문입니다.

 

테이블에 없는 정보를 찾아내기 위해 다른 테이블을 스캔하는 것은 매우 비효율적입니다.

내가 찾아야 하는 범위를 더 빠르게 축소화 하는 방법이 있다면 그걸 선택하는 것이 맞고

Index를 Cardinality 순으로 정렬함으로서 이를 일부 해소할 수 있습니다.

 

결국 디스크 I/O가 느리기 때문에 성능이 느린 것이고

IOT, 클러스터, 파티션, 테이블 Prefetch, Batch I/O 모두 디스크 I/O를 최소화하기 위한 전략입니다.

 

인덱스 구조

인덱스를 이용하면 테이블 전체를 스캔하지 않아도 범위에 대한 스캔이 가능한데

그 이유는 인덱스가 정렬되어있기 때문입니다.

 

일반적으로 인덱스는 B+ tree를 이용하는데요

B는 Balanced를 의미하고, 트리의 Root와 모든 leaf간의 거리가 같아서 Balanced 라고 합니다.

B+ tree의 구조는 다음과 같습니다. 

 

B+ Tree (출처 : http://www.cburch.com/cs/340/reading/btree/index.html)

루트와 브랜치에 있는 각 레코드는 하위 블록에 대한 주소값을 가지며

키값은 하위 블록에 저장된 키값의 범위를 나타내는데

자세히 보면 각 브랜치에 key보다 하나 더 큰 갯수로 주소값을 가지는 것을 볼 수 있습니다.

키값이 하위 블록에 저장된 키 값의 범위를 나타내기 때문인데, 

위에서 2번째 왼쪽 테이블의 9와 11 이 적힌 브랜치를 보면

첫번째 인덱스는 9의 다음 대상, 두번째 인덱스는 11의 다음 값을 가리키는 것을 확인할 수 있습니다. 

Root와 Branch의 Leftmost Child는 키값을 갖지 않으며, 가장 왼쪽 끝에 위치한 블록을 가리키게 됩니다. 

 

리프 블록에 저장된 레코드는 키 값으로 정렬이 되어있고, 해당 테이블 레코드를 가리키는 주소값(ROWID)을 가집니다.

인덱스의 키값이 같으면 ROWID 순으로 정렬되어 있습니다.

인덱스를 스캔하는 이유는, 결국 이 ROWID를 빠르게 찾기 위한 것입니다. 

ROWID엔 데이터 블록 주소와 ROW 번호로 구성되어 있어서, 테이블 레코드를 빠르게 찾을 수 있습니다. 

 

ROWID = 데이터 블록 주소 + ROW 번호 (데이터 파일 번호 + Block 번호 + Row 번호)

데이터 블록 주소 = 데이터 파일 번호 + Block 번호

Block 번호 = 데이터 파일 내에서 부여한 순번

ROW 번호 = 블록 내 순번

 

인덱스 탐색 과정은 수직적 탐색과 수평적 탐색으로 나뉘는데

수직적 탐색은 인덱스 스캔 시작지점을 찾는 과정이고

수평적 탐색은 수직적 탐색을 통해 주어진 데이터 블록 주소를 얻은 후 데이터를 찾는 과정입니다. 

 

수직적 탐색

레코드 중 조건을 만족하는 첫번째 레코드를 찾는 과정입니다.

트리에서 Root에서 출발하여 목표하는 Leaf를 찾아가는 과정인데요

탐색 과정에서 찾고자 하는 값보다 크거나 같은 값을 만나면, 바로 직전 레코드가 가리키는 하위 블록으로 이동합니다. 

 

그 이름에서 나타나듯 위에서 아래로 수직 탐색하는 것입니다. Leaf 노드에 처음 도달한 순간 수직 탐색은 종료됩니다.

 

수평적 탐색

Leaf 는 Doubly Linked List로 구성이 되어 있어, 좌우로 스캔하여 만족하는 데이터를 찾을 수 있습니다.

필요한 컬럼이 인덱스에 다 있으면 인덱스만 스캔하고 끝나지만, 일반적으로 인덱스 스캔 후 테이블도 액세스하는데

이때 ROWID가 필요합니다.

 

수평적 탐색은 처음 매칭되는 인덱스를 발견한 후 일치하지 않는 레코드를 만날 때 까지 진행됩니다.