SQLP - 인덱스 기본 원리

@markdown

## 인덱스 특징과 종류

____

- 인덱스는 DB에서 원하는 데이터를 쉽게 찾을 수 있도록 도와준다.

- 테이블을 기반으로 선택적으로 생성할 수 있는 구조

- 인덱스의 목적은 검색 성능의 최적화 및 검색조건에 만족하는 데이터를 효과적으로 찾는 것 이다.

- Oracle의 트리 기반 인덱스 종류 : B-트리, Bitmap, Reverse Key, Function-Based 등이 존재한다.

### 트리 기반 인덱스


- DBMS에서 가장 일반적인 인덱스(B-트리 인덱스)

- B-트리 인덱스는 브랜치, 리프 블록 그리고 가장 상위 루트 블록으로 구성된다.

- 브랜치 블록은 분기를 목적으로 하고, 다음 단계 블록을 가리키는 포인터를 가지고 있다.

- 리프 블록은 인덱스를 구성하는 칼럼의 데이터와 해당 데이터가 있는 위치를 가리키는 레코드 식별자(Record ID)로 구성되어 있다.

- 리프 블록은 양방향 링크를 가지고 있어 `오름차순`과 `내림차순` 검색을 쉽게 할 수 있다. 

- B-트리 인덱스는 `=`로 검색하는 일치검색과 `BETWEEN`, `>`과 같은 연산자로 검색하는 범위검색 모두에 적합한 구조이다.

### B-트리 인덱스 데이터 검색과정

- 1. 브랜치 블록의 가장 왼쪽 값이 찾고자 하는 값보다 작거나 같으면 왼쪽 포인터로 이동

- 2. 찾고자 하는 값이 브랜치 블록의 값 사이에 존재하면 가운데 포인터로 이동

- 3. 오른쪽에 있는 값보다 크면 오른쪽 포인터로 이동

- 위 과정을 만족하는 리프 블록을 찾을 때까지 반복한다.(그림 2-3-7은 그 과정을 나타낸 것)


#### 37 데이터를 찾는 과정

- 루트 블록 50보다 작으므로 왼쪽 포인터[11,40]으로 이동

- 37이 11과 40 사이 값이기 때문에 가운데 포인터[35,37,40]로 이동

- 가운데 포인터로 이동하여 37이 이동한 블록에 존재하는지 검색한다.

- 검색 결과 해당 리프 블록에 37이 존재하므로 데이터를 찾음

## SQL Server의 클러스터형 인덱스

____

- 인덱스 종류 : 클러스터형 인덱스, 비클러스터형 인덱스로 나뉜다.

### 클러스터형 인덱스 특징


- 인덱스의 리프 페이지가 곧 데이터 페이지(레코드 식별자가 없음)

- 클러스터형 인덱스의 리프 페이지를 탐색하면 해당 테이블의 모든 컬럼 값을 바로 얻을 수 있다.

- 리프 페이지의 모든 데이터는 인덱스 키 칼럼의 순으로 물리적인 정렬이 되어 저장된다.(한 가지 순서로만)

- 그림 2-3-8에서 Employees_PK 한가지 순서로 정렬되어 있고, 인덱스 키 칼럼외에 나머지 칼럼이 함께 있다.

## 전체 테이블 스캔과 인덱스 스캔

____

### 전체 테이블(Full Table Scan) 스캔

- 테이블에 존재하는 모든 데이터를 읽어가며 검색 조건에 맞으면 결과로 추출, 맞지 않으면 버리는 방식이다.


- Oracle의 경우 검색 조건에 맞는 데이터를 찾기 위해 테이블의 고수위 마크(High Water Mark) 아래의 모든 블록을 읽는다.

- HWM(고수위 마크)는 테이블에 데이터가 쓰여졌던 블록 상의 최상위 위치를 의미

- HWM까지 테이블의 모든 데이터를 읽어야 하기 때문에 모든 결과를 찾을 때까지 시간이 오래 걸림

- Full Table Scan 연산으로 읽은 블록들은 재사용성이 떨어지기 때문에, 메모리에서 곧 제거될 수 있도록 관리한다.

### 인덱스 스캔(Index Scan)

- 인덱스를 구성하는 칼럼의 값을 기반으로 데이터를 추출하는 액세스 기법

- 리프 블록은 인덱스 구성의 칼럼 값과 레코드 식별자로 구성되어 있다.

- 인덱스에 존재하지 않는 칼럼의 값이 필요한 경우 현재 읽은 레코드 식별자를 이용하여 테이블을 액세스 해야한다.

- SQL문에 필요로 하는 모든 칼럼이 인덱스 구성 칼럼에 포함된 경우 테이블에 대한 액세스는 발생하지 않는다.

- 인덱스 스캔 종류 : 인덱스 유일 스캔(Index Unique Scan), 인덱스 범위 스캔(Index Range Scan), 인덱스 역순 범위 스캔(Index Range Scan Descending)

### 인덱스 유일 스캔(Index Unique Scan)

- Unique 인덱스를 사용하여 단 하나의 데이터를 추출하는 방식

- 유일 인덱스는 중복을 허락하지 않는다.

- 인덱스 구성 칼럼에 모두 `=`로 값이 주어지며, 결과는 최대 1건이다.

- 유일 인덱스 구성 칼럼에 대해 모두 `=`로 값이 주어진 경우에만 사용가능

### 인덱스 범위 스캔(Index Range Scan)

- 인덱스를 이용하여 한 건 이상의 데이터를 추출하는 방식

- 인덱스 구성 칼럼이 `=`로 값이 주어지지 않은 경우와 Non-Unique 인덱스를 이용하는 모든 액세스 방식이 인덱스 범위 스캔이다.


- 기본 인덱스 범위 스캔은 인덱스 리프 블록의 양방향 링크를 이용하여 왼쪽에서 오른쪽으로 스캔, 역순 범위 방식은 오른쪽에서 왼쪽으로 데이터를 스캔한다.

### 전체 테이블과 인덱스 스캔 방식의 비교


- 인덱스 스캔은 인덱스에 존재하는 레코드 식별자를 이용해서 검색하는 데이터의 정확환 위치를 알고서 데이터를 읽는다.

- 한번의 I/O 요청에 한 블록씩 데이터를 읽는다. 따라서 대용량 데이터 중에 일부의 데이터를 찾을 경우 몇 번의 I/O만으로 원하는 데이터를 쉽게 찾을 수 있다.

> SQL 전문가 가이드 : 제3장 SQL 최적화 기본 원리 - 제2절 인덱스 기본(p.454 ~ p.460)

> 사진 출처 : 구루비넷