20180218 데이터베이스 인덱스(Index) : 인덱스 기본

해당 글은 전적으로 [ 꿈꾸는 개발자, DBA 커뮤니티 구루비 ] 에서 참고하였음을 밝힙니다. 개인 공부 및 기록을 위한 글입니다. 따라서 옮기는 과정에서 경어체는 모두 제거하였으며, 본인의 관점으로 글을 작성하였습니다. 상세하고 정돈된 내용은 하단에 참고링크를 보시길 바랍니다.

인덱스 종류

트리기반 인덱스

• DBMS에서 가장 일반적인 인덱스
• B Tree 인덱스는 브랜치 블록과 리프 블록으로 구성
• 브랜치 블록 중 가장 상위에 있는 블록은 루트 블록이다.
• 브랜치 블록은 분기를 목적으로 하는 블록
• 리프 블록은 트리 가장 아래 단계에 존재
• 이진트리와는 다르게 하나의 노드가 여러  자식을 가질 수 있다. 따라서 트리의 높이가 낮아진다.
• 리프 블록은 인덱스를 구성하는 컬럼의 데이터와 해당 데이터를 가지는 행의 위치를 가리키는 레코드 식별자로 구성 ( 생성 컬럼의 데이터 값 + Table Row의 Row ID )
• 인덱스 데이터는 인덱스를 구성하는 컬럼의 값으로 정렬된다.
• 인덱스 데이터의 값이 동일하다면, 레코드 식별자 순서로 저장된다.
• 리프 블록은 양방향 링크를 가지고 있으며 이를 통해 오름차순 및 내림차순 검색을 쉽게 할 수 있다.
• B Tree 인덱스는 "=", "BETWEEN", ">", "<" 등과 같은 연산자로 검색구조에 적합한 구조이다.

아래의 그림은 emp 테이블에서 SELECT 쿼리문을 수행하는 내용이다.

(1) 인덱스를 ename 컬럼으로 설정하고 ename 이 "Davis" 인 값을 찾는다.

(2) 브랜치 블록의 값을 기준으로 작으면 왼쪽 포인터, 값 사이에 존재하면 가운데 포인터, 값보다 크면 오른쪽 포인터로 이동한다. 

(3) (2)의 과정을 반복하다 해당 ename이 "Davis" 인 값을 찾아서 조회한다.

SQL Server의 클러스터형 인덱스

SQL Server의 인덱스 종류는 저장 구조에 따라 클러스터, 논클러스터형 인덱스로 구분된다. 

클러스터형 인덱스에는 두가지 특징이 존재한다.

(1) 인덱스 리프 페이지가 곧 데이터 페이지이다. 테이블 탐색에 필요한 레코드 식별자가 리프페이지에 없다. ( 테이블 = 인덱스 )

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

(2) 리프 페이지에서 모든 로우(=데이터)는 인덱스 키 컬럼의 순으로 물리적 정렬되어 저장된다.

- 테이블 로우는 물리적으로 한가지 순서로만 정렬될 수 있다. 따라서 클러스터형 인덱스 테이블당 한개만 생성할 수 있다.  예를 들어 전화번호부 한 권을 상호와 인명으로 동시 정렬할 수 없는 것과 동일한 이야기이다.

EmployeeID, LastName, FirstName, HireDate 총 네가지 컬럼으로 구성된 employees 테이블이다. 해당 테이블은 EmployeeID에 기반한 클러스터형 인덱스를 생성한 모습이다.

Full Table Scan & Index Table Scan

[ 옵티마이저 접근 경로 ]

- Full Table Scan 

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

오라클의 경우 그림과 같이 검색 조건에 맞는 데이터를 찾기 위해 테이블의 (HWM : High Water Mark) 아래의 모든 블록을 읽는다. 

HWM (=High Water Mark) 란?

테이블에 데이터가 쓰여졌던, 마지막까지 등록된 블록 최상위 위치를 의미한다. (데이터가 지워져서 존재하지 않을 수도 있다.) HWM은 증가하기만 한다. truncate 명령을 이용하면 Header Block의 위치로 되돌아간다. (0으로 set) Delete 명령은 HWM에 변화를 주지 않는다. 

Full Table Scan을 하는 경우 HWM까지의 블록 내 모든 데이터를 읽어야하기 때문에 모든 결과를 찾을 때까지 시간이 오래 걸릴 수 있다. 옵티마이저가 연산으로 Full Table Scan을 선택하는 이유는 다음과 같다.

• SQL문에 조건이 존재하지 않은 경우

• SQL문의 주어진 조건에 사용 가능한 인덱스가 존재하지 않는 경우

• 옵티마이저의 취사선택 (조건을 만족하는 데이터가 많은 경우, 결과 추출을 위해서 대부분의 블록을 액세스해야 한다고 옵티마이저가 판단)

• 그 밖의 경우 (병렬처리 방식, Full Table Scan 방식의 힌트를 사용한 경우)

- Index Scan

- 인덱스 스캔은 인덱스를 구성하는 컬럼의 값을 기반으로 데이터를 추출하는 방식

- 인덱스 리프 블록은 인덱스를 구성하는 컬럼의 값과 레코드 식별자 RowID로 구성

- 인덱스는 인덱스 구성 컬럼의 순서로 정렬

(1) Index unique scan

유일 인덱스는 중복을 허락하지 않는다. 유일 인덱스 구성 컬럼에는 모두 "=" 의 구성이다. 중복되지 않은 유니크한 값을 "=" 조건으로 검색할 경우 해당 데이터 한 건을 찾는 순간 더 이상 탐색하지 않는다.

(2) Index range scan

인덱스를 이용하여 최소 한 건 이상의 데이터를 추출하는 방식이다. 컬럼 모두에 대해 "=" 로 값이 주어지지 않은 경우(BETWEEN, LIKE, 부등호 등)와 non-unique index 를 이용한 스캔방식으로 데이터를 액세스한다.

루트 블럭에서 리프 블럭까지 수직적으로 탐색한 후 리프 블럭을 필요한 부분만 스캔하는 방식이다. 가장 일반적으로 이용되는 액세스 방식이다.

스캔하는 범위(Range)를 얼만큼 줄일 수 있느냐가 관건이다. 

(3) Index range scan descending ( 기본 )

인덱스 리프블록의 양방향 링크를 이용하여 내림차순으로 데이터를 읽는 방식이다. 이 방식을 이용해서 최대값을 쉽게 찾을 수 있다.

(4) Index Full Scan

수직적 탐색 없이 인덱스 리프 블록을 처음부터 끝까지 수평적으로 탐색하는 방식이다. 최적의 인덱스가 없을 때 차선으로 선택하며 Table Full Scan 보다 I/O를 줄일 수 있거나 정렬된 결과를 쉽게 얻을 수 있을 경우 사용한다.

Full Table Scan vs Index Scan

풀 스캔과 인덱스 스캔의 차이점은 대용량 데이터 중 극히 일부의 데이터를 찾을 때 인덱스 스캔 방식을 이용하면, 몇번의 I/O 만으로도 데이터를 찾을 수 있고, 전체 테이블 스캔은 모든 데이터를 읽으면서 원하는 데이터를 찾아야 하므로 비효율적인 검색을 한다. 

[ 참고링크 ]

[ 제2절 인덱스 기본 ]

[ B-tree 인덱스 & B-tree 인덱스 구조 ]

[ 비트맵 인덱스 ]

[ 비트리 인덱스 ]

[ 다양한 인덱스 스캔 방식 ]