오라클 인덱스(Index) 구조 - B*Tree

테이블에서 데이터를 찾는 방식 2가지

1. 테이블 전체를 스캔
2. 인덱스를 이용
 
인덱스는 큰 테이블에서 소량 데이터를 검색할 때 사용한다. 그래서 온라인 트랜잭션 처리(Online Transaction Process, OLTP) 시스템에서는 소량 데이터를 주로 검색하므로 인덱스 튜닝이 무엇보다 중요하다.
 

인덱스란

대용량 테이블에서 필요한 소량의 데이터만 빠르게 효율적으로 액세스하기 위해 사용하는 오브젝트다.
DBMS 는 일반적으로 B*Tree(Balanced Tree) 인덱스를 사용한다.
 

B*Tree 구조를 가지는 인덱스 구조

 B*Tree 구조는 루트 블록, 브랜치 블록, 리프 블록으로 구성되어 있다.
루트와 브랜치 블록에 있는 각 레코드는 하위 블록에 대한 주소값을 가지고 있다.
키값은 하위 블록에 저장된 키값의 범위를 나타낸다. 이미지에서 루트블록의 '서' 레코드가 가리키는 하위 블록에는 '서'보다 크거나 같은(고객명>='서')레코드가 저장돼 있다는 뜻이다.
루트와 브랜치 블록에는 LMC(LeftMost Child)라는 키값을 갖지 않는 특별한 레코드가 하나 있는데, 가장 왼쪽의 첫번째 레코드로, 이건 자식 노드 중에서 가장 왼쪽 끝에 위치한 블록을 가리킨다.
LMC 가 가리키는 주소로 찾아간 블록에는 키값을 가진 첫 번째 레코드보다 작거나 같은 레코드가 저장돼 있다.
리프블록에 저장된 각 레코드는 키값 순으로 정렬돼 있을 뿐 아니라 테이블 레코드를 가리키는 주소값(ROWID)를 가지고 있다. 리프블록은 double linked list 구조로 되어 있다.
 
인덱스를 스캔하는 이유는 '검색 조건을 만족하는 소량의 데이터를 빨리 찾고 거기서 ROWID를 얻기 위해서이다. ROWID는 "데이터 블록 주소+로우번호"로 구성되어 있어 이 값을 알면 테이블 레코드를 찾아갈 수 있다.
 

인덱스 탐색

. 인덱스 수직적 탐색

조건을 만족하는 첫 번째 레코드를 찾는 과정이다. 즉, 인덱스 스캔의 시작지점을 찾는 과정이다.
 

. 인덱스 수평적 탐색

찾고자 하는 데이터가 더 안나타날 때까지 인덱스 리프 블록을 수평적으로 스캔한다.
select 절의 조건을 만족하는 데이터를 모두 찾기 위해서 수평적 탐색을 진행하고, 그 결과로 rowid 를 획득한다.
select 컬럼이 인덱스 컬럼들로 구성되었다면 인덱스만 스캔하고 끝난다. 그러나 일반적으로 인덱스를 스캔한 후 획득한 rowid 를 가지고 테이블로 액세스(랜덤 액세스)하여 원하는 레코드를 찾는다.
 

결합 인덱스 구조

두개 이상의 컬럼을 결합해서 인덱스를 만들 수 있다.
루트블록에서 찾고자 하는 값(남자 이재희)보다 큰 첫 번째 레코드를 만나게 된다. 그게 남&최 레코드다. 그 레코드 바로 직전 레코드인 LMC 가 가리키는 블록으로 넘어간다. 브랜치 블록에서 남자 이재희보다 큰 블록을 찾는다. 그 레코드는 바로 남&정재우 레코드다. 바로 직전 레코드인 '남&이재룡'이 가리키는 리프 블록으로 넘어간다. 블록 안에서 남자 이재희를 찾는다.(수직적 탐색)
남자 이재희 레코드를 발견한 후, 남자 이재희보다 큰 값이 나타날 때까지 수평적 탐색을 진행한다. 찾은 레코드의 결과 ROWID 를 이용해서 테이블 액세스를 한다.
 

** 결합 인덱스 생성시 컬럼 배치 순서

DBMS 가 사용하는 B*Tree 인덱스는 엑셀처럼 평면구조가 아니라 다단계 구조다.  위 예시로 살펴보면 성별+이름 인덱스나, 이름+성별 인덱스 모두 읽는 인덱스 블록의 개수가 똑같다.
모두 같은 일량(액세스하는 블록 개수)은 3개의 블록 액세스로 동일하다.
인덱스 선두 컬럼을 모두 '=' 조건으로 검색할 때는 어느 컬럼을 인덱스 앞쪽에 두든 블록 i/o 개수가 같기때문에 성능도 똑같다.
 
 

정리

인덱스는 데이터테이블에서 소량의 데이터를 찾을 때 사용하는 오브젝트이다.
b*tree 구조로 설계되어 있어 다단계 방식으로 데이터를 찾아간다.
데이터를 탐색할 때는 루트블록에서부터 브랜치 블록을 거쳐 인덱스 스캔의 시작 리프 블록을 찾는 '수직적 탐색 과정'을 먼저 거친다. 이후 리프블록에서 찾는 데이터보다 큰 데이터가 나타날 때 까지 탐색을 진행하는 '수평적 탐색 과정'을 진행한다. 탐색 완료 후, 탐색의 결과물인 rowid 정보를 토대로 테이블 랜덤 액세스를 통해 rowid가 있는 데이터 블록을 액세스하여 실제 row 데이터들을 찾는다. 
찾은 row 데이터는 버퍼 캐시 메모리에 싱글 블록 I/O 방식으로 적재한다.