Improved extendible hashing with high concurrency
Yasuhiro Hirano, Tetsuji Satoh, Fumiaki Miura · Systems and Computers in Japan · 1995
Abstract We propose an improved extendible hashing scheme and a bucket multi‐versioning scheme that achieve a higher concurrency. In our improved extendible hashing, the global depth and directory entries are asynchronously modified to reduce lock conflicts on the directory. Furthermore, bucket multi‐versioning enables read‐only access to a bucket which is being split. Simulation studies show that these two methods provide an increase in speed in proportion to the number of processors and that they enable concurrent insertions and retrievals to be performed without either affecting the other.