DB 인덱스에서는 왜 HashTable을 사용하지 않을까?

데이터베이스의 인덱스는 보통 밸런스 트리(B-Tree)를 사용한다.

# 밸런스 트리(Balanced Tree)란?

- 트리의 노드가 한 방향으로 쏠리지 않도록, 노드 삽입 및 삭제 시 특정 규칙에 맞게 재 정렬되어 왼쪽과 오른쪽 자식 양쪽 수의 밸런스를 유지하는 트리이다. 항상 양쪽 자식의 밸런스를 유지하므로, 트리의 평균시간복잡도 O(logN)을 항상 보장한다.

오른쪽과 같은 상황이 벌어지지 않게, 밸런스 트리를 이용한다.

- 다만 재정렬되는 작업으로 인해 노드 삽입 및 삭제 시 일반적인 트리보다 성능이 떨어지게 된다. 그러므로 밸런스 트리는 삽입/삭제의 성능을 희생하고 탐색에 대한 성능을 높였다고 볼 수 있다. 밸런스 트리는 대표적으로 RedBlack-Tree, B-Tree가 있다

 

 

---

# 왜 탐색이 가장 빠른 해시테이블을 인덱스에 사용하지 않나요?

해시테이블이 탐색에 있어 상수시간 O(1)을 보장하는 건 맞다. 하지만 여기에는 함정이 있는데, '단 하나의 데이터를 탐색할 때' 해당되는 이야기이다. 데이버테이스에서 검색은 등호(=) 뿐 아니라 부등호(<, >)도 사용 할 수 있다.

즉, 모든 값이 정렬되어 있지 않은 해시테이블은 특정 기준보다 크거나 작은 값을 찾을 수 없다. 즉 DB의 인덱스로는 사용할 수 없는 자료구조인 것이다.

해시테이블을 이용한 인덱스 예제

 

---

# 왜 RedBlack-Tree가 아닌 B-Tree를 사용하는거죠?

- RedBlack-Tree 와 B-Tree는 각각 다른 특징을 가진다. 먼저 RedBlack-Tree를 살펴보자

@ RedBlack-Tree

레드-블랙 트리는 이진 트리의 특수한 형태로 삽입, 삭제, 검색에서 항상 일정한 실행시간을 보장하는 밸런스 트리의 일종이다. 레드-블랙 트리는 2가지 노드(레드,블랙)를 다음과 같은 규칙으로 이진트리를 구성한다

1. 루트와 모든 마지막 노드(null leaf, NIL)는 블랙이다.
2. 레드 노드의 양쪽 자식은 언제나 블랙이다. (= 레드는 연달아 나올수 없고, 항상 블랙이 부모이다)
3. 어떤 노드에서 시작하여 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 같은 개수의 블랙노드를 가지고 있다. (* 리프 노드 자신은 제외)
=> 이러한 규칙을 이용하여 [루트~가장 먼 곳]의 거리가 [루트~ 가장 가까운 곳]의 두 배보다 작게 이진트리를 구성한다. 즉 시간복잡도가 트리의 깊이에 따라 결정되므로 트리의 삽입, 삭제, 검색 성능을 일정하게 유지시킨다.

 

---

@ B-Tree

B-Tree는 노드하나에 여러 데이터를 저장할 수 있다. 각 노드 내부는 항상 정렬된 상태이며 현재 노드안에 있는 데이터의 범위를 이용하여 자식노드를 만든다. 즉 각 노드는 최대 (n+1)개의 자식노드를 가지게 된다. 보통 B-Tree는 O(log N)의 참조 시간을 갖기 위해 한 노드의 데이터 개수를 3~5개정도로 제한하여 사용한다.

아래 그림을 통해 알아보자. 루트 노드안에 3개의 값이 있다. 각 값의 범위 (0~100, 100~155, 155~266, 266~)를 이용하여 최대 4개 (3+1)의 자식노드를 생성한다. 이렇게 구성하면 트리를 탐색 할 때 마치 배열처럼 순서대로 접근할수도 있고 특정 값을 탐색할 때 밸런스 트리처럼 O(log N)의 시간복잡도를 가지게 된다.

 

---

@ RedBalck-Tree 와 B-Tree의 큰 차이

사실 논리적인 시간복잡도로 생각하면 둘 다 O(log N)의 성능을 낸다.
하지만 하드웨어적인 측면에서 봤을 때 성능은 크게 차이난다. 그 이유는 바로 참조 포인터의 사용.

참조 포인터를 사용하는 Linked-List와 인덱스를 사용하는 Array의 차이를 떠올려보자.
배열 같이 상수 인덱스로 접근하는 경우, 정말로 정렬된 실제 메모리에서 단순 덧셈으로 한번에 접근하는거라 탐색 속도가 굉장히 빠르다. 하지만 참조 포인터의 경우 계속해서 해당 메모리 주소를 타고 들어가서 원하는 값을 가져오기에 탐색 속도가 느리다.

RedBlack-Tree의 경우 각각의 노드를 참조 포인터만 사용해서 접근하지만, B-Tree의 경우 같은 노드의 값은 배열처럼 상수 인덱스 덧셈으로 빠르게 데이터에 접근 할 수 있다. 즉 특정 값을 탐색하거나 부등호(<, >) 등의 연산에서 순서대로 값을 가져올 때 훨씬 좋은 효율을 낸다.

 

---

@ 그럼 참조 포인터를 사용 안하는 Array 쓰면 더 좋은거 아니에요?

B-Tree가 아니라 아예 배열을 사용해서 전부 상수 인덱스로 접근한다면 값을 가져올 때 훨씬 빠르게 가져올 수 있는건 맞다. 심지어 정렬된 배열을 사용하면 부등호 연산도 B-Tree보다 더 빠르게 처리 할 수있을 것이다.

 

하지만 배열은 '접근'만 좋을 뿐이지 데이터의 저장, 삭제가 일어나는 순간 끔찍한 성능을 보여주게 된다. 그러니 모든 면으로 적절한 밸런스를 가지고 있는 B-Tree가 데이터베이스에는 가장 적합한 것이다.실제로 B-Tree 를 설명할 때 '데이터베이스나 파일 시스템에 널리 활용되는 밸런스 잡힌 트리구조'라고 하기도 한다.

---

# B-Tree 요약

1. 노드안의 배열은 항상 정렬된 상태로 있어 크고 작은 부등호 연산에 문제가 없다.
2. 배열의 인덱스 접근을 적절하게 섞어서 사용하기에 방대한 데이터 탐색에도 빠른 메모리 접근을 지원한다.
3. 밸런스 트리라서 저장, 수정, 삭제에도 O(logN)의 복잡도를 항상 보장한다.

 

그래서 DB 인덱스는 배열과 밸런스트리의 장점을 적절히 섞어서 사용하는 B-Tree가 제일 적합하다.