1

我正在阅读论文，使 B+-trees 缓存在主内存中具有意识。在第 3.1.2 节中，作者描述了几种在 CSB+ 树节点中搜索的方法。

基本方法是使用传统的 while 循环简单地进行二进制搜索。

统一的方法是通过代码扩展，将 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是怎么来的？

任何提示将不胜感激。此外，将我指向代码扩展知识的链接会很有帮助。

实际上，我不确定在论文上提出问题是否合适，因为在此处转录时可能遗漏了一些关键信息（问题可能需要重新格式化）。我只是希望有人碰巧读过这篇论文。

谢谢

4

1 回答 1

1

这里的关键点是同一部分的以下引用：

我们将所有未使用的键 (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

“代码扩展”不是一个广泛使用的术语，所以我不能给你最相关的链接。我认为，这与"Loop unwinding"没有太大区别。

于 2012-09-15T15:28:45.503 回答