树哈希表？
Tree Hashtables?
Hashtable 的平均复杂度为 O(1)，最坏情况复杂度为 O(n)。平衡树的平均复杂度为 O(logn)，最坏情况复杂度为 O(logn)。大多数数据库是使用 "tree" 而不是 "bucket" 哈希表设计的吗？这将给出平均情况 O(1) 和最坏情况 O(logn)，对吗？
Hashtable's ... worst case complexity is O(n).
对于许多 "separate chaining" aka "open hashing" 实现来说都是如此，但是一些这样的实现（例如 Java's）使用碰撞元素的平衡树，将最坏情况的复杂度降低到 O(记录 n)。对于 "closed hashing" 实现，最坏的情况很容易甚至比 O(n) 更糟糕：这完全取决于如何选择连续的桶用于碰撞后的探测，以及何时进行重新散列以增加桶的数量。
Are most databases designed using "tree" instead of "bucket" hashtables?
"database" 的构成是有争议的。做一个不切实际的调查。甚至你的问题的意思也不清楚 - 也许你的意思是比较使用树的单独链接和封闭散列？我无法评论 "database" 之间的常见做法，但会指出在任何给定情况下最好的做法在很大程度上取决于存储的键和值的大小及其冲突倾向。作为对比的例证，python "dict"s（字典，这是哈希表的 python 术语）使用封闭哈希，而 C++ 标准有效地强制要求分离链接，但程序员两种语言都很少抱怨这些实现选择。
Hashtable 的平均复杂度为 O(1)，最坏情况复杂度为 O(n)。平衡树的平均复杂度为 O(logn)，最坏情况复杂度为 O(logn)。大多数数据库是使用 "tree" 而不是 "bucket" 哈希表设计的吗？这将给出平均情况 O(1) 和最坏情况 O(logn)，对吗？
Hashtable's ... worst case complexity is O(n).
对于许多 "separate chaining" aka "open hashing" 实现来说都是如此，但是一些这样的实现（例如 Java's）使用碰撞元素的平衡树，将最坏情况的复杂度降低到 O(记录 n)。对于 "closed hashing" 实现，最坏的情况很容易甚至比 O(n) 更糟糕：这完全取决于如何选择连续的桶用于碰撞后的探测，以及何时进行重新散列以增加桶的数量。
Are most databases designed using "tree" instead of "bucket" hashtables?
"database" 的构成是有争议的。做一个不切实际的调查。甚至你的问题的意思也不清楚 - 也许你的意思是比较使用树的单独链接和封闭散列？我无法评论 "database" 之间的常见做法，但会指出在任何给定情况下最好的做法在很大程度上取决于存储的键和值的大小及其冲突倾向。作为对比的例证，python "dict"s（字典，这是哈希表的 python 术语）使用封闭哈希，而 C++ 标准有效地强制要求分离链接，但程序员两种语言都很少抱怨这些实现选择。