- 인덱스란 DB에서 데이터의 저장, 수정, 삭제에 대한 성능을 희생시켜 검색 성능을 높여주는 방법이다. 인덱스의 가장 큰 특징은 데이터들이 정렬이 되어있다는 점이다.
- 인덱스는 where 절에서 ‘자주 조회’하고 ‘수정 빈도’가 낮으며 ‘데이터 중복’이 적은 컬럼을 선택하는 것이 좋다. join 조건으로 자주 사용되는 컬럼도 인덱스로 사용하면 좋다.
- 하지만 인덱스를 사용하는 것이 무조건 좋은 것은 아니다. 인덱스는 INSERT, UPDATE, DELETE 같은 DML에 취약하다. 데이터가 추가되거나 값이 바뀐다면 인덱스 테이블 내에 있는 값들을 다시 정렬을 해야 한다. 또한 인덱스를 관리하기 위해서는 DB에 저장공간이 추가로 필요하기 때문에 인덱스 생성은 마지막 수단으로 강구해야 할 문제이다.
- 보통 DB의 인덱스는 B-Tree 자료구조를 이용하여 테이블의 요소를 빠르게 탐색하도록 설계되어 있다. 그렇다면 왜 많은 자료구조중에 B-Tree를 사용할까?
- 일반적인 Tree는 평균적으로 O(logN)의 시간 복잡도를 가진다. 하지만 Worst Case에서는 O(N)의 시간 복잡도를 가지게 된다. 이러한 경우를 방지하기 위해 밸런스 트리를 이용한다.
- 밸런스 트리(Balanced Tree)란 트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재 정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리이다. 항상 양쪽 자식의 밸런스를 유지하므로, 무조건 O(logN)의 시간 복잡도를 가지게 된다. 다만 재정렬되는 작업으로 인해 노드 삽입 및 삭제 시 일반적인 트리보다 성능이 떨어지게 된다. 그러므로 밸런스 트리는 삽입/삭제의 성능을 희생하고 탐색에 대한 성능을 높였다고 볼 수 있다. 밸런스 트리는 대표적으로 B-Tree, RedBlack-Tree 등이 있다.
- 하지만 탐색에 관해서 시간복잡도가 훨씬 우수한 자료구조는 많다. 예를 들어 탐색시간이 O(1)인 해시테이블이 있다.
하지만 해시테이블은 "단 하나의 데이터를 탐색하는 시간" 에만 O(1)이다. 여러개의 데이터를 조회하는 DB에는 맞지 않다.
예를 들어 Where 3 >= x and x >= -1 의 부등호가 들어간 쿼리에서는 해시테이블이 모든 값이 항상 정렬되어있지는 않으므로 O(1)을 보장할 수 없으며 매우 비 효율적이다.
- 그렇다면 배열이나 LinkedList는 어떨까? 배열은 오직 "탐색"에서만 B-Tree보다 빠르며 저장, 삭제는 훨씬 비효율적이다. LinkedList는 애초에 Index Number의 개념이 없기 때문에 배열보다도 더 적합하지 않다(정렬 알고리즘 조차 사용 힘듬).
- 마지막으로 RedBlack-Tree와 비교해보자 RedBlack-Tree는 각 노드는 하나의 값만 가진채로 좌, 우 자식 노드의 개수 밸런스를 맞춘다. 빨간색, 검은색 노드는 노드의 삽입/삭제 작업을 할 때 마다 규칙에 맞게 재정렬을 하기 위한 수단이므로 여기서는 신경쓰지말자.
- B-Tree는 아래처럼 하나의 노드에 여러 데이터가 저장 될 수 있다. 각 노드 내 데이터들은 항상 정렬된 상태이며, 데이터와 데이터 사이의 범위를 이용하여 자식노드를 가진다. 그러므로 자식 노드 개수는 항상 n + 1이다.
- 이처럼 RedBlack-Tree와 B-Tree 모두 항상 좌, 우 자식노드 개수의 밸런스를 유지하므로 최악의 경우에도 무조건 O(logN)의 시간복잡도를 가진다. 그렇다면 왜 RedBlack-Tree는 DB 인덱스로 선택받지 못할까?
- 답은 두 트리의 차이점에 있다. 바로 "하나의 노드가 가지는 데이터 개수"이다. 두 트리 모두 시간복잡도는 같지만 이는 알고리즘에 의한 이론적인 계산시간일 뿐이다. 트리에서 자식노드에 접근하기 위해서는 참조 포인터 접근을 해야한다.
B-Tree는 하나의 노드가 가지는 데이터 양이 RedBlack-Tree보다 많기 때문에 그만큼 자식 노드에 덜 접근하며, 이로인한 포인터 접근 수 차이로 인해 B-Tree가 RedBlack-Tree보다 탐색시간이 더 빠를 수 밖에 없다.
cf) B+Tree는 위의 B-Tree에서 리프노드들을 연결한 트리이다. 때문에 범위 검색이 쉽다. 요즘 DB는 대부분 B+Tree로 구현된다.
ref)
https://helloinyong.tistory.com/296
'CS' 카테고리의 다른 글
| Batch and Stream Processing [CS] (0) | 2022.12.22 |
|---|---|
| Data Governance [CS] (0) | 2022.12.19 |
| Process & Thread[CS] (0) | 2022.12.14 |
| Deadlock [CS] (0) | 2022.12.14 |
| ORM [CS] (0) | 2022.12.14 |