Linear hashing: growing a hash index one bucket at a time
How linear hashing grows a disk hash table one bucket at a time, splitting at a pointer instead of the full bucket, versus static and extendible hashing.
Part of Indexes.
Read first
- Disk access cost: random vs sequential I/O
Why seek and rotation make random I/O over 100× slower than sequential I/O on a disk, and why databases use large pages and locality.
Read next
- B+-trees: why an index lookup takes four reads
How a B+-tree index stays shallow: fanout from big disk pages gives log-base-500 height, leaf splits keep it balanced, linked leaves serve range scans.