DataBase Index에서 기본적으로 HashTable이 아닌 B-Tree를 쓰는 이유

  의문의 시작  

해시 테이블은 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간복잡도를 가지는 좋은 성능의 자료구조인데 DateBase에서 Index로 사용안하는지 갑자기 의문이 생겼다. 지금 생각해보면 조금만 고민하면 답을 찾을 수 있는데 왜 안보였는지...

서치를 해보니 나와 같은 의문점을 가진 사람들이 꽤 있어서 자료가 찾기 편했다. 바로 알아보자!

 

 

  자료구조 비교

 

  HashTable 

HashTable이란 Key와 Value로 데이터를 저장하는 자료구조 중 하나로써, 데이터의 삽입, 삭제, 탐색에 평균적으로 O(1)이라는 빠른 성능의 시간복잡도를 자랑하는 자료구조이다.

 

HashTable의 프로세스를 알아보면,

1. 검색하고자 하는 키값을 입력받아서
2. 해시함수를 통해 반환받은 HashCode를
3. 배열의 Index로 환산하여
4. Value에 접근하는 자료구조이다.

Function(key) -> HashCode -> Index -> Value

 

여기서 키값은 문자열, 숫자, 파일데이터 등이 될 수 가 있으며,

해시함수는 입력받은 키값의 사이즈에 상관없이 특정한 규칙을 통해 HashCode를 반환해주게 된다.

 

  HashTable이 빠른이유

해시함수를 이용해서 만든 HashCode는 정수이다.

배열공간을 고정된 크기만큼 미리 만들어놓고, HashCode를 배열의 개수로 나머지 연산(%)을 하여 배열에 나눠 담는다.

따라서 해시코드 자체가 배열방의 Index로 잡히기 때문에 검색을 할 필요없고 바로 접근을 할 수 있어서O(1)의 빠른 속도를 자랑할 수 있는 것이다.

 

  Hash충돌

HashTable에서 발생할 수 있는 문제점이 있다. 키값으로 사용될 수 있는 개수가 무한대에 육박하는데, HashCode는 그 가지수가 정수개밖에 제공못하기 때문에 어떤 키는 중복되는  HashCode를 가질 수 밖에 없는 상황이 발생한다.

또한 HashCode가 다르더라도 인덱스로 환산하였을때 같은 인덱스로 배정받았든 하나의 배열에 겹쳐서 저장되는 경우를 Hash충돌이라 한다.

보통 LinkedList를 이용하여 같은 방으로 배정받는 경우 뒤에 다음 데이터를 연결하여서 붙이는 방식으로 해결하곤 한다.

 

 

  B-Tree

💡 다음은 DataBase에서 Index로 사용하는 자료구조인 B-Tree에 대해 알아보자.

 

B-Tree는 Tree의 노드가 한 방향으로 쏠리지 않게 균형 있게 높이를 유지하는 Balanced Tree 중 하나이다.

모든 leaf node가 같은 level을 유지하도록 밸런스를 맞춰주며, 항상 양쪽 자식의 밸런스를 유지하므로 평균적으로 O(log N)이라는 시간복잡도를 가진다.

 

B-Tree의 특징으로는

• 각 노드는 여러 데이터를 저장할 수 있다
• 노드 내 데이터는 항상 key기준으로 오름차순으로 정렬된 상태이다.
• 또한 최상위 노드를 루트노드, 중간을 브랜치 노드 마지막을 리프노드라고 한다.
• 모든 leaf노드는 같은 level을 유지한다.
• 데이터와 데이터의 범위를 이용하여 자식 노드를 가지며, 자식 노드 개수는 (N+1) 이다.

 

아래 블로그에서 정말 자세하게 B-Tree에 대한 설명을 참고할 수 있다.

https://rebro.kr/169 

[DB] 10. B-Tree (B-트리)

 

  RedBlack-Tree

