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.
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.