[매일메일] 데이터베이스 인덱스에 대해서 설명해주세요

 

인덱스는 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조이다. (백과사전의 색인과 같음)

저장되는 칼럼 값을 사용하여 항상 정렬된 상태를 유지하는 것이 특징이다.

-> 이런 특징으로 인해 인덱스는 INSERT, UPDATE, DELETE의 성능이 희생된다는 것이 단점 (??)

 

MySQL, InnoDB를 기준으로 B+Tree와 같은 변형 B-Tree 자료구조를 이용해서 인덱스를 구현한다.

B-Tree 인덱스는 컬럼의 값을 변형하지 않고 인덱스 구조체 내에서 항상 정렬된 상태로 유지한다.

 

여기서 B-Tree란, 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종,

이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조.

이런 식으로 여러 개의 (2개 이상의) 자식을 가질 수 있음.

B 트리의 데이터 삽입과정은 다음과 같다

1. 트리가 비어있다면 루트 노드를 할당하고 K를 삽입한다.

2.트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.

3. 리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료 한다.

4. 리프 노드가 부적절한 상태에 있다면 분리한다.

 

다시 돌아가서

B-Tree(Balance tree)에서는 3가지 노드가 존재한다. 최상위에 하나의 루트 노드가 존재하며, 가장 하위 노드인 리프 노드가 존재한다. 이 두 노드 중간에 존재하는 브랜치 노드가 존재한다. 최하위 노드인 리프 노드에는 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있다.

 

InnoDB 스토리지 엔진에서는 세컨더리 인덱스(프라이머리 인덱스를 제외한 모든 인덱스)의 리프 노드에는 레코드의 PK가 저장된다. 세컨더리 인덱스 검색에서는 레코드를 읽기 위해 PK를 가지고 있는 B-Tree를 다시 한 번 검색해야한다.

 

MySQL의 스캔 방식은?

1. 인덱스 레인지 스캔

: 검색할 인덱스 범위가 결정되었을 경우 사용, 가장 빠름

 - 인덱스에서 조건을 만족하는 값이 저장된 시작 리프 노드를 찾음 (index seek)

 - 시작 리프 노드부터 필요한 만큼 인덱스를 차례대로 읽는다. (index scan)

 - 인덱스 키와 레코드 주소를 이용해 저장된 페이지를 가져오고 레코드를 읽어온다.

 

레코드를 읽어오는 과정에서 랜덤 IO가 발생할 수 있음. 읽어야 할 데이터 레코드가 전체 20-25%인 경우 풀 테이블 스캔(순차 IO 이용)이 더욱 좋을 수 있음.

 

2. 인덱스 풀 스캔

: 인덱스를 사용하지만 인덱스를 처음부터 끝까지 모두 읽는 방식

  - 인덱스를 ABC 순서로 만들었는데 조건절에 B or C로 검색하는 경우 사용됨

  - 인덱스를 생성하는 목적은 아니지만, 그래도 풀 테이블 스캔보다는 나음

 

3. 루트 인덱스 스캔

: 듬성듬성하게 인덱스를 읽는 것을 의미(인덱스 레인지, 인덱스 풀 스캔은 타이트 인덱스 스캔으로 분류됨)

  - 중간에 필요하지 않은 인덱스 키 값은 무시하고 다음으로 넘어가는 형태로 처리한다

  - group by, max(), min() 함수에 대해 최적화 하는 경우에 사용됨