[DB] Index란?

📖 Index(인덱스)

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

 

인덱스를 사용하면 데이터베이스에서 원하는 정보(레코드, 튜플)를 빠르게 조회할 수 있다.

인덱스는 튜플의 주소라고 생각하면 쉽다. (인덱스에 키를 대응시키고 튜플에 값을 대응시켜보자)

또한 인덱스는 정렬되어 있다.

 

인덱스를 이루는 자료구조

인덱스를 구현하기 위한 자료구조로 대표적인 것은 B-Tree와 해시 테이블이다.

 

1️⃣ B(Balanced)-Tree 인덱스

B-Tree는 데이터베이스의 인덱싱 알고리즘 가운데 가장 먼저 도입되고 가장 일반적으로 사용되는 알고리즘으로 트리 구조를 따른다.

(트리구조 : 루트 노드, 브랜치 노드, 리프 노드로 구성되는 형태)

트리의 리프 노드가 실제 데이터 레코드를 찾아가기 위한 주소 값(키 값)을 가지고 있다. 모든 노드들이 데이터를 가진다.

그리고 인덱스의 키 값은 빠른 탐색을 위해 정렬되어 있다.

하지만 키 값에 대응되는 레코드는 정렬 되어 있을 수도 있고 아닐 수도 있다.(대부분 RDMS에는 레코드들이 정렬되지 않고 저장된다.)

 

인덱스는 페이지 단위로 저장된다.(페이지? 👉 디스크와 메모리에 대해 데이터를 읽고 쓰는 최소의 단위로 블록이라고도 한다.)

레코드를 찾는 순서를 간단하게 살펴보면

1. 데이터를 따라서 리프노드에 도달하면 인덱스 키에 해당하는 레코드의 PK 값이 저장되어 있다.
2. 이후 PK를 따라 리프노드에서 실제 레코드를 읽어온다.

위와 같다. 즉, 인덱스를 통해서 데이터를 조회하면 인덱스를 통해 PK를 찾고 👉 PK를 통해 레코드를 찾는 2가지 작업이 수행되는 것이다.

그렇기 때문에 모든 테이블을 뒤져서 레코드를 찾는 것보다 레코드를 찾는 속도가 훨씬 빠르다.

 

2️⃣ 해시 테이블 인덱스

해시 테이블은 데이터를 Key : Value 쌍으로 저장하는 자료구조로, 빠른 데이터 검색이 필요할 때 유용하다.

key값을 이용해서 고유한 인덱스를 생성한 후, 그 인덱스에 저장된 값을 읽어오는 구조이다.

해시 테이블의 시간 복잡도는 O(1)로 매우 빠른 검색을 지원한다.

 

레코드를 찾는 순서를 간단하게 살펴보면

1. 검색하고자 하는 값을 넘기면
2. 해시 함수를 거쳐서 찾고자 하는 key 값이 포함된 버킷을 찾아내고
3. 버킷 안에서 실제 레코드가 저장된 위치를 찾는 순서로 검색이 이루어진다.

그래서 트리 내의 여러 노드를 거쳐서 검색하는 B-Tree에 비해서 속도가 빠르다.

 

하지만 해시 테이블 자료구조는 동등 비교 검색에 최적화 되어있다.(DB 인덱스에서 해시 테이블이 사용되는 경우도 적다.)

만약 해시 함수의 값이 1이라도 달라지면 기존 해시 값과 완전히 다른 해시 값을 생성한다.

그렇기 때문에 부등호 연산이 자주 사용되는 데이터베이스 검색에는 적합하지 않다.

 

예시를 들어보면

💡 동등 비교인 경우

"12345"라는 key를 가진 데이터를 해시 테이블에 저장했다고 가정하자

1. 해시 함수는 "12345"를 입력받아 특정 인덱스(예: 7번 버킷)으로 매핑한다.
2. 이제 "12345"를 검색할 대 해시 함수가 다시 같은 결과(7번 버킷)를 생성하므로 데이터는 곧바로 7번 버킷에서 검색된다.
3. 즉, 해시 값의 일치 여부를 통해 빠르게 동등성을 확인한다.(O(1))

