[SQLP] 2-1. 인덱스 구조 및 탐색

인덱스 구조 및 탐색

 

인덱스 탐색 과정

: 수직적 탐색과 수평적 탐색

 

---

1. 미리 보는 인덱스 튜닝

 

데이터를 찾는 두 가지 방법

1. 처음부터 끝까지 찾기 [모든 교실을 돌면서 학생 찾는 경우]

2. 기록을 조회해서 해당되는 곳에서 찾기 [이름순으로 정렬한 학생 명부 이용]

 

-> 해당하는 내용이 많으면 1번이 빠르고, 수가 적으면 2번이 빠르다.

 

이름 ->이름으로 많이 찾기 때문에 이름순 정렬-	학년-반-번호 -> 인덱스 ROWID
강수지	4학년 3반 37번
홍길동	1학년 5반 15번
홍길동	2학년 6반 24번
홍길동	5학년 1반 16번

 

데이터베이스 테이블에서 데이터를 찾는 방법

: 테이블 전체 스캔 -> 모든 교실을 돌면서 학생 찾는 경우

: 인덱스 이용 -> 이름순으로 정렬한 학생 명부 이용

 

테이블 전체 스캔보다 인덱스 튜닝이 SQL 튜닝에 더 다양하고, 효율적이다.

 

---

 

인덱스 튜닝의 두 가지 핵심요소 [인덱스 스캔 효율화 튜닝, 랜덤 액세스 최소화 튜닝]

:인덱스는 큰 테이블에서 소량 데이터 검색시 사용

 

특히 온라인 트랜잭션 처리 시스템에서 중요하다. [OLTP]

 

인덱스 튜닝 방법

인덱스 스캔 효율화 튜닝 : 인덱스 스캔 과정에서 발생하는 비효율 최소화

랜덤 액세스 최소화 튜닝 : 테이블 액세스 횟수 최소화 [랜덤 I/O 방식 사용하기 때문에]

 

-> SQL튜닝에서 가장 중요한 점은 랜덤 I/O를 줄이는 것

 

랜덤 I/O 극복

: 데이터베이스 성능에 가장 영향을 미치는 요소가 디스크 I/O이기 때문에,

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

 

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

-> 따라서, 랜덤 I/OD을 줄이기 위해 DBMS에서 많은 기능을 제공한다.

 

조인 메소드 중 일반적으로 사용하는 NL 조인이 대량 데이터 조인할 때 느린 이유도 랜덤 I/O 때문

-> 소트머지 조인과 해시 조인

 

---

2. 인덱스 구조

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

: 색인과 같은 역할

 

범위 스캔 : 인덱스를 이용해서 일부만 읽고 멈춘다 [인덱스가 정렬되어 있을 경우 가능]

 

B*Tree 인덱스

: DBMS에서 일반적으로 사용하는 인덱스로, 나무를 거꾸로 뒤집은 모양이다

: 뿌리T가 위쪽에 있고, 가지B를 거쳐 맨 아래에 잎사귀L가 존재

 

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

 

키값은 하위 블록에 저장된 키값의 범위 [해당하는 키값보다 크거나 같은 레코드 저장]를 나타내는데, 루트와 브랜치 블록에는 키값을 갖지 않는 레코드가 하나 존재한다.

 

이 레코드는 가장 왼쪽 첫 번째 레코드, 즉, 자식 노드 중 가장 왼쪽 끝에 위치한 블록을 가리킨다.

['Leftmost Child'의 줄임말로 LMC라고 한다.]

 

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

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

[인덱스 키값이 같은 경우 ROWID 순으로 정렬]

 

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

ROWID는 데이터블록주소 (DBA)와 로우 번호로 구성되어 있어서 이 값을 이용해 테이블 레코드를 찾을 수 있다.

 

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

 

인덱스 탐색 과정

수직적 탐색	인덱스 스캔 시작지점을 찾는 과정
수평적 탐색	데이터를 찾는 과정

 

인덱스 탐색 과정을 알고 나면 인덱스 구조를 더 잘 이해할 수 있다.

---

3. 인덱스 수직적 탐색

: 정렬된 인덱스 레코드 중 조건을 만족하는 첫 번째 레코드를 찾는 과정으로 인덱스 스캔 시작지점을 찾는 과정

 

인덱스 수직적 탐색은 루트 블록에서부터 시작한다.

 

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

[루트에서 시작해 리프 블록까지 수직적 탐색이 가능한 이유]

 

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

-> 리프 블록에 도달하고, 조건을 만족하는 첫 번째 레코드 발견

 

2. 찾고자 하는 값보다 큰 값이 루트 블록에 존재하면, 바로 직전 레코드(LMC)가 가리키는 하위 블로으로 이동

 

3. 이동한 브랜치 블록에는 찾고자 하는 값과 정확히 일치하는 레코드 존재

 

3. 존재하더라도, 그 레코드가 가리키는 하위 블록으로 이동하면 안 된다.

 

4. 바로 직전 레코드(LMC)가 가리키는 하위 블록으로 이동해야 첫 번째 리프 블록 맨 마지막에 저장된 레코드를 빠뜨리지 않을 수 있다.

 

즉, 수직적 탐색은 조건을 만족하는 레코드를 찾는 과정이 아닌, 조건을 만족하는 첫 번째 레코드를 찾는 과정

 

