엄범


선형 해싱 vs 확장성 해싱

확장성 해싱은 global 디렉터리 구조(bucket address table)를 유지해야 한다는 단점이 있지만, 무조건 한 번의 쿼리로 데이터를 읽어올 수 있다.


선형 해싱은 global 디렉터리 구조를 유지하지 않는다는 장점이 있지만, 다음과 같은 단점이 있다.

* overflow chain = synonym chain = 동거자 체인

  • 어디서 오버플로우가 발생하든, Next가 가리키는 앞쪽 버킷부터 split한다.
    - 선형 해싱은 어디까지 3비트로 읽어야 할지를 앞에서 부터 Next 이전까지는 3비트로, Next 부터는 2비트로 읽는 방식을 사용한다.
  • 어디서 overflow가 발생하든 앞에서 부터 순차적으로 split해 나간다. 따라서 맨 마지막 버킷에서 계속 overflow가 발생하는 경우 그 앞의 저장공간이 널널한 버킷들이 split되기 때문에 저장 공간 효율이 나쁘다.
    - 저장 공간 활용도는 평균 60% 정도로 알려져 있고, 확장 해싱 보다 낮은 편이다.
  • overflow chain 때문에 체인이 연결된 항목을 검색할 때는 쿼리를 두 번 이상 날려야 할 수 있다는 단점이 있다.
    + 그러나 실험 결과 평균 접근 횟수는 거의 1 정도로 알려져 있다. 따라서 overflow chain을 유지하는 것으로 인한 추가 접근은 큰 이슈는 아니다. 체인이 2개 이상 연결되는 경우가 그렇게 흔치 않다고 한다. 해시니까.


확장성 해싱은 한쪽의 레코드가 많이 늘어나는 경우도 커버가 가능하다. 예를 들면 어떤 항목은 4비트로 검색하고, 어떤 항목은 2비트로 검색하는 것이 가능하다.


그러나 선형 해싱은 무조건 3비트/2비트, 증가하면 4비트/3비트. 이런 식으로만 검색이 가능하다. 무조건 앞에서부터 split되면서 버킷이 늘어나기 때문이다. 

한쪽에 많이 몰리는 경우는 Overflow chain만 계속 늘어나면서 애꿎은 앞쪽 버킷만 계속 split 되다가 자신 차례가 왔을 때 그제서야 split된다.


따라서 디렉터리 구조를 관리해야 한다는 점만 빼면 종합적으로 봤을 때 일반적으로 확장성 해싱이 더 좋아 보인다.




대규모 서비스에서는 버킷 하나가 DB서버 하나에 대응된다고 볼 수 있는데, 선형 해싱 같은 경우 어느 DB에서 오버플로우가 발생하면, 그 DB에 오버플로우 체인으로 새로운 DB를 증설(1)하고, 앞쪽에 있는 DB를 split해서 나눠담을 새로운 DB를 또 증설(2) 해야해서 한 번의 오버플로우에 2개의 DB를 증설해야 할 수도 있다.

그래서 여러모로 단점이 좀 있다.