Does doubling the directory double the data?

No. Existing buckets can be referenced by multiple entries; the overflowing bucket is the one being divided.

Must every split increase global depth?

No. A bucket whose local depth is smaller than global depth can split using the existing directory size.

Is it an AI learning algorithm?

No. It is an indexing technique that can support the storage systems used by AI applications.

AI Glossary / Graphs and symbolic AI / Intermediate

Extendible hashing

Definition

Extendible hashing is a dynamic indexing method that uses selected bits of a key's hash value to locate a storage bucket through a directory. When a bucket needs more space, it can be split, and the directory expands when additional hash bits are needed.

What it means

A conventional fixed-size hash table can become crowded as its data grows. Extendible hashing separates the directory of bucket addresses from the buckets holding records. Multiple directory entries may point to the same bucket, so increasing the directory does not mean duplicating every stored record.

The technique is useful for key lookups in changing collections. A hash value helps locate candidates, but the original key must still be compared to establish a match. Extendible hashing is not a method for finding semantically similar documents, and its bucket arrangement does not preserve the natural ordering needed for efficient range queries.

How it works

The directory has a global depth g, meaning that g selected hash bits identify one of 2 raised to g directory entries. A bucket has a local depth l, indicating how many bits distinguish its contents. Usually l is no greater than g.

If an insertion overflows a bucket, split that bucket using one additional bit. When its local depth is below the global depth, existing directory entries can be redirected without doubling the directory. If the depths are equal, the directory must first grow so that the additional bit can distinguish the split buckets.

Only the affected bucket's records need redistribution during that split, although directory growth updates the address structure. Deletion can permit compatible buckets to merge and the directory to shrink under suitable rules. Implementations differ in their split, merge, storage and concurrency policies, so the basic scheme should not be mistaken for a complete production specification.

Three practical examples

1. A record store indexes equipment identifiers. As new identifiers arrive, crowded buckets split locally while exact lookups continue through the directory.

2. An AI data pipeline needs to retrieve metadata by a document's stable identifier. A hash index can support that lookup, while a separate vector or text index handles similarity-based discovery.

3. A database teaching system uses extendible hashing to illustrate growing indexes. Tests can inspect global depth, bucket depths and directory pointers after insertions rather than treating resizing as an invisible operation.

Think of it this way

Think of a reception desk with a routing list that directs visitors to rooms by a code. If one room becomes crowded, it is divided and the routing list becomes more specific for that group. Several list entries can still point to another unchanged room. The analogy captures selective subdivision, but real hashing needs exact bit rules, collision handling and consistent updates that a receptionist's judgment does not provide.

Worked example

Consider a table with bucket capacity two. Use the least-significant hash bits and let each integer's displayed binary representation be its illustrative hash. Global depth starts at one. The even bucket, local depth one, holds keys 2 and 4; the odd bucket, also depth one, holds key 1.

Insert key 6. Its final bit is zero, so the even bucket would overflow. Since that bucket's local depth equals the global depth, double the directory from two entries to four and increase global depth to two.

Split the even bucket by its last two bits. Key 4 ends in 00, while keys 2 and 6 end in 10. Thus directory entry 00 points to a bucket containing 4, and 10 points to a bucket containing 2 and 6. Both new buckets have local depth two. Entries 01 and 11 still point to the same odd bucket containing 1, whose local depth remains one. There are four directory entries but only three buckets. This is a hand trace, not a recommendation to use identity hashing in production.

Illustrative case study

Fictional case study: Maple Records prototypes a growing identifier index. A developer expects every directory expansion to double record storage. By inspecting a small example, the team sees that unchanged buckets can have several directory references and need not be copied.

The next tests deliberately create uneven hash patterns and concurrent insertions. The team measures directory memory, split frequency and lookup correctness, and defines how interrupted updates recover. The case illustrates questions to examine before deployment; it reports no actual performance gain or successful production implementation.

Common misconceptions and mistakes

Global depth describes directory addressing, not the number of records in a bucket. Local depth is not necessarily equal for all buckets. A directory entry is a reference to a bucket, not automatically a separate bucket.

Hashing does not eliminate collisions. Different keys can share the same relevant bits, or even the same complete hash. Repeated subdivision cannot distinguish identical complete hashes, so a real implementation needs a policy for such cases and finite depth limits. Do not interpret a classical page-access result as a promise about all modern implementations, caches or concurrent workloads.

Business use

Evaluate extendible hashing when exact key access and dynamic growth are important. Check the hash distribution on representative keys, expected bucket occupancy, maximum directory size and deletion behavior. Include the cost of maintaining the index alongside retrieval time.

For storage, verify that bucket and directory changes remain consistent across failures. For parallel access, verify synchronization during splits and merges. Compare the method with the database's supported alternatives, especially if the application also needs ordered scans. The relevant outcome is dependable retrieval under the workload, not simply a small comparison count.

Check your understanding

After the worked example's split, where does a lookup for key 1 go?

Answer: Its final two bits are 01, so that directory entry leads to the unchanged odd bucket. The 11 entry also references that bucket because its local depth is still one.

Related terms

Linear hashing
Database index
Hash table
bucket
hash collision
global depth
local depth
directory
dynamic indexing

Learn next

Draw directory pointers before and after a split, then contrast a split below global depth with one that requires doubling. Study collision handling and transactional update rules before treating the classroom structure as a deployable index.

Sources

Primary sources: Fagin and colleagues, original-paper record and abstract: https://research.ibm.com/publications/extendible-hashinga-fast-access-method-for-dynamic-files ; Carnegie Mellon implementation guidance: https://15445.courses.cs.cmu.edu/fall2022/project1/ . The original full paper was not retrieved. The example explains the basic directory scheme, not every implementation variant.

Previous: Extended Kalman smoother Next: Extension neural network