일단 트리에 대해서 얘기해 보자.
트리 노드의 요소가 위처럼 한쪽 방향으로만 쏠려있다면 최악의 탐색 시간은 O(N)을 가지게 된다.
이러한 경우를 방지하기 위해 우리는 밸런스 트리(Balanced Tree)를 이용할 수 있다.
밸런스 트리는 대표적으로 RedBlack-Tree, B-Tree가 있다.
밸런스 트리는 최악의 경우에도 O(logN)이므로, 탐색시간에 매우 효율적인 자료구조이다. 그래서 데이터베이스의 인덱스는 밸런스 트리, 그중 B-Tree를 선택했다.
그냥 hash Table을 사용하면 되는 것 아닌가?
사실 그렇다. 모든 자료구조와 그 어떤 알고리즘을 비교해도 탐색 시간이 가장 빠른 것은 바로 해시 테이블이다. 해시 테이블은 해시 함수를 통해 나온 해시 값을 이용하여 저장된 메모리 공간에 한 번에 접근을 하기 때문에 O(1)이라는 시간 복잡도를 가진다. (물론 해시 충돌 등으로 최악의 경우에 O(N)이 될 수 있지만, 평균적으로는 O(1)으로 볼 수 있다)
그러나 이는 온전히 '단 하나의 데이터를 탐색하는 시간' 에만 O(1)이다. 예를 들어 1,2,3,4,5가 저장되어 있는 해시 테이블에서 3이라는 데이터를 찾을 때에만 O(1)이라는 것이다.
우리는 DB에서 등호(=) 뿐 아니라 부등호(<, >)도 사용할 수 있다는 것을.
모든 값이 정렬되어있지 않으므로, 해시 테이블에서는 특정 기준보다 크거나 작은 값을 찾을 수 없다. 굳이 찾으려면 찾을 수는 있지만 O(1)의 시간 복잡도를 보장할 수 없고 매우 비효율적이다.
그렇기에 기준 값보다 크거나 작은 요소들을 항상 탐색할 수 있어야 하는 DB 인덱스 용도로 해시 테이블은 어울리지 않는 자료구조인 것이다.
RedBlack-Tree와 B-Tree의 차이는 무엇일까?
이 둘의 가장 큰 차이는 '하나의 노드가 가지는 데이터 개수'이다. RedBlack-Tree는 무조건 하나의 노드에 하나의 데이터 요소만을, B-Tree는 하나의 노드에 여러 개의 데이터 요소를 저장한다.
그리고 B-tree는 마치 배열처럼 정렬이 되어 있다.
맞다! 이것은 배열이다. 실제 메모리 상에 차례대로 저장이 되어있는 것이다. 같은 노드 공간의 데이터들끼리 굳이 자식 노드처럼 참조 포인터 값으로 접근할 필요가 없다.
이는 즉, 같은 노드 상 데이터를 탐색할 때는 포인터 접근을 하는 것이 아니라 실제 메모리 디스크에서 바로 다음 인덱스의 접근을 하는 것이다.
배열은 데이터들이 메모리 공간에 차례대로 저장이 되어 있으므로 접근할 주소를 바로 알 수 있다.
B-Tree도 자식 노드를 접근할 땐 참조 포인터로 접근을 하지만, 하나의 노드가 가지는 데이터 개수가 많아질수록 포인터 개수는 확연히 줄어들고, 트리 내에서 다루는 데이터가 많아질수록 이러한 차이는 더욱 커질 것이다.
비록 같은 O(logN)이지만, 포인터 접근 수의 차이로 인해 B-Tree가 RedBlack-Tree보다 탐색 시간이 더 빠를 수밖에 없다.
솔직히 이 둘의 성능 차이는 웬만한 데이터 개수로는 차이가 없겠지만, 글로벌하게 데이터를 다루는 수준이라면 이러한 차이가 분명 큰 영향이 있을 것이다.
참고 : https://helloinyong.tistory.com/296
