News for hackers. Stuff that matters.
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.