[MySQL] 인덱스 자료구조

인덱스의 핵심은 탐색 범위를 최소화 하는 것이다. 그렇다면 탐색이 빠른 자료구조들은 어떤 것이 있을까?

Hash Map, List, Binary Search Tree 등이 있는데, 하나씩 간단하게 살펴보도록 하자.

✅ HashMap

- 단건 검색 속도 O(1)

- 범위 탐색 O(N)

- 전방 일치 탐색 불가 Ex) like 'AB%'

 

해시맵은 키와 밸류가 있다. 그렇기 때문에 단건 검색 속도는 빠른편이며 상수 시간이 걸리게 된다. 범위 탐색에는 O(N) 시간이 걸리게 된다.

✅ List

- 정렬되지 않은 리스트의 탐색은 O(N)

- 정렬된 리스트의 탐색은 O(logN)

- 정렬되지 않은 리스트의 정렬 시간 복잡도는 O(N) ~O(N * logN)

- 삽입 / 삭제 비용이 매우 높음

 

정렬되지 않은 리스트는 탐색에 O(N) 시간이 걸리지만 정렬된 리스트의 탐색은 O(logN) 시간이 걸리게 된다. 리스트는 삽입 및 삭제 비용이 매우 높은데, 예를 들어 가운데 데이터를 삭제한다고 했을 때 처음부터 해당 값까지 탐색을 해야 한다.

✅ Tree

- 트리 높이에 따라 시간 복잡도가 결정

- 트리 높이를 최소화하는 것이 중요

- 한쪽으로 노드가 치우치지 않도록 균형을 잡아주는 트리 사용

-  ex) Red-Black Tree, B+Tree

 

Binary Research를 이용한다는 가정하에 트리 높이에 따라 시간 복잡도가 결정된다. 그렇기 때문에 트리 높이가 검색 시간에 있어 중요한 요소가 된다. 

✅ B+ Tree

- 삽입 / 삭제시 항상 균형을 이룸

- 하나의 노드가 여러 개의 자식 노드를 가질 수 있음

- 리프노드에만 데이터 존재(연속적인 데이터 접근 시 유리)

 

대부분의 RDBMS는 B+Tree를 많이 사용하게 된다. B+ Tree의 중요한 특징으로는 하나의 노드가 여러 개의 자식 노드를 가질 수 있다는 것이다. 또한 리프노드에만 데이터가 존재하기 때문에 연속적인 데이터 접근 시 유리하고, 각 노드에 접근할 때마다 데이터를 직접 보는것이 아니라서 데이터 레퍼런스 횟수도 훨씬 적다.