二叉树是最优的，除非它们不是

搜索树的最佳案例深度是 ，如果 是树的元数（或分支）。直觉上，我们知道如果我们增加 ，深度会下降，但仅此而已吗？如果不是，我们如何选择最佳分支？虽然最佳搜索树确实会有 depth ，但我们不能无限增加，因为我们还增加了必须在每个节点中进行的比较次数。 -ary 树将有（在最坏的情况下）键，对于每个键，我们必须对小于和相等进行比较（最右边的子树将在没有比较的情况下被搜索，它将是所有的“else”比较）。我们必须首先了解这些比较如何影响平均搜索时间。如果我们使用简单的比较方案，每个键都要求进行两次（可能很昂贵）比较。一个测试所寻求的值是否小于一个键；一个来测试它们是否相等。如果两个测试都不为真，我们继续下一个键。如果所有测试都不为真，则是“其他”情况，我们将沿着最右边的分支进行。该方案所做的工作比必要的多，并且会要求每个节点进行比较（因为每个节点都有键）。这种直接方法的主要问题是比较可能非常昂贵。虽然比较两个整数类型（ int 等）通常被认为是“免费的”，但比较字符串是昂贵的。因此，您显然不想对两个字符串进行两次测试，一次用于 <，一次用于 =。更好的方法是使用三向比较，也称为“飞船操作员”。宇宙飞船运算符 <=> 是 C++20 版本的 C 的旧 qsort 比较函数（实际上更好，因为它还能自动提供所有比较运算符）。基本上，如果 a<b，则 a<=>b 可以返回 <0，如果它们相等，则返回 0，如果 a>b，则返回 >0。因此，我们可以存储昂贵比较的结果，然后对结果进行廉价比较。这减少了对每个节点进行昂贵比较的次数。搜索复杂度，计算最好情况树在最坏情况下的比较次数是一个严格递增的函数（因为我们可以将其视为一个常数，因为我们没有优化 ）：

我们忽略了，或者说抽象了一些重要的东西：访问节点的成本。在主存中，可以很方便地假设读取一个节点是免费的，即没有成本。这当然是错误的，因为即使从缓存中读取也会导致延迟；幸运的是很小。如果我们从磁盘读取节点（是的，甚至是 NVMe），那就更错误了。一个经典的旋转锈盘读取一个块会导致几毫秒的延迟，相对于比较内存中的两个键（一旦它们）来说，这可能真的非常昂贵。与比较成本，和 ，访问节点的成本。我们可以设置为 1 并相对于 .让我们说类似的事情。现在，对我们来说幸运的是，这个函数在 中是凸的，所以我们可以求解最优给定 和 。为此，我们取导数并找到它为零的地方，即求解 。由于分母在 中严格递增，我们必须求解零分子。但是，有一个轻微的复杂性：不是代数。我们必须使用 Lambert W 函数的数值解。它给了我们， ， ，下图显示了函数的表面， 和 ，一个轴是 ，块大小，另一个是 ，树中的项目数。绿色平面显示了使用 Lambert W 函数找到的最优值。总而言之，当我们忽略访问节点的成本时，二叉树是最佳的，但当访问节点的成本变得更高时，它们就不是最优的了。当我们访问磁盘上的节点时，成本很高，在一个节点中捆绑许多键变得很有趣，我们给出了最佳解决方案。然而，这个问题通常可以更直接地解决。我们只是在一个 I/O 块中放置尽可能多的键。磁盘在（通常）512 字节的小块上运行，但文件系统在更大但固定大小的块上运行，例如 4 或 8k。因此，一个好的策略是在该块中放入尽可能多的键，因为即使比较的数量很大，它仍然比将该块放入主内存要快。