algorithm - 具有有序节点的树的搜索成本

Question

上下文:我正在构建一个 FoundationDB，我正在考虑先使用哪个键

假设我们有这组元素:

{AP,AQ,AR,BP,BQ,BR}

我们想从中构建一棵树。一种方式是先按第一个字符分组，再按第二个字符分组，得到

          root
     +-----+------+
     +            +
     A            B
+----+----+  +----+----+
|    |    |  |    |    |
+    +    +  +    +    +
P    Q    R  P    Q    R

另一种可能的方法是先按第二个字符分组，然后按第一个字符分组，得到:

           root
   +--------+--------+
   +        +        +
   P        Q        R
+--+-+   +--+--+   +-+--+
+    +   +     +   +    +
A    B   A     B   A    B

假设字符串的概率分布是均匀的，哪一个导致搜索时间最快？一般来说，最好在顶层或树或底层树上有大量分支？

Answer 1

第一个解决方案将导致从 2 个选项中选择一个，然后从 3 个选项中选择一个，而第二个解决方案将首先从三个选项中选择一个，然后从两个选项中选择一个。理论上两者应该大致相同。

编辑:根据您的评论。如果你有两层，其中的选择数量明显不同，例如 30 和 1000000，我建议你将 30 个选项放在较高级别，然后将 1000000 个选项放在较低级别。我相信缓存会在类似情况下加速较低级别。