Extendible Hashing       

Middleware and Datastores Accomplishment | 1979

IBM researcher: Ronald Fagin

Where the work was done: IBM Almaden Research Lab

What we accomplished: From Wikipedia: Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup . . . [T]ime-sensitive applications are less affected by table growth than by standard full-table rehashes.  The method is very widely used.

Related links: Extendible hashing on Wikipedia; Extendible Hashing -- A Fast Access Method for  Dynamic Files 

 

Image credit: Wikipedia Svick

 

BACK TO MIDDLEWARE and DATASTORES
BACK TO IBM RESEARCH ACCOMPLISHMENTS