Hashtable's average complexity is O(1), and worst case complexity is O(n). Balanced Tree's average complexity is O(logn), worst case complexity is O(logn). Are most databases designed using "tree" instead of "bucket" hashtables? This would give average case O(1) and worst case O(logn), correct?
0
votes
1 Answers
0
votes
Hashtable's ... worst case complexity is O(n).
That's true for many "separate chaining" aka "open hashing" implementations, but some such implementations (e.g. Java's) use balanced trees of colliding elements, reducing worst case complexity to O(log n). For "closed hashing" implementations, the worst case can easily be even worse than O(n): it all depends on how successive buckets are chosen for probing after collisions, and when rehashing is done to increase the number of buckets.
Are most databases designed using "tree" instead of "bucket" hashtables?
What constitutes a "database" is arguable. Doing a survey impractical. And even what you mean by your question is unclear - perhaps you mean to compare separate chaining using trees with closed hashing? I can't comment on the common practice amongst "database"s, but will point out that what is best in any given situation depends very heavily on the size of the keys and values being stored and their collision proneness. As an illustration of the contrast, python "dict"s (dictionaries, which is the python term for hash tables) used closed hashing, whereas the C++ Standard effectively mandates separate chaining, but programmers of both languages complain relatively rarely about those implementation choices.
