인덱스 구조 및 탐색

인덱스 탐색 과정은 수직적 탐색과 수평적 탐색 두 단계로 이루어진다.

 

◎ 데이터를 찾는 두 가지 방법

• 테이블 전체를 스캔
• 인덱스를 이용

 

◎ 인덱스 튜닝의 두 가지 핵심요소

학생을 '학년-반-번호'로 분류하는 건 인덱스로 따지면 ROWID에 해당한다.

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

 

온라인 트랜잭션 처리(Online Transaction Processing, 이하 OLTP) 시스템에서는 소량 데이터를 주로 검색하므로 인덱스 튜닝이 무엇보다 중요하다.

 

인덱스 튜닝의 핵심요소는 크게 두 가지로 나뉜다.

 

1. 인덱스 스캔 과정에서 발생하는 비효율을 줄이는 것

- 인덱스 스캔 효율화 튜닝

 

ex) 시력이 1.0~1.5인 홍길동을 찾는 경우.

1) 이름과 시력 순으로 정렬한 경우 - 소량만 스캔해도 됨

2) 시력과 이름 순으로 정렬한 경우 - 많은 양을 스캔해야 함

 

 

2. 테이블 액세스 횟수를 줄이는 것

- 인덱스 스캔 후 테이블 레코드를 액세스할 때 랜덤 I/O 방식을 사용하므로 이를 '랜덤 액세스 최소화 튜닝'이라고 한다.

 

ex) 시력이 1.0~1.5인 홍길동을 찾는 경우.

- 만약 이름과 시력 순으로 정렬한 명부가 있다면 가장 좋겠으나

- 이름으로 정렬된 명부와 시력순으로 정렬된 명부가 따로 있다면?

- 시력순으로 정렬되었다면 여러 번 교실을 왕래해야할 것이다.

- 반면 이름순으로 정렬된 명부라면 두 번만 방문해도 될 것이다.

 

 

※ 두 튜닝 방법 모두 중요하지만 굳이 하나를 고르라면 랜덤 액세스 최소화 튜닝이 더 중요하다.

- 이는 성능에 미치는 영향이 더 크기 때문이다.

 

 

◎ SQL 튜닝은 랜덤 I/O와의 전쟁

 DB 성능이 느린 이유는 디스크 I/O 때문이다.

읽어야 할 데이터량이 많고, 그 과정에서 디스크 I/O가 많이 발생할 때 느리다.

인덱스를 많이 사용하는 OLTP 시스템이라면 디스크 I/O 중에서도 랜덤 I/O가 특히 중요하다.

NL 조인도 랜덤 액세스 이기에 대량의 데이터를 처리할 때 느린 것이다.

 

 

◎ 인덱스 구조

인덱스는 대용량 테이블에서 필요한 데이터만 빠르게 효율적으로 액세스하기 위해 사용하는 오브젝트다.

흡사 책의 목차와 같은 역할이다.

 

DB에서도 인덱스 없이 데이터를 검색하려면, 테이블을 처음부터 끝까지 모두 읽어야 한다.

반면, 인덱스를 이용하면 일부만 읽고 멈출 수 있다. 즉, 범위 스캔(Range Scan)이 가능하다. 범위 스캔이 가능한 이유는 인덱스가 정렬되어 있기 때문이다.

 

DBMS는 일반적으로 B*Tree 인덱스를 사용한다.

나무를 거꾸로 뒤집은 모양이어서 뿌리(루트, Root)가 위쪽에 있고, 가지(브랜치, Branch)를 거쳐 맨 아래에 잎사귀(리프, Leaf)가 있다.

 

 

 

루트와 브랜치 블록에 있는 각 레코드는 하위 블록에 대한 주소값을 갖는다.

키값은 하위 블록에 저장된 키값의 범위를 나타낸다.

 

ex) 루트 블록 '서' 레코드가 가리키는 하위 블록은 '서'보다 크거나 같은(고객명 >= '서') 레코드가 저장되어 있다는 뜻이다.

ex) 브랜치 블록 '이재룡'이 가리키는 하위 블록에는 '이재룡'보다 크거나 같은(고객명 >= '이재룡') 레코드가 저장돼 있다.

 

루트와 브랜치 블록에는 키값을 갖지 않는 특별한 레코드가 하나 있다. 가장 왼쪽 첫 번째 레코드이다.

이를 'LMC'라고 하며 'Leftmost Child'의 줄임말이다.

 

LMC가 가리키는 주소로 찾아간 블록에는 키값을 가진 첫 번째 레코드보다 작거나 같은 레코드가 저장돼 있다.

리프 블록에 저장된 각 레코드는 키값 순으로 정렬돼 있을 뿐만 아니라 테이블 레코드를 가리키는 주소값, 즉 ROWID를 갖는다.

 

인덱스 키값이 같으면 ROWID 순으로 정렬된다.

