Previous chapter
Static Hashing
Bucket : 레코드를 저장하는 저장단위 (4KB), 복수의 버킷이 존재함.
Hash function을 이용해 Bucket에 할당하도록 사용된다.
같은 버킷에 동떨어진 키가 매핑이 될 수 있다.
•
해시 인덱스에서는 엔트리와 포인터를 저장하는 편
•
파일을 쓴다고 하면 레코드를 저장한다고 생각하면 됨
버킷의 사이즈가 고정되어있는 녀석을 Static Hashing이라고 한다.
버킷은 순차적으로 할당되고, 절대 삭제되지 않는다.
Handling of Bucket Overflows
버킷의 용량을 초과하는 엔트리 개수에 대해
Skew는 다음과 같은 이유로 일어난다.
•
같은 키를 가지는 경우
•
그냥 해시 함수가 구-려서
버킷 오버플로우가 일어날 확률은 줄일 수 있으나, 버킷 오버플로우 자체를 없앨 수는 없다.
이를 위해 오버플로우 버킷을 사용했다.
Overflow Chaining
Closed Hashing : 기존 버킷이 꽉 찼을 경우 새로운 버킷을 생성한 후, 링크드리스트 방식으로 연결하는 방식
Open Hashing : 기존 버킷이 꽉 찼을 경우, 다음 순서의 버킷에서 데이터를 찾아야한다.
Examples of Hash File organization
Deficiencies of Static Hashing
Dynamic Hashing
Static Hashing에서 Rehashing은 상대적으로 값이 비싸고, Rehashing이 진행되는 동안에는 연산이 blocked되므로, 연산이 지연되는 현상이 발생한다.
따라서 Rehashing을 더 완화할 수 있는 방법을 찾아야 하는데,
•
해싱함수를 완전히 바꾸지 않으며 리해싱을 할 수 있거나(Extendible Hashing)
•
????를 만족할 수 있어야 함.
Extendible Hashing
해시의 버켓이 가득 찼을 때 오버플로우 버켓을 사용하는 것은 상당한 문제가 있다.
•
버켓의 사이즈가 작을 경우, 오버플로우가 지나치게 발생해 시간 복잡도가 증가한다.
•
버켓의 사이즈가 클 경우, 버켓 안에 남는 공간이 생겨 메모리 낭비가 심해진다.
이를 위해서 우리는 해싱을 다시 진행하며, Extendible Hashing은 그 Rehashing 중 하나이다.
초과될 때마다 비트 스트링의 길이를 1씩 증가시켜 확장성을 만족시키는 해싱 구조이다.
•
해시 키의 일부만 사용하며 postfix나 prefix가 될 수 있다.
◦
postfix(LSB)는 i 비트이며, 0~32라고 가정하자.
◦
Directory 사이즈는 2^i라고 한다.
◦
처음 i의 사이즈는 0이다.
•
여러개의 엔트리가 하나의 버킷을 가리키기도 한다.
•
다만 특정 조건을 만족하면 하나의 버킷이 세포분열을 한다!!!!
General Extendible Hashing Structure
Directory는 버킷을 가리키는 하나의 Indirection Layer라고 생각하면 된다.
이때 Hash prefix는
How it works
Key K에 대해 버킷을 찾기 위해 gloabl Depth를 사용한다.
global depth = h(K) 의 LSBs
Global Depth와 Local Depth가 같은 레벨의 버켓은 Unique하지만, L < G인 버켓은 그렇지 않다는 것을 확인할 수 있다.
•
01과 11의 경우, Global Depth = 2, Local Depth = 1이므로, 두개가 하나의 버킷을 공유하게 된다.
이 상태에서 L=1인 버켓에서 Collision이 일어났다고 가정해보자.
L < G이므로, L을 1 증가시킨 후, 각각의
이제 모든 L=2인 상태에서 Collision이 일어났을 때를 살펴보자.
L = G이므로, Split을 해도, Directory에서 가리킬 수 있는 Entry가 없다!!
이를 해결하기 위해, Directory의 Entry를 늘려준 후, 버켓의 스플릿을 진행해야한다.
이를 디렉토리 더블링이라고 한다.
Extendible Hashing vs. Other Schemes
•
B트리처럼 스플릿을 진행하므로, 오버헤드가 적게 발생한다.
•
그러나 Indirection directory가 있으므로, 추가적인 딜레이가 발생한다.
Linear Hashing
버킷의 오버플로우가 발생하게 되면, 데이터가
Algorithm
각 ‘라운드’별로 알고리즘을 반복적으로 수행한다.
현재 라운드 넘버는 Level이다.
Comparison of Ordered Indexing and Hashing
•
주기적인 재구성이 필요하며, 그에 따른 비용도 발생함.
•
insertion과 deletion에
Multiple-Key Access and Bitmap Index
Next chapter