수직적 탐색시 루트를 포함한 브랜치 블록은 이정표나 팻말 역할을 하는데, 조건을 만족하는 첫 번째 레코드가 목표 지점으로, 팻말을 만날 때마다 어느 쪽으로 가면 목표 레코드를 만날 수 있는지 확인하면서 이동

 

-> 팻말을 따라 이동시 조건을 만족하는 첫 번째 레코드 발견 가능

---

4. 인덱스 수평적 탐색

:수직적 탐색을 통해 찾은 스캔 시작점을 이용해, 찾고자 하는 데이터가 더 이상 나타나지 않을 때까지 인덱스 리프 블록을 수평적으로 스캔

 

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

 

양방향 연결 리스트 구조인, 인덱스 리프 블록은 서로의 앞뒤 블록에 대한 주소값을 갖기 때문에

좌에서 우로, 또는 우에서 좌로 수평적 탐색이 가능하다.

 

인덱스를 수평적으로 탐색하는 이유

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

2. ROWID를 얻기 위해서

 

-> 필요한 칼럼을 인덱스가 모두 갖고 있는 경우 인덱스만 스캔하고 종료되지만, 일반적으로는 인덱스를 스캔 후 테이블도 액세스하는 과정을 거치는데, 이 경우 ROWID가 필요하다.

 

---

5. 결합 인덱스 구조와 탐색

: 두 개 이상의 칼럼을 결합해 인덱스를 만드는 결합 인덱스

 

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

1. 찾고자 하는 레코드를 인덱스에서 찾기 위해서 루트 블록 스캔

2. 루트 블록 스캔해서 찾고자 하는 값보다 큰 첫 번째 레코드 발견

3. 그 레코드가 가리키는 하위 블록으로 이동해서 찾기

4. 찾지 못했으므로, 바로 직전 LMC 레코드가 가리키는 하위 블록, 즉 왼쪽 브랜치 블록으로 이동

5. 이 레코드가 가리키는 하위 블록으로 내려가 찾았지만, 발견 못함

6. 따라서 바로 직전 레코드가 가리키는 하위 블록으로 이동

7. 리프 블록에 도달했으므로, 조건에 맞는 레코드 찾기

8. 리프 블록은 인덱스 키값 순으로 정렬 되어있으므로 찾고자 하는 레코드보다 큰 값을 만나면 멈춘다.

 

고객명 '이재희'찾기

1. 성별이 '남'이면서 '최'씨 성을 가진 레코드 ('남' & '최')

2. 그 레코드가 가리키는 하위 블록으로 내려가 첫 번째 남자 '이재희' 발견 못함

3. 바로 직전 LMC가 가리키는 하위 블록 즉, 왼쪽 브랜치 블록으로 이동

4. 왼쪽 브랜치 블록을 스캔하다가 찾고자 하는 값보다 큰 첫 번째 레코드 발견

5. 성별이 '남'이면서 '정재우'로 시작하는 이름을 가진 레코드 ('남' & '정재우')

6. 이 레코드가 가리키는 하위 블록으로 내려가 첫 번째 남자 '이재희' 발견 못함

7. 바로 직전 레코드 ('남' & '이재룡')이 가리키는 하위 블록으로 이동

8. 리프 블록에 도달했으므로, 남자 '이재희'찾기

9. 인덱스 키값 순이므로, '남' & '이재희'보다 큰 값을 만날 경우 멈춘다.

 

-> 수직적 탐색을 거쳐서 찾은 인덱스 시작점이 성별='남'이 아니라, 성별='남'이면서 고객명='이재희'인 레코드

 

 

인덱스 칼럼 순서 바꾸기

: 성별과 고객명 기준에서 바꿔서 고객명과 성별 순으로 구성한 인덱스

 

[고객명 + 성별]과 [성별 + 고객명]은 읽는 인덱스 블록 개수가 똑같다.

즉, 인덱스를 어떻게 구성하든 블록 I/O 개수가 같고, 개수가 같기 때문에 성능도 똑같다.

 

---

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

 

인덱스 성별 여자 이름 유관순

1. 인덱스를 [성별 + 이름] 순으로 구성

: 총 사원 50명 중에서 성별 = '여자'인 레코드 25건, 이름 검사해 최종적으로 2명 출력 -> 25번 검사

 

2. 인덱스를 [이름 + 성별] 순으로 구성

: 총 사원 50명 중에서 이름='유관순'인 레코드 2건을 찾고, 거기서 성별을 검사해 최종적으로 2명 출력 -> 2번 검사

 

검사 횟수를 줄이기 위해 -> 선택도가 낮은 '이름' 칼럼을 앞쪽에 두고 결합인덱스 생성

 

-> 인덱스 탐색 과정을 액셀의 데이터 필터 기능처럼 이해하는 방법

 

B*Tree 인덱스는 다단계 구조로, 액셀처럼 평면 구조가 아니기 때문에

 

루트에서 브랜치를 거쳐 리프 블록까지 탐색하면서, '여자'이면서 '유관순'인 첫 번째 사원을 바로 찾아간다.

 

즉, 거기서부터 두 건을 스캔하므로, 유관순이 아닌 레코드를 만날 때까지 세 건을 스캔

 

따라서 어느 칼럼이 앞에 있든 일량에는 차이가 없다.

 

---

Balanced

: delete 작업에 의해 인덱스가 불균형 상태에 놓일 수 있다.

[다른 리프 노드에 비해 루트 블록과의 거리가 더 멀거나 가까운 리프 노드 발생]

B*Tree 인덱스에서는 발생하지 않는다. [B : Balanced의 약자]

 

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

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