Hashing is a widely used technique for building indices in main memory. Hashing has also been used as a way of organizing records in a file.

Static hashing becomes inefficient when we try to add large number of records within a fixed number of buckets and thus we need Dynamic hashing where the hash index can be rebuilt with an increased number of buckets.

Extendible Hashing is a dynamic hashing method wherein array of pointers, and buckets are used to hash data.

Extendible hashing has some important advantages. Most significant is the fact that when looking for a record, we never need to search more than one data block. We also have to examine an entry of the bucket array, but if the bucket array is small enough to be kept in main memory, then there is no disk I/O needed to access the bucket array.

How Extendible hashing works !!!