(Database) 인덱스(index)가 뭐고 왜 쓸까?

1. 들어가며 🙌

---

수 많은 데이터가 저장되어 있는 데이터베이스를 상상해보자.
100개, 1000개, 10000개, 100000개...

그리고 여기에서 한 데이터를 찾는 select연산을 수행한다고 상상해보라.
(마치 배열에서 선택정렬을 한다고 생각하는 것과 같다.)

그렇다면 데이터의 수 만큼 탐색 시간이 늘어날 것이다.

그리고 우리는 생각한다.
어떻게 하면 탐색 시간을 줄일 수 있을까?

자료구조를 배웠다면 힌트를 얻을 수 있을 것이다.

퀵정렬이 왜 빠른가? 바로 기준점이 있기 때문이다.

그렇다. 지금하려는 인덱스도 데이터베이스의 기준점에 대해서 얘기한다.

2. 인덱스가 뭘까? (왜 써?)

---

인덱스는 데이터베이스 테이블에 대한 검색 성능을 높여주는 자료구조이다.

그렇다. 인덱스를 사용하는 이유는 검색 성능을 높여주기 위해서이다.

검색 성능이라는 것은 무엇을 말할까?

SELECT, DELETE, UPDATE 등의 연산을 할 때에는 데이터베이스에서 '조회' 라는 절차가 반드시 이루어진다.

이 때 조회가 검색을 하는 것이고, 검색성능의 향상은 곧 CRUD 중에서 RUD의 성능 향상을 수반한다.
(중복검사의 경우 C에도)

3. 인덱스는 어떻게 구현되어 있을까? (인덱스의 구조)

---

인덱스는 주로 해시 테이블과 B+Tree로 구현할 수 있다.

이 글에서는 B+Tree에 대해 살펴 볼 것이다.

B+Tree에 대한 이해를 하려면 B-Tree에 대한 이해가 필요하다.

B-Tree

B-Tree는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로,
이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조(이진트리는 2개)이다.

B-Tree를 사용하면 자료를 효율적으로 검색할 수 있는 것은 바로 B-Tree가 데이터를 정렬 된 상태로 보관하기 때문이다.

이 정렬된 방식은 우리에게 삽입 및 삭제를 상수 시간으로 할 수 있도록 만들어 준다.

어덯게 이게 가능할까? 그 비결은 바로 노드의 구성에 있다. B-Tree의 노드의 구조를 살펴보자

B-Tree의 노드는 대게 항목과 자식 포인터의 순서 집합으로 표현된다.
루트 노드를 제외한 모든 노드는 임의의 수 L, U(L<U)에 대해 최소 L항목, 최대 U항목을 가지고 있으며,
최대 U+1개의 자식 포인터를 가지고 있다.

탐색 알고리즘은 이진 탐색 트리와 같다.

루트 노드에서 하향식으로 탐색하며, 탐색하려는 값을 구분 값과 비교하여 자식 포인터를 찾아 나가는 과정이다.

B+Tree

그럼 B-Tree와 B+Tree는 뭐가 다를까?
B+Tree는 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드를 추가로 가지고 있다.

(이 구조에 대해서는 더 상세한 포스팅이 필요할 것 같다.)

이 비단말 노드 덕분에 (사실상 pivot역할을 하는 친구) 빠르게 검색을 할 수 있는 것이다.

4. 인덱스의 장단점은?

---

앞에서 우리는 인덱스를 사용하는 이유에 대해서 알아보았다.
그리고 인덱스가 정렬이 되어 있다는 것도 알 수 있었다.

여기에서 오는 장점은 실로 엄청나다.

최대값과 최소값을 가져올 때 양 끝단의 값을 가져오면 되고,

orderBy 쿼리 문을 사용할 때도 별다른 정렬이 필요 없다.

또한 검색이 매우 빠르기 때문에 전체적인 데이터베이스에 가해지는 부하가 적어진다.

하지만 이렇게 강력한 인덱스에도 단점이 존재한다.

인덱스의 단점

인덱스 얘기가 나올 때 마다 항상 Trade-off가 등장한다.
그럼 어떤 부분에서 손해를 볼까?

첫 번째로, 항상 인덱스를 정렬된 상태로 유지해야한다는 단점이 있다.

이 문제는 주로 삽입, 삭제, 업데이트에서 발생한다.

두 번째로, 인덱스를 위해서 DB의 약 10%에 해당하는 저장공간이 필요하다.

세 번째로, 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고 그 이상의 데이터를 처리할 땐
인덱스를 사용하지 않는 것이 더 낫다.

5. 정리

---

인덱스를 잘 알고 적재적소에 사용해야한다.