인덱스 구조 및 탐색

홍길동 학생을 찾는 방법은 두 가지

첫째는 홍길동 학생을 차즌ㄴ 것

둘째는 교무실에서 학생명부를 조회해 홍길동 학생이 있는 교실만 찾아가는 것

 

홍길동 학생이 많다면 전자가 바르고, 몇 안되면 후자가 빠르다.

 

 

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

온라인 트랜잭션 시스템에서는 소량 데이터를 주로 검색 -> 인덱스 튜닝이 무엇보다 중요

 

1. 인덱스 스캔 효율화 튜닝

학생명부에서 이름과 시력순으로 정렬 -> 홍길동에 대한 데이터 소량만 찾으면 된다.

반면에 학생명부를 시력과 이름순으로 정렬해 두면 많은 양을 스캔해야 한다.

 

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

인덱스 스캔 후 테이블 레코드를 액세스 할 때 랜덤 I/O 방식 사용 

학생명부를 뒤지는 과정에도 비효율이 있을 수 있지만, 학생명부에 없는 나머지 정보를 얻기 위해 직접 교실을 찾아가는 부담에 비하면 적다. 

 

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

 

데이터베이스 성능이 느린 이유 디스크 I/O , 읽어야 할 데이터량이 많고, 그 과정에 디스크 I/O가 많이 발생

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

 

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

반면, 인덱스를 이용하면 일부만 읽고 멈출 수 있다. 즉 범위 스캔이 가능

DBMS는 일반적으로 B*Tree 인덱스 사용 -> 나무를 거꾸로 뒤집은 모양이어서 뿌리가 위쪽에 있고, 가지를 거쳐 맨 아래에 잎사귀가 있다.

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

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

 

루트와 브랜치 블록에는 키값을 갖지 않는 특별한 레코드

가장 왼쪽 첫 번째 레코드 -> 'LMC'라고 하며 'Leftmost Child'

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

 

인덱스 수직적 탐색

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

인덱스 수직적 탐색은 루트블록에서 시작

루트를 포함해 브랜치 블록에 저장된 각 인덱스 레코드는 하위 블록에 대한 주소값

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

 

인덱스 수평적 탐색

인덱스에서 본격적으로 데이터를 찾는 과정

인덱스 리프 블록끼리는 서로 앞뒤 블록에 대한 주소값을 가짐

즉 양방향 연결 리스트 구조, 좌에서 우로, 또는 우에서 좌로 수평적 탐색이 가능

인덱스를 수평적으로 탐색하는 이유 -> 조건절을 만족하는 데이터를 모두 찾기 위해, ROWID를 얻기 위해

필요한 컬럼을 인덱스가 모두 갖고 있어 인덱스만 스캔하고 끝나는 경우도 잇지만, 일반적으로 인덱스를 스캔하고서 테이블도 엑세스

 

결합 인덱스 구조

 

고객 테이블에 성별과 고객명 기준으로 만든 인덱스 구조를 짰다면

SELECT * 
FROM 고객 
WHERE 성별 = '남' AND 고객명 = '이재희'

이러한 쿼리문에 대한 탐색을 할 때

루트블록을 스캔하다 보면 찾고자 하는 값보다 큰 첫 번쨰 레코드를 가지게 된다. 

해당 레코드 직전 하위블록으로 이동한 후 다시 찾고자 하는 값보다 큰 첫 번째 레코드를 만남

그 이후 또 직전 하위블록으로 이동한 후 리프블록에 도달했으면 그때부터 '이재희' 고객을 찾으면 된다.

 

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