8장. 직접화일 - 해시테이블, 확장성 해싱 VS 선형 해싱

왜 선형 해싱과 확장성 해싱이 modular 보다 나은가?

• modular는 overflow로 인한 확장이 발생했을 때, 전체 데이터를 다 재배치해주어야 한다.
• 반면 선형 해싱과 확장성 해싱은 overflow가 발생하는 버킷만 split하므로 데이터 재배치를 최대한 줄일 수 있다.
• 즉 선형 해싱과 확장성 해싱을 사용해도 데이터의 이동을 완전히 피할 수는 없지만 modular 보다는 낫다.

선형 해싱 (Linear hashing)

• 선형 해싱은 next에 대한 정보가 필요 (next 이전이면 3bit 접근, 이후이면 2bit 접근)
• 별도로 유지하거나, 유지 안해도 bucket 개수로 evaluation 가능할 듯

확장성 해싱 (Extendiable hashing)

확장성 해싱은 global 디렉터리 구조(bucket address table)를 유지해야 한다

선형 해싱 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를 증설해야 할 수도 있다. (오버플로우 체인으로 증설된 DB(1)도 나중에 쓰기 때문에 미리 증설한다고 봐도 되긴 하지만…)

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