💡 부등호 연산인 경우

"1", "2", "3", "4", "5"라는 키가 각각 다른 해시 값으로 변환되어 해시 테이블에 저장되어 있다고 가정하자

key "1" 👉 해시 값: 12AB34

key "2" 👉 해시 값: CDEF78

key "3" 👉 해시 값: 9A1B2C

..

여기서 볼 수 있듯 key 값이 "1"에서 "2"로 단 1 증가했음에도 해시 값은 전혀 다른 값으로 변한다.

해시 함수는 입력 간의 순서와 크기는 고려하지 않고 고유한 해시 값을 생성하기 때문이다.

1. 이 때 Key > 3 이라는 조건으로 검색한다고 하면
2. 해시 함수는 key를 고유한 해시 값으로 변환하므로 키의 크기나 순서를 알 수 없다. 또한 key가 정렬되어 있지도 않다.
3. 즉, 해시 테이블의 모든 데이터를 하나씩 확인해야 한다.(O(N))

3️⃣ B+-Tree 인덱스

B+-Tree 인덱스는 자식 노드가 2개 이상인 B-Tree를 개선한 자료구조이다.

B+-Tree 인덱스는 리프 노드만 인덱스와 함께 데이터를 가지고 있으며 다른 노드들은 인덱스만 가진다.

리프 노드들은 LinkedList로 연결되어 있어서 부등호를 이용한 순차 검색에 용이하다.

MySQL이 B+-Tree 구조를 가진다.

 

인덱스 스캔 방식

MySQL의 인덱스 스캔 방식에는 크게 인덱스 레인지 스캔, 인덱스 풀 스캔, 루스 인덱스 스캔이 있다.

 

1️⃣ 인덱스 레인지 스캔

인덱스 레인지 스캔은 검색할 인덱스 범위가 결정된 경우 사용되며 가장 빠른 스캔 방식이다.

SELECT * FROM EMPLOYEE WHERE NAME BETWEEN "Lemon" AND "Mango";

위와 같은 쿼리가 날아갔다고 해보자. 그리고 Employee 테이블의 name 칼럼에 인덱스가 걸려있다고 하자

쿼리의 실행 순서는

1. 인덱스 탐색 : 인덱스의 조건을 만족하는 값이 저장된 시작 리프 노드를 찾는다.
2. 인덱스 스캔 : 시작 리프 노드부터 필요한 만큼 인덱스를 순서대로 읽는다.
3. 랜덤 I/O : 읽어들인 인덱스와 PK를 사용해서 최종 레코드를 읽는다.

2️⃣ 인덱스 풀 스캔

인덱스 풀 스캔은 처음부터 끝까지 페이지를 이동하며 모든 인덱스를 읽는 스캔 방식이다.

 

만약 인덱스가 A, B, C 순서로 되어있고 쿼리의 조건절이 B 또는 C 칼럼으로 검색되면 이 때 인덱스 풀 스캔이 사용된다.

 

인덱스 풀 스캔은 인덱스를 사용한다고 하지 않는다. 하지만 모든 데이터 레코드들을 읽는 풀 테이블 스캔보다는 인덱스만 스캔하는 인덱스 풀 스캔이 분명히 성능이 낫기 때문에 사용된다. 

 

3️⃣ 루스 인덱스 스캔

루스 인덱스 스캔은 인덱스를 듬성듬성 읽는 스캔 방식이다.(위의 두 스캔 방식은 타이트 인덱스 스캔으로 분류)

 

중간에 필요하지 않은 인덱스 키 값은 무시하고 넘어간다.

Group by, max(), min() 함수에 대해 최적화 하는 경우에 사용된다.

 

참고 자료

https://mangkyu.tistory.com/286

[MySQL] B-Tree로 인덱스(Index)에 대해 쉽고 완벽하게 이해하기

https://mangkyu.tistory.com/96

[Database] 인덱스(index)란?