나중에 설명할 인덱스를 소개하기 전에, Hash와 균형 트리의 차이점을 짚고 넘어가는 게 나을 듯 싶습니다. 사실, 나중에 인덱스에 대해서 할 때, 이런 이야기는 상당히 많이 나오기 때문입니다. 범위 검색과 동등 검색. 맞나 잘 모르겠어요. 일치 검색인지. 하여튼, Tree 기반 인덱스와 Hash 기반 인덱스가 나오는데요.

 

 이에 대해서 지금은 잘 모르셔도 괜찮습니다. 대신에, 균형 Tree 기반으로 찾는 것과, Hash 기반으로 찾는 것에 대해서 다루고 넘어가도록 하겠습니다. 자료구조에 대해서 복습도 할 겸. 사실 왜 그렇게 하는지 디스크와 메모리에 대한 차이도 이해해야 겠지만, 여기서 길게 언급하면 글이 매우 길어질 듯 싶으니 언급하진 않겠습니다.

 

 


 먼저, Hash 기반 자료구조는 = 검색에 특화된 구조입니다. 대략적인 동작 방식은 아래와 같습니다.

 

 

 먼저 Key 값을 hash값으로 압축합니다. 예를 들어, h("abc")는 53이 나오면, "abc"를 53으로 압축합니다.

 

 

 이것이 [2]번 버킷에 대응된다고 해 봅시다. 그러면 [2]번 bucket에 "abc"를 넣습니다.

 

 

 다음에 "a"라는 Key가 들어왔습니다. 이것의 hash 값이 3이였다고 해 봅시다.

 

 

  그리고, 이것이 3번 버킷에 대응된다고 한다면, 3번 버킷 안에 "a"가 추가될 거에요.

 

 

 다음에, "t"와 "u"의 Hash 값이 각각 37, 52이고, 이것들이 또 3번 버킷에 대응된다고 해 봅시다.

 

 

 그러면, 이런 식으로 들어갈 겁니다. 그러면 이 구조는, 어떠한 특정 Key를 찾는 연산에 특화되어 있을 겁니다. 예를 들어 "a"를 찾는다고 가정을 한다면. 일단 "a"의 Hash 값이 3이였고, 이것이 3번 버킷에 대응되므로, 3번 bucket에 있을 겁니다.

 

 

 물론 최악의 경우에, 엄청나게 충돌이 많이 나오는 것은 피할 수 없겠지만, 재해싱을 하고 그러면, 평균적으로 find 함수의 복잡도는 O(1)이 됩니다. 기본적으로 균형 Tree 기반의 구조가 O(depth)만큼 들어간다는 것을 생각해보면 상당히 빠른 구조임을 알 수 있어요. find(key)는, 동등 연산입니다. 다시 말하면, 동등 연산은 Hash 기반 구조에서는 상당히 빠릅니다. 그런데, 기본적으로 이것은 정렬이 되어 있지 않습니다. 그 이야기인 즉슨, 범위 쿼리에는 적절하지 않다는 것입니다.

 

 저 구조에서 'a'보다 사전순으로 같거나 뒤에 있으면서, 't'보다 사전순으로 같게 있거나 앞에 있는 Key들을 모두 출력하라고 하면 어떨까요?

 

 

 

 최악의 경우, 전체를 탐색해야 합니다. 어떤 상황이 생길지 상상이 되실 겁니다. Full Scan. 버킷 각각에 Key 값이 sort 되어 있다고 해 봅시다. 삽입, 삭제가 자주 일어나는 상황인 경우, 버킷 각각은 균형 Tree로 작성이 되어야 겠군요. load factor를 0.8로 잡고, 대충 Key가 65536개 들어갔다고 해 봅시다. 버킷 수가 10만개고요. 이 중 정확히 256개의 Bucket에 256개의 Key가 들어가 있다고 해 봅시다.

 

 

 그러면 Key값이 s보다 크거나 같고, e보다 작거나 같은 Key를 모두 출력해 주라는, (흔히 Between 이라고 하는) 쿼리가 들어왔을 때, 각 버킷마다 s보다 크거나 같은 최초의 위치를 찾기 위해서, 꽤 많은 시간이 걸릴 겁니다. 버킷에 달려있는 것이 균형 2진 트리라고 한다면, O(log(원소 크기))에 비례할 건데, 일단 밑이 2인 log(256) = 8입니다. 8에 256을 곱하면? 2048인가요?

 

 이는 그냥 65536개의 원소를 균형 트리 하나에 넣었을 때의 복잡도보다 훨씬 나쁜 수치입니다. 물론, 전체적인 복잡도는 탐색하는 시간도 만만치 않긴 하겠지만, 제가 언급한 차이는 그냥 무시할 만한 수준일까요? 범위가 상당히 작은 range 쿼리를 생각해 보시면 그렇지 않을 수도 있다는 것을 직감하실 수 있을 겁니다.

 

 


 그러면 균형 트리는 어떤가요? 정렬 되어 있는 트리에서의, 범위 range Query에서는, 다음 원소의 위치를 찾는 next 연산과, lower_bound, upper_bound 연산이 중요한데요.

 

 

 

 일단 s보다 크거나 같은 위치를 찾는 데 소요되는 시간은 log(원소 갯수)에 비례합니다. 물론, 균형 2진 트리라면 밑이 2일 거에요. 다음에, 계속 next 원소를 탐색을 할 건데요. 이 때 복잡도는 얼마나 될까요? 그런데.. 생각보다 많이 걸리지는 않습니다.

 

 전체 탐색을 한다고 가정하면, 한 노드를 많아봐야 3번 방문하므로 O(3n)이 될 겁니다. 그리고, 다음 원소를 탐색하는데, 최악의 경우에, depth만큼 올라가고, 다시 depth만큼 내려갈 겁니다.

 

 

 그러니, next 연산을 할 때, 최악의 경우 O(log(원소 갯수))입니다만, 시작 위치부터 끝 위치까지 next 연산을 계속 한다면, 노드들을 많아봐야 3번 재방문 하므로 O(3n)이 됩니다. Key 값이 '남', '여'만 있는 경우에는 어떨까요? 사실, 쿼리마다 O(log(원소 갯수))도 아깝지만, O(3n) 또한 무시 못합니다. 물론 남자 50%, 여자 50%가 있다면 조금 낫긴 하겠지만. 당연하게도 B 트리는, 이것보다 depth가 극단적으로 작긴 합니다. 하지만, 탐색할 때 걸리는 오버헤드는 무시 못합니다.

 

 이것 때문에, 데이터의 중복도가 높은 성별과 같은 컬럼은, Hash나 Tree 기반으로 처리해도 별로 효용이 없다는 이야기가 나오는 이유입니다. 사실 더 할 이야기가 많지만, 일단은 이 정도만 이해하셔도 별 문제는 없으리라 생각이 듭니다.