我正在读这篇论文，使B+树在主内存中具有缓存意识。在第3.1.2节中，作者描述了在CSB+树节点内搜索的几种方法。
基本的方法是使用传统的while循环简单地进行二进制搜索。
uniform方法是通过代码扩展，假设使用了所有键，将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是如何产生的？
如有任何提示，不胜感激。此外，一个指向代码扩展知识的链接也会很有帮助。
事实上，我不确定在纸上提问是否合适，因为在这里转录时可能遗漏了一些关键信息（问题可能需要重新格式化）。我只希望有人碰巧读过这篇论文。
感谢
这里的关键点是来自同一部分的以下报价：
我们把所有的节点中未使用的键（keyList[nKeys..2d-1]）使用尽可能大的密钥
同样重要的是，在B+/CSB+树中，我们搜索的不是节点值，而是这些值之间的间隔。一组可能的值由5个键划分为6个间隔。
由于右侧子树的大部分都填充了尽可能大的密钥（L），因此我们需要比平时更少的比较：
4
/
2 L
/ /
1 3 5 L
/
L L
根节点的右后代具有最大可能的密钥，无需检查其右侧的任何节点。每个间隔需要进行3次比较：
interval comparisons
up to 1 k>4, k>2, k>1
1..2 k>4, k>2, k>1
2..3 k>4, k>2, k>3
3..4 k>4, k>2, k>3
4..5 k>4, k>L, k>5
5..L k>4, k>L, k>5
如果我们把最深的子树放在左边，我们就有了一棵树，非空节点放在更深一层：
L
/
4 L
/ /
2 5 L L
/
1 3
在此树中搜索节点"1"需要将关键字与4个不同的节点进行比较：L、4、2和1。
如果我们知道我们只有五个有效密钥，那么我们有以下树：
2
/
1 4
/
3 5
在这里，我们可以用一种平均2.67个比较的方式来安排比较：
interval comparisons
up to 1 k>2, k>1
1..2 k>2, k>1
2..3 k>2, k>4, k>3
3..4 k>2, k>4, k>3
4..5 k>2, k>4, k>5
5..L k>2, k>4, k>5
"代码扩展"不是一个广泛使用的术语，所以我不能给你最相关的链接。我认为，这与"循环展开"没有太大区别。