Red Black Tree는 B-Tree와 같이 Balaced Tree 중 하나이다. 

모든 노드는 검은색 혹은 빨간색이며, 루트 노드는 검은색으로 시작하여 각 노드는 하나의 데이터만 가진 상태로 좌, 우 자식의 노드 개수를 맞추며 빨간색과 검은색은 노드를 재정렬하는데 사용된다.

 

아래 블로그에서 Red Black Tree에 대한 자세한 설명을 참고할 수 있다.

https://code-lab1.tistory.com/62

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

 

 

  B-Tree VS RedBlack-Tree

💡 왜 다수의 DB는 일반적으로 RedBlack-Tree가 아닌 B-Tree를 인덱스로 채택했을까?

B-Tree의 각 노드는 배열로 실제 메모리에 차례대로 정렬되어 저장되어 있다.

따라서 같은 노드의 데이터를 접근할 때 실제 메모리에서 바로 다음 인덱스로 접근할 수 있다.

하지만 RedBlack-Tree는 각 노드는 하나의 데이터만 가졌기 때문에 모든 데이터를 접근할 때 무조건 참조 포인터를 통해 접근해야한다. 

즉, RedBlack-Tree는 접근하려는 주소를 연산을 통해 알아 내어 내부로 접근하는 참조 포인터가 B-Tree보다 더 많이 소모가 되어 데이터가 많아질수록 소모되는 시간의 차이가 점점 커지게 된다.

따라서 DataBase와 같은 많은 데이터에 접근이 필요할 경우 B-Tree가 RedBlack-Tree보다 더 적합하게 된다는 것을 알 수 있다.

이렇게 따지면 RedBlack-Tree가 무조건 비효율적으로 보이나, 적은 데이터에서 많은 수정이 일어날 경우 B-Tree에 비해 RedBlack-Tree가 더 적합할 수 있다.

 

참고

algorithm - B-tree faster than AVL or RedBlack-Tree? - Stack Overflow

 

 

  HashTable보다 B-Tree가 적합한 이유

이제 의문의 종착지에 도달했다.

본인이 HashTable을 생각했을 때 간과한 사실이 있다. DataBase는 범위를 통해 접근하는 경우가 많다는 점이다.

즉, DataBase에서는 데이터 탐색시에 =, >, < 등 다양한 범위를 지정하여 탐색할 수 있다.

HashTable은 = 부등호를 이용하여 하나의 값에 접근할 때는 O(1)의 속도로 빠르게 접근할 수 있다.

하지만 >, < 등 범위로 지정하여 접근할 경우, HashTable의 경우 해시함수를 통해 Index화 시켜놨기 때문에 순서가 없어 일일이 하나씩 접근해야 한다. 즉, 범위로 접근하거나 Orderby를 사용할 경우 O(N)이상 이라는 시간복잡도를 가져 인덱스로써의 가치가 없어지게 된다.

 

반면에 B-Tree를 사용할 경우 평균적으로 O(logN)이라는 빠른 성능으로 탐색, 삽입, 수정, 삭제할 수 있으며, 정렬이 되어 있기 때문에 >,<과 같은 범위탐색에 효율적으로 접근할 수 있다. 또한 노드마다 배열로 구현되어 있기 때문에 참조포인터를 RB-Tree에 비해 조금 사용하여 방대한 데이터 접근에 더 적합하다.

따라서 DataBase의 여러 고려사항을 따졌을 때 가장 적합한 자료구조로 채택이 된다.

 

  DataBase에서 HashTable의 사용

DataBase에서 HashTable이 Index로만 사용이 안될뿐이지 Join할 경우 HashTable 자료구조를 사용하게 된다.

컬럼의 Index가 없고 = 연산자로 Join을 하게 될 경우, 적은 데이터의 테이블을 메모리에 HashTable로 올려놓고 HashJoin을 사용하는데 이때 Index없는 NL보다 평균적으로 빠르게 조회할 수 있다.