인덱스를 스캔하는 이유는, 검색 조건을 만족하는 소량의 데이터를 빨리 찾고 거기서 ROWID를 얻기 위함이다.

ROWID는 데이터 블록 주소와 로우 번호로 구성되므로 이 값을 알면 테이블 레코드를 찾아갈 수 있다.

• ROWID = 데이터 블록 주소 + 로우 번호
• 데이터 블록 주소 = 데이터 파일 번호 + 블록 번호
• 블록 번호 : 데이터 파일 내에서 부여한 상대적 순번
• 로우 번호 : 블록 내 순번

 

인덱스 탐색 과정에는 수직적 탐색과 수평적 탐색으로 나눌 수 있다.

 

 

◎ 인덱스 수직적 탐색

수직적 탐색이란 인덱스 스캔 시작지점을 찾는 과정이다.

정확히는 정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정이다.

 

인덱스 수직적 탐색은 루트(Root) 블록에서부터 시작한다. 루트를 포함해 브랜치 블록에 저장된 각 인덱스 레코드는 하위 블록에 대한 주소값을 갖는다. 루트에서 시작해 리프 블록까지 수직적 탐색이 가능한 이유다. 수직적 탐색 과정에서 찾고자 하는 값보다 크거나 같은 값을 만나면, 바로 직전 레코드가 가리키는 하위 블록으로 이동한다.

 

수직적 탐색은 '조건을 만족하는 레코드'를 찾는 과정이 아니라 '조건을 만족하는 첫 번째 레코드'를 찾는 과정이다.

 

 

◎ 인덱스 수평적 탐색

수직적 탐색을 통해 스캔 시작점ㅌ을 찾았다면, 찾고자 하는 데이터가 안 나타날 때까지 인덱스 리프 블록을 수평적으로 스캔한다. 인덱스에서 본격적으로 데이터를 찾는 과정이다.

 

인덱스 리프 블록끼리는 서로 앞뒤 블록에 대한 주소값을 갖는다. 즉, 양방향 연결 리스트 구조다. 좌에서 우로, 또는 우에서 좌로 수평적 탐색이 가능한 이유다.

 

인덱스를 수평적으로 탐색하는 이유는 두 가지이다.

1. 조건절을 만족하는 데이터를 모두 찾기 위해서

2. ROWID를 얻기 위해서

 

필요한 컬럼을 인덱스가 모두 갖고 있어 인덱스만 스캔하고 끝나는 경우도 있지만, 일반적으로 인덱스를 스캔하고서 테이블도 액세스하기 때문에 ROWID가 필요하다.

 

 

◎ 결합 인덱스 구조와 탐색

두 개 이상의 컬럼을 결합해서 인덱스를 만들 수도 있다.

인덱스 선두 컬럼을 모두 "=" 조건으로 검색할 때는 어느 컬럼을 인덱스 앞쪽에 두든 블록 I/O 개수가 같으므로 성능도 같다.

 

SELECT 이름
     , 성별
  FROM 성별 = '여자'
   AND 이름 = '유관순'

인덱스에 대한 잘못된 인식

1. 인덱스를 [성별 + 이름] 순으로 구성
- 총 사원 50명 중 성별 = '여자'인 레코드 25건을 찾고, 거기서 이름을 검사해 최종적으로 2명 출력
> 25번 검사

2. 인덱스를 [이름 + 성별] 순으로 구성
- 총 사원 50명 중 이름 = '유관순'인 레코드 2건을 찾고, 거기서 성별을 검사해 최종적으로 2명 출력
> 2번의 검사

결론.
선택도가 낮은 컬럼을 앞에 두고 결합 인덱스를 생성해야 검사횟수를 줄일 수 있어 성능에 유리

 

루트에서 브랜치를 거쳐 리프까지 '여자'이면서 '유관순'인 사원을 바로 찾아간다.

정확히 유관순이 아닌 레코드를 만날 때까지 총 세 건을 스캔한다.

그건 인덱스를 어떤 순서대로 구성해도 마찬가지다. 따라서 어느 컬럼을 앞에 두든 일량에는 차이가 없다.

 

인덱스 구성에 따라 성능에 차이가 나는 건 맞지만 위처럼 이해해선 곤란하다.

 

 

◎ Balanced

DELETE 작업으로 인해 인덱스가 불균형(Unbalanced) 상태에 놓일 수 있다는 것은 다른 리프 노드에 비해 루트 블록과의 거리가 더 멀거나 가까운 리프 노드가 생길 수 있다는 설명이다.

 

B*(Balanced)Tree 인덱스에서 이런 현상은 절대 발생하지 않는다.

Balanced는 어떤 값으로 탐색하더라도 인덱스 루트에서 리프 블록에 도달하기까지 읽는 블록 수가 같음을 의미한다.

즉, 루트로부터 모든 리프 블록까지의 높이(height)는 항상 같다.