我正在读报纸，making B+-trees cache conscious in main memory . 在 Section 3.1.2 中，作者描述了在CSB树节点内进行搜索的几种方法 .
基本方法是使用传统的while循环简单地进行二进制搜索 .
统一方法是通过 code expansion ，将while循环展开为 if-then-else 语句，假设使用了所有键 .
作者给出了以下示例，该示例展示了对具有最多9个键的节点的搜索的展开 . 节点中的数字表示在 if 测试中使用的键的位置
4
/ \
2 6
/ \ / \
1 3 5 8
/ \
7 9
然后是令人困惑的部分：
如果实际只存在5个键，我们可以通过3个比较来遍历这个树 . 另一方面，将最深的子树放在左边而不是右边的展开需要在一些分支上进行4次比较 .
那么为什么它需要在下面的树中进行更多的比较：
6
/ \
4 8
/ \ / \
2 5 7 9
/ \
1 3
此外，
如果我们知道我们只有五个有效密钥，我们可以硬编码一棵树，平均而言，使用2.67比较而不是3比较 .
2.67 是怎么来的？
任何提示将不胜感激 . 此外，指导我了解 code expansion 知识的链接会有所帮助 .
实际上，我不确定在纸上提问是否合适，因为在这里转录时可能遗漏了一些关键信息（问题可能需要重新格式化） . 我只是希望有人碰巧读过这篇论文 .
谢谢
1 回答
这里的关键点是以下同一部分的引用：
同样重要的是，在B / CSB树中，我们不搜索节点值，而是搜索这些值之间的间隔 . 一组可能的值被5个键分成6个区间 .
由于大多数正确的子树都填充了最大可能的键（L），因此我们需要比平常更少的比较：
根节点的右后代具有最大可能的密钥，不需要检查其右侧的任何节点 . 每个区间都需要3次比较：
如果我们在左边放置最深的子树，我们有一棵树，非空节点放在一层更深：
在此树中搜索节点“1”需要将密钥与4个不同的节点进行比较：L，4,2和1 .
如果我们知道我们只有五个有效密钥，那么我们有以下树：
在这里，我们可以安排比较，平均得出2.67比较：
"Code expansion"不是一个广泛使用的术语，所以我不能给你最相关的链接 . 我认为，这与"Loop unwinding"没有太大区别 .