2.1 인덱스 구조 및 탐색

2.1.1 미리 보는 인덱스 튜닝

데이터를 찾는 두 가지 방법

• 테이블 전체를 스캔한다. (모든 교실을 돌며 학생을 찾는다.)
• 인데스를 이용한다. (이름순으로 정렬한 학생부를 이용하여 학생을 찾는다.)

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

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

<인덱스 튜닝 방법>

1. 인데스 스캔 효율화 튜닝 (인덱스 스캔 과정에서 발생하는 비효율을 줄이는 것)
   : 인덱스 스캔 순서에 따라 스캔하는 양이 달라진다.
2. 랜덤 액세스 최소화 튜닝 (테이블 액세스 횟수를 줄이는 것)★
   : 인덱스 스캔 후 테이블 레코드를 액세스할 때 랜덤 I/O방식을 사용하는데, 이 액세스를 튜닝하는 것이다.

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

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

데이터베이스 성능이 느린 이유는 디스크 I/O 때문이다. 가장 일반적으로 사용하는 NL 조인이 대량 데이터를 조인할 때 느린 이유도 랜덤 I/O 때문이다. 소트머지 조인, 해시 조인도 랜덤 I/O를 극복하기 위해 개발된 기능이다.

---

2.1.2 인덱스 구조

인덱스는 정렬이 되어 있기 때문에 범위 스캔(Range Scan)이 가능하다. DBMS는 일반적으로 B-Tree(Balanced Tree) 인덱스를 사용한다. 나무(Tree)를 거꾸로 뒤집은 모양이어서 뿌리(Root)가 위쪽에 있고, 가지(Branch)를 거쳐 맨 아래에 있는 잎사귀(Leaf)가 있다.

루트와 브랜치 블록에는 키값을 갖지 않는 특별한 레코드가 하나 있다. 가장 왼쪽 첫 번째 레코드인 LMC(Leftmost Child)이다. LMC는 자식 노드 중 가장 왼쪽 끝에 위치한 블록을 가리킨다.
리프 블록에 저장된 각 레코드는 키값 순으로 정렬돼 있을 뿐만 아니라 테이블 레코드를 가리키는 주소값, 즉 ROWID를 갖는다.

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

인덱스 탐색 과정은 수직적 탐색(인덱스 스캔 시작지점을 찾는과정)과 수평적 탐색(데이터를 찾는 과정)으로 나눌 수 있다.

---

2.1.3 인덱스 수직적 탐색

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

---

2.1.4 인덱스 수평적 탐색

수직적 탐색을 통해 스캔 시작점을 찾았으면 인덱스에서 본격적으로 데이터를 찾는 과정이다. 인덱스 리프 블록끼리는 서로 앞뒤 블록에 대한 주소값을 갖는다. 즉, 양방향 연결 리스트(double linked list) 구조다.

---

2.1.5 결합 인덱스 구조와 탐색

교재 참고(page 79). 결합 인덱스의 컬럼 순서를 바꿔도 읽는 인덱스 블록 개수는 똑같다. 인덱스 선두 컬럼을 모두 = 조건으로 검색할 때는 어느 컬럼을 인덱스 앞쪽에 두든 블록 I/O 개수는 같으므로 성능도 똑같다.

Balanced Tree(B-Tree)는 어떤 값으로 탐색하더라도 인덱스 루트에서 리프 블록에 도달하기 까지 읽는 블록 수가 같다.