DataManagement - Index

다음 글은 MySQL을 기반으로 한 포스트입니다.

 

Tree : https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog

Index : 데이터베이스 내의 테이블의 검색 속도를 높이기 위해 사용되는 데이터 구조 (ex. B-tree 인덱스, Hash 인덱스, Fractal 인덱스)

Page(Block) : 데이터를 저장하는 단위(일정한 크기로, 일정한 수의 레코드가 저장되어짐)로써 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 작업 단위

쿼리를 통해 하나의 레코드만 읽고 싶더라도, 결국 하나의 블록을 읽어야 함.
따라서, 개별 데이터의 크기를 최대한 작게하여, 1페이지에 많은 데이터들을 저장할 수 있도록 함.

 

MySQL에서 사용되는 가장 일반적인 B-Tree 인덱스에 대해 알아보자.

 

B-Tree 인덱스

 B-Tree(Balanced Tree) 인덱스는 2개의 자식만을 갖는 이진 트리를 확장시켜 N개의 자식을 가질 수 있도록 고안된 것이며, 좌우 자식간의 균형이 항상 맞아야 한다는 의미에서 Balance Tree이다. 기본적으로 데이터를 트리 구조로 구성하여, 각 노드에 여러 개의 데이터 값이 저장되는데, 루트 노드에서 시작해 각 노드에서는 데이터 값의 범위를 비교하여 해당 노드에서 검색할 수 있는 데이터의 범위를 좁힌다. 이 과정을 반복하여 검색 대상을 빠르게 찾을 수 있다.

• 루트 페이지(노드) : 최상위에 존재하는 단 하나의 노드, 자식 페이지의 정보들이 저장됨
• 브랜치 페이지(노드) : 자식 페이지의 정보들이 저장됨
• 리프 페이지(노드) : 인덱스 키와 PK가 저장되어 있으며, 자식 페이지가 없고 해당 노드에서는 실제 데이터들과 연결된다.
• 인덱스 키 : 첫 번째 컬럼으로 기본적인 설정이 되지만, B-Tree 인덱스는 복합 인덱스 또한 지원하기 때문에

 

B-Tree 인덱스를 통한 데이터 읽기

 어떤 경우에 인덱스를 사용할지 판단하게 하려면 MySQL이 어떻게 인덱스를 이용해 실제 코드를 읽어내는지 알아야 한다.

 

1. Index Range Scan

 특정 범위의 값을 검색하는 방법. (실제 데이터들 - 리프 노드의 범위에 대한 검색)

SELECT * FROM table WHERE column1 > 10 AND column1 < 20;

루트 노드에서 인덱스 키와 비교를 해가면서 브랜치 노드를 거쳐 리프 노드(필요한 레코드의 시작위치)까지 찾아 들어가게 된다. 만약 리프노드의 끝까지 다 읽었다면 리프 노드 간 링크를 이용해 다음 리프 노드를 찾아 다시 스캔한다. 여기까지가 인덱스만 읽는 경우이다.

 인덱스를 다 스캔했다면, 실제 데이터 파일의 레코드를 읽어와야 할 수 있는데, 인덱스는 정렬되어있기 때문에 인덱스의 컬럼의 정순/역순으로 레코드를 가져오며, 또한, 리프 노드에서 검색 조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어올때 한 건당 랜덤 I/O가 발생한다.

랜덤 I/O는 데이터를 특정 위치에서 읽고 쓰는 입출력 작업을 말한다. 순차적으로 처리되는 시퀀셜 I/O와는 대조적으로 디스크나 메모리와 같은 저장 장치에서 특정 위치에 있는 데이터를 빠르게 찾고 읽거나 쓰는 작업이다.

 

2. 인덱스 풀 스캔

조건절에 사용된 컬럼이 인덱스의 첫번째 컬럼이 아니면 인덱스 풀 스캔이 일어남. 처음부터 끝까지 읽는 방식이라서 다른 방식보다 느리다.

 

3. 루스 인덱스 스캔

  인덱스 레인지 스캔과 비슷하게 작동하지만, 필요하지 않은 인덱스 키 값은 무시하고 넘어간다. 일반적으로 Group by 또는 MAX, MIN함수에 대해 최적화를 하는 경우 사용하게 된다.

 

인덱스 스킵 스캔

 조건절에 첫 번째 인덱스가 없어도 두 번째 인덱스 만으로 인덱스를 검색할 수 있게 해주는 기능, 8.0 버전부터 인덱스 스킵 스캔 최적화 기능이 도입되면서 옵티마이저가 A 컬럼을 건너 뛰어서 B, C 컬럼만으로도 인덱스 검색이 가능하게 되었다.

select * from example where col2='a' and col3='c';
--> 조건절에 사용된 컬럼이 인덱스의 첫 번째(A) 컬럼이 아니지만 B,C 컬럼만으로도 인덱스 검색이 가능하게 됐다.

 

다중 컬럼 인덱스

 인덱스에 2개 이상의 컬럼을 포함하는 인덱스가 사용된다. 이를 다중 컬럼 인덱스라고 한다. 여기서 두 번째 컬럼이 첫번째 컬럼에 의존해 정렬되어 있으며, 두 번째 컬럼이 첫 번째 컬럼과 같은 레코드에 있어야 의미가 있다는 것을 나타냄.

 

B-Tree 인덱스의 정렬 및 스캔 방향

인덱스를 생성하면, 인덱스를 어느 방향으로 읽을지는 옵티마이저가 실시간으로 만들어내는 실행 계획에 따라 결정된다. 이런 스캔 방향을 통해 오름차순/내림차순 정렬 효과를 얻을 수 있다.

내림차순 인덱스

InnoDB 스토리지 엔진은 인덱스 역순 스캔이 정순 스캔에 비해 느림.

• 페이지 잠금이 인덱스 정순 스캔에 적합한 구조
• 페이지 내에 인덱스 레코드가 단방향으로만 연결된 구조

 

비교 조건의 종류와 효율성

다음 예제로 비교 조건에 따라 인덱스의 효율이 어떻게 달라지는지 살펴보자.

SELECT * FROM example
WHERE col1 = 'ex' AND col2 >= 10 ;

• 케이스 A : 인덱스가 col1, col2인 경우
• 케이스 B : 인덱스가 col2, col1인 경우

케이스 A인 경우, 먼저 dept_no가 ‘d002’이고 emp_no가 10114보다 큰 레코드를 찾는다. 이후에는 dept_no가 ‘d002’가 아닐 때까지 인덱스를 쭉 읽기만 하면 된다. 하지만, 후자의 경우 다중 인덱스의 col2로 정렬되어 있기 때문에 더 많은 레코드들과 비교하면서 쿼리를 수해하기 때문에 더 많은 시간이 든다.

 

인덱스의 가용성

 B-Tree 인덱스의 특징은 값의 왼쪽 부분에 의존하여 오른쪽이 차례대로 정렬되는 것인데, 이는 왼쪽 부분이 없으면 인덱스 레인지 스캔이 불가능하다. 그 예로는 다음과 같다

select * from example where col1 like '%ple';

이는 비교 대상의 왼쪽 부분이 없기에, 인덱스를 효율적으로 사용할 수 없다. 이렇게 인덱스를 잘 사용하기 힘든 조건들은 다음과 같다.

• Not-Equal(not in, not between, is not null)
• LIKE %~, _~
• 스토어드 함수나 다른 연산자로 인덱스 컬럼이 변형된 후 비교된 경우
• 인덱스 컬럼의 타입을 변환해야 비교가 가능한 경우
• 문자열 데이터 타입의 콜레이션이 다른 경우