Extendible Hash

Main concepts:

(1).Directory page: The directory page covers the direction information of the Buckets, including : Bucket_page_id, Bucket_size, Split_Bucket_index, Bucket_Depth(global & local).
(2).Bucket pages: The Bucket_pages store the data of key-value pairs at each Bucket page, and use the linear array of Readable_ and Occupied to mark the available position.
(3) Tomb Stones: positions that are Occupied but not Readable
(4)Image Bucket:The bucket that generates from the Split Bucket. It has the same local depth as the Split Bucket. And for the local_mask, their local masks are the same except the Local_Depth's bit. For example, the bucket with bucket_index 0010, and its local depth is 3, then the split_bucket_index is 0110. When a bucket is full, we should increase its local depth and rehash its key_values to itself and its Image_bucket.

Hashing Model

1. Details of Bucket pages

2. Details of the Extension Process