Re:Why databases use ordered indexes but programming uses ha...
by mrfusion on Tuesday December 10, 2019 @07:41AM
(#21751882)
Why can’t hash tables shrink and grow gracefully?
[ Parent
| on HN ]
Re:Why databases use ordered indexes but programming uses ha...
by jameshart on Tuesday December 10, 2019 @08:02AM
(#21752031)
Because items are placed into buckets based on their hash, and as you add or remove buckets you need to redistribute items.
I guess it depends what your definition is of ‘graceful’.
Re:Why databases use ordered indexes but programming uses ha...
by geophile on Tuesday December 10, 2019 @03:29PM
(#21756513)
A b-tree grows and shrinks gracefully because each update modifies O(log n) pages. And the base of the logarithm is pretty big.
A typical hash table is not graceful in this way, because while each insert is O(1), you occasionally need to rehash everything into a bigger table, and that is O(n). As I noted above, linear and extensible hashing avoid this problem. An insert that forces a reorg just reorgs one bucket.
Re:Why databases use ordered indexes but programming uses ha...
by tanilama on Tuesday December 10, 2019 @08:43AM
(#21752314)
It might be down to memory/space allocation after all.
All hashtable requires rehashing up to certain fill rate, otherwise it will regress to linear look up. For the two most popular implementations, linked-list based or open addressing based, the common strategy for rehashing is to create another instance of hash table and copy the KV over. But on disk, this will be disastrous.