[Database] 인덱스 (Index)

 

인덱스란?

 

데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조 (특정 컬럼을 복사해서 정렬해 둔다!)

 

ex) 우리가 책에서 원하는 내용을 찾는다고 하면, 책의 모든 페이지를 찾아보는 것은 오랜 시간이 걸린다. 그렇기 때문에 책의 저자들은 보통 책의 맨 뒤에 색인을 추가하는데, 데이터베이스의 index는 책의 색인과 같다.

 

https://coding-factory.tistory.com/746

데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 주소를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕는다.

---

인덱스의 관리

 

DBMS는 index를 항상 최신의 정렬된 상태로 유지해야 원하는 값을 빠르게 탐색할 수 있다.

따라서 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면, 각각 다음과 같은 연산을 추가적으로 해주어야 하며 그에 따른 오버헤드가 발생한다.

 

- INSERT: 새로운 데이터에 대한 인덱스를 추가함

- DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행함

- UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가함

---

인덱스의 장단점

장점

 

👆 테이블을 조회하는 속도와 그에 따른 성능을 향상시킬 수 있다.

 

Where절에 특정 조건에 맞는 데이터들을 찾아낼 때 레코드의 처음부터 끝까지 다 읽어서 검색 조건과 맞는지 비교해야 한다. => 풀 테이블 스캔 (Full Table Scan)

인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건 (Where)에 맞는 데이터들을 빠르게 찾아낼 수 있다.

 

👆 전반적인 시스템의 부하를 줄일 수 있다.

 

단점

 

👆 인덱스 관리를 위한 저장공간이 필요하다.

 

인덱스는 데이터를 추가로 저장하는 구조이므로 데이터베이스의 디스크 공간을 차지한다.

인덱스가 크거나 많은 수의 인덱스가 있는 경우, 데이터베이스의 전체 디스크 공간 사용량이 증가할 수 있다.

큰 인덱스는 디스크 I/O 비용을 증가시킬 수도 있다.

 

👆 인덱스를 관리하기 위해 추가 작업이 필요하다.

 

데이터베이스에서 데이터가 추가, 수정, 삭제될 때 인덱스도 함께 업데이트되어야 한다.

특히 대량의 데이터를 한 번에 업데이트하는 경우, 인덱스 업데이트에 의한 성능 저하가 발생할 수 있습니다.

 

👆 인덱스의 유지 비용이 발생한다.

 

데이터 변경 작업이 빈번하게 발생하는 경우에는 인덱스 유지 비용이 상당히 커질 수 있다.

---

인덱스를 사용하면 좋은 경우

 

특정 컬럼을 검색조건으로 자주 사용하는 경우

ex) 주문 번호로 주문을 검색하는 경우, 주문 번호 컬럼에 인덱스를 생성하면 해당 주문을 빠르게 찾을 수 있다.

 

정렬 연산이 자주 발생하는 경우 (Order By)

정렬 기준으로 사용되는 컬럼에 인덱스를 생성하면 정렬 속도가 향상될 수 있다.

ex) 사용자의 이름으로 정렬하는 경우, 이름 컬럼에 인덱스를 생성하면 정렬 작업이 빠르게 수행될 수 있다.

 

---

인덱스의 자료구조

 

B+ Tree

 

DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조

B+Tree는 모든 노드에 데이터(Value)를 저장했던 BTree와 다른 특성을 가지고 있다.

 

 

- 리프노드(데이터노드)만 인덱스와 함께 데이터(Value)를 가지고 있고, 나머지 노드(인덱스노드)들은 데이터를 위한 인덱스(Key)만을 갖는다.

- 리프노드들은 LinkedList로 연결되어 있다.

- 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 된다.

- Root Node에서 경로를 확인한 후 그에 맞는 노드로 이동하여 최종적으로 원하는 데이터가 있는 Leaf Node에 도착한다.

 

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있다.

이러한 이유로 BTree의 리프노드들을 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화하였다. (물론 Best Case에 대해 리프노드까지 가지 않아도 탐색할 수 있는 BTree에 비해 무조건 리프노드까지 가야 한다는 단점도 있다.)

이러한 이유로 비록 B+Tree는 O(log2n) 의 시간복잡도를 갖지만 해시테이블보다 인덱싱에 더욱 적합한 자료구조가 되었다.

 

 

 

Reference

[자료구조] 그림으로 알아보는 B+Tree

[Database] 인덱스(index)란?

인덱스(INDEX)의 필요성