❏ Index란
인덱스(Index)는 데이터베이스 테이블의 데이터를 빠르게 검색하기 위한 데이터 구조입니다.
예를 들어, 두꺼운 책에서 원하는 내용을 찾는다고 해봅시다. 책의 내용이 많을 수록 모든 페이지를 전부 확인해보는 것은 시간이 오래 걸리게 되겠죠? 그렇기에 중요한 단어가 어느 페이지에 위치해 있는지 나열한 목록, 색인을 추가해두는 편인데요.
인덱스도 이러한 책의 색인과 유사한 개념으로, 데이터와 데이터의 위치를 포함한 자료구조를 통해 빠르게 조회해올 수 있습니다. 👍
인덱스를 사용하지 않으면 특정 데이터를 찾기 위해서는 테이블 전체를 순차적으로 읽어야 하는 FULL TABLE SCAN이 발생합니다.
특정 컬럼에 대한 인덱스를 생성하면, 데이터와 데이터의 물리적 주소를 함께 저장합니다.
❏ Index의 자료 구조
저장하는 방식이나 알고리즘에 따라 다양한 인덱스가 존재하는데, 대표적으로 해시 테이블과 B 트리, B+ 트리 인덱스에 대해 다뤄보겠습니다.
❍ 해시 테이블(Hash Table)
해시 테이블은 (Key, Value)의 형태로 데이터를 저장하는 자료구조입니다.
특정 컬럼 값을 해시 함수를 통해 도출하여 해시 값을 구하고 이를 Key로, Value에는 탐색 목적이었던 데이터의 Value를 담아 해시 테이블을 구성합니다.
이러한 해시 테이블의 시간 복잡도는 $O(1)$로 매우 빠르게 검색을 할 수 있습니다.
학생 테이블에서 성적이 80점 이상인 학생 조회를 한다면, 해시 테이블 인덱스로 빠른 검색이 가능할까?
영호도 성적이 80점이고 영희도 성적이 80점이라면, 해시 테이블에서 Index가 중복되기 때문에, 충돌이 발생합니다.
즉, 해시 테이블 인덱스는 1 : 1 관계일 때, 하나의 데이터만을 탐색할 때, 사용하는 것이 좋습니다.
해시 테이블 인덱스는 등호(=) 연산에만 특화되어있기 때문에, 부등호(>, <) 연산이 자주 사용되는 데이터베이스 검색에서는 적합하지 않습니다.
❍ B Tree(Balanced Tree)
B Tree는 자식을 2개만 가지는 이진 트리(Binary Search Tree)를 확장하여 N개의 자식을 가질 수 있도록 한 자료구조 입니다.
이처럼 Key가 항상 정렬된 상태인 것이 특징이며, 각 노드에는 Key와 Value(데이터의 물리적 주소, 데이터 포인터), 자식 노드를 가리키는 포인터가 저장됩니다.
따라서, 루트 노드에서 하위 노드로 Key 값의 크기를 비교하며 찾고자 하는 데이터를 검색합니다. 시간 복잡도는 $O(logN)$입니다.
❍ B+ Tree
B-Tree에서 조금 더 변형된 구조를 B+Tree라 하는데, 가장 보편적으로 사용되는 인덱스입니다.
B Tree에서는 모든 노드에 Value(데이터 포인터)를 저장했었던 것과 달리,
B+ Tree에서는 단말 노드에서만, Key와 함께 Value(데이터 포인터)를 가지는 특성이 있습니다. 다른 노드에는 Key와 포인터만 가지고 Value(데이터 포인터)는 포함하지 않습니다.
단말 노드가 아닌 노드로 구성된 인덱스 세트(Index Set)와 단말 노드로만 구성된 순차 세트(Sequence Set)로 구분됩니다.
- 인덱스 세트(Index Set) : 단말 노드에 있는 Key를 찾아갈 수 있도록 경로만 제공
- 순차 세트(Sequence Set) : 해당 데이터의 주소를 가리킨다.
단말 노드가 LinkedList로 연결되어 있기에, 부등호 연산에 적합합니다.
| B Tree | B+ Tree |
| 모든 노드가 Key와 Value, 포인터를 포함한다. | 단말 노드에만 Value를 포함한다. |
| 중간에 데이터를 빨리 찾으면, 바로 Value를 얻을 수 있다. | 무조건 단말 노드까지 도달해야 Value를 얻을 수 있다. 고정적으로 O(logN)의 시간 복잡도를 가진다. |
| 부등호 연산이 B+ Tree보다 조금 오래 걸린다 | 부등호 연산에 유리하다 |
❏ 인덱스의 장단점
❍ 장점
- 검색 속도 향상
- 시스템의 부하를 줄일 수 있다
❍ 단점
- 인덱스를 잘못 사용하면 오히려 저장공간 낭비, 성능 저하
따라서, 생성/수정/삭제가 자주 발생하지 않고 자주 검색되는 컬럼에 인덱스를 생성하면 좋습니다.