[DB] 인덱스 사용 이유 이해하기

Intro

DB에 데이터 양이 많다면 쿼리 수행이 느리다.

쿼리의 성능을 높이기 위해 인덱스를 잘 활용하는 것이 좋다.

 

"인덱스: DB 테이블 검색 성능을 높여주는 자료구조"

 

.

.

 

★ 참고로, 아래 영상의 도움을 크게 받아 정리했다. 강추한다.

https://www.youtube.com/watch?v=iNvYsGKelYs

 

 

---

INDEX란?

테이블 검색 성능을 높여주는 자료구조라고 했다.

어떤 자료구조길래?

 

.

.

 

person 테이블에서 age가 25인 행을 찾고 싶다.

그렇다면 다음과 같은 select문이 익숙할 것이다.

SELECT * FROM person WHERE age = 25

 

그런데 데이터가 막 10억개로 무지 많은 상황에서 모든 행을 다 뒤져 찾는다면, age = 25를 찾는 것이 무지 느리다.

즉 index가 없는 경우 조회가 매우 느리게 된다.

 

 

이럴 때 index를 사용한다.

이진 탐색을 알 것이다.

컬럼을 따로 sort해 둔 상태에서 절반씩 소거하며 원하는 데이터를 빠르게 찾을 수 있다.

 

다시말해 age컬럼을 복사해서, 미리 sort해두고, 원하는 데이터를 빠르게 찾는 것이다.

그렇게 탐색 목적으로 정렬해 둔 컬럼 사본을 index라고 부른다. 

 

 

 

 

---

INDEX의 정렬 방식

 

sort해둔 컬럼 사본이 index고, 이진 탐색을 통해 빠른 데이터 조회가 가능하다고 했다.

그런데 그 sort은 어떻게 이루어질까?

 

sort라고 하면 가장 먼저 간단히 ArrayList나 LinkedList를 떠올릴 것이다.

데이터베이스는 Tree 구조를 사용한다.

산발되어있는 데이터를 연결연결만 해 둬서 Tree구조로 크고 작음을 저장해두는 것이다.

즉, age컬럼의 4 2 6 1 3 5 7 데이터는 아래와 같은 Tree 구조로 sort된다.

즉, index는 Tree 구조로 자료들을 배치해둔다.

 

Binary Search Tree

 

위 Binary Search Tree에서 노드당 데이터(key) 하나씩으로 구성되어있다.

여기서 '조금 다른 트리 구조'를 사용한다면 성능을 더 강화할 수 있다.

노드당 데이터(key) 하나씩이 아니라, 노드당 데이터(key) 두세개씩 두자는 거다.

이것은 B-Tree라는 자료구조로, 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조이다. 이진 트리를 확장한 것인데, 특별한 점은 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조다. 항상 정렬된 상태로 저장된다.

 

아래 B-Tree를 위 BST와 비교해보면, 단 두번의 이동으로 더 많은 데이터를 검색할 수 있음이 보인다.

 

B-Tree

 

 

그러나 실제 요즘 데이터베이스에서는 B-Tree보다 더욱 검색 성능이 개선된 B+Tree를 사용한다.

데이터를 노드마다 보관하는 것이 아닌, 리프노드에만 데이터를 보관한다.

여기서 리프노드들간에도 link되어있다!

그래서 "범위 검색"이 아주 쉬워진다는 장점이 있다. 

 

4부터 8까지의 데이터를 찾겠다고 해보자.

아까 본 B-Tree는 4, 5, 6, 7, 8을 찾기 위해 4 6 5 6 7 6 8을 거치는데, (inorder traversal)

이번에 보는 B+Tree는 리프노드로 가서 쭈루룩 4 5 6 7 8을 읽어들이면 된다.

 

B+Tree

 

 

참고로, 데이터베이스에서 O(1)인 해시테이블을 사용하지 않는 이유는 연속적인 순차 검색 (부등호 >, <를 생각하라)이 불가능하기 때문에 부적합하다. B+Tree는 O(log2N)이긴 하지만, 앞서 설명한 이유로 리프노드가 linked 상태이므로 순차 검색이 용이하다.

 

 

 

 

---

INDEX에서 검색 후 자료 가져오는 동작 방식

 

탐색 목적으로 정렬해 둔 컬럼 사본을 index라고 부른다고 했다.

index 구조가 존재하는 경우 index에서 조회를 하며, 조회를 성공하면, index와 연결된 '원래 테이블 행' 주소를 타고 들어가서 데이터를 가지고 오는 방식으로 동작한다.

 

 

 

---

INDEX의 단점

 

1. index는 컬럼을 복사해 정렬해두는 자료구조이므로, DB 용량을 차지한다.

└ 따라서, 검색작업이 필요 없는 컬럼은 굳이 index를 만들 필요가 없다.

 

2. 기존 테이블 데이터에 삽입, 수정, 삭제가 일어나면 index에도 똑같이 반영해줘야 한다. 데이터 정렬 상태 또한 변동이 일어난다. 따라서 성능 저하가 일어날 수 있다.

└ 따라서,  DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 index를 생성하는 것이 좋다.

└ index 생성을 남발하는 것보다 sql을 최적화하는 것이 우선시되어야 한다. index를 남발하면 하나의 쿼리문을 빠르게 할 수는 있어도 DML 사용시 전체적인 성능 저하가 지속될 것이다.

 

* 참고: PK는 이미 정렬상태기 때문에 index를 만들 필요가 없다.

└ clustered index라고 부른다. clustered index는 데이터가 테이블에 물리적으로 저장 되는 순서를 정의한다. 즉 clustered index 는 특정 컬럼을 기준으로 데이터들을 정렬시킨다.

 

 

---