如何在给定一组预定密钥的情况下对密钥重新排序,以便在插入B树时使用最少数量的节点？

Question

所以我有一个问题,我很确定它是可以解决的,但经过许多小时的思考和讨论,只取得了部分进展.

问题如下.我正在构建一个BTree,可能是几百万个密钥.在搜索BTree时,它会根据需要从磁盘分页到内存,并且每个操作页面都相对昂贵.这实际上意味着我们需要遍历尽可能少的节点(尽管在遍历节点之后,遍历该节点的成本,直到该节点为0).因此,我们不希望通过使大量节点接近最小容量来浪费空间.从理论上讲,这应该是可以预防的(在合理范围内),因为树的结构取决于键插入的顺序.

因此,问题是如何重新排序密钥,以便在构建BTree之后使用最少数量的节点.这是一个例子:

我偶然发现了这个问题你应该以什么顺序将一组已知的密钥插入到B-Tree中以获得最小的高度？不幸的是,这个问题略有不同.答案,似乎也没有解决我的问题.还有一点值得补充的是,我们希望通过手动构建树来获得数学保证,并且只使用insert选项.我们不想手动构建树,犯错误,然后发现它是无法搜索的!

我也偶然发现了两篇研究论文,这些论文非常接近解决我的问题,但并不完全存在! B树和最佳2,3树的时间和空间最优性(我实际上从上面拍摄了图像)讨论并量化了空间最优和空间质量BTrees之间的差异,但是没有达到描述如何设计插入顺序,就我所知.

任何有关这方面的帮助都将非常感激.

谢谢

研究论文可在以下网址找到:

http://www.uqac.ca/rebaine/8INF805/Automne2007/Sujets2007Automne/p174-rosenberg.pdf

http://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1143&context=hmc_fac_pub

编辑::我最终用FILLORDER算法填充了如上文所述构造的btree骨架.如前所述,我希望避免这种情况,但是在发布了2个优秀答案之前我最终实现了它!

Answer 1

下面的算法应该适用于节点中键的最小数量 = d 且最大值 = 2*d 的 B 树，我想如果选择中值的方式已知，它可以推广到 2*d + 1 个最大键。

下面的算法旨在最小化节点数量而不仅仅是树的高度。

该方法基于将密钥放入任何非完整叶子中的想法，或者如果所有叶子都已满则将密钥放在最低非完整节点下。

更准确地说，所提出的算法生成的树满足以下要求： 具有最小可能的高度；每个级别上不超过两个非完整节点。（它始终是两个最右边的节点。）

由于我们知道除根之外的任何级别上的节点数都严格等于上一级上的节点数和总键数之和，因此我们可以证明级别之间不存在有效的节点重新排列，从而减少节点总数。例如，增加插入到任何特定级别之上的键的数量将导致该级别上的节点的增加，从而导致节点总数的增加。虽然任何将键数量减少到特定级别以上的尝试都会导致该级别上的节点数减少，并且无法在不增加树高度的情况下容纳该级别上的所有键。同样明显的是，任何特定级别上的按键排列都是最佳排列之一。使用上述推理，还可以通过数学归纳法构建更正式的证明。

这个想法是保存计数器列表（列表的大小不大于树的高度）来跟踪在每个级别上添加了多少键。一旦我将 d 键添加到某个级别，这意味着在该级别中创建的节点被填充了一半，如果有足够的键来填充该节点的另一半，我们应该跳过此键并为更高级别添加根。通过这种方式，根将恰好放置在前一个子树的前半部分和下一个子树的前半部分之间，这将导致分裂，当根取代它时，两半子树将分开。当我们使用更大的钥匙时，放置跳过的钥匙的地方将是安全的，并且可以稍后填充。

这是几乎可以工作的（伪）代码，数组需要排序：

PushArray(BTree bTree, int d, key[] Array)
{
    List<int> counters = new List<int>{0};
    //skip list will contain numbers of nodes to skip 
    //after filling node of some order in half
    List<int> skip  = new List<int>();
    List<Pair<int,int>> skipList = List<Pair<int,int>>();

    int i = -1;
    while(true)
    {     
       int order = 0;
       while(counters[order] == d) order += 1;
       for(int j = order - 1; j >= 0; j--) counters[j] = 0;

       if (counters.Lenght <= order + 1) counters.Add(0);
       counters[order] += 1;

       if (skip.Count <= order)
              skip.Add(i + 2);    
       if (order > 0)
           skipList.Add({i,order}); //list of skipped parts that will be needed later
       i += skip[order];

       if (i > N) break;

       bTree.Push(Array[i]);
    }

    //now we need to add all skipped keys in correct order
    foreach(Pair<int,int> p in skipList)
    {
        for(int i = p.2; i > 0; i--)
            PushArray(bTree, d, Array.SubArray(p.1 + skip[i - 1], skip[i] -1))
    }
}

例子：

以下是在第一次遍历数组时，对于 d = 2，数字和相应的计数器键应如何排列。我用“o”标记了在第一次传递期间推入 B 树的键（在递归循环之前）并用“x”跳过。

                                                              24
        4         9             14             19                            29 
0 1 2 3   5 6 7 8   10 11 12 13    15 16 17 18    20 21 22 23    25 26 27 28    30 ...
o o x x o o o x x o  o  o  x  x  x  x  x  x  x  x  x  x  x  x  o  o  o  x  x  o  o ...
1 2     0 1 2     0  1  2                                      0  1  2        0  1 ...
0 0     1 1 1     2  2  2                                      0  0  0        1  1 ...
0 0     0 0 0     0  0  0                                      1  1  1        1  1 ...
skip[0] = 1 
skip[1] = 3 
skip[2] = 13

由于我们不迭代跳过的键，因此无需添加 B 树本身和排序数组，时间复杂度为 O(n)；

在这种形式中，当没有足够的键来填充跳过块后的节点的后半部分时，可能不清楚它是如何工作的，但如果数组的总长度小于〜i + 2 *，我们也可以避免跳过所有skip[order]键而是使用skip[order]和skip[order - 1]键，在更改计数器之后但在更改变量i之前可能会添加这样的字符串：

while(order > 0 && i + 2*skip[order] > N) --order;

这将是正确的，因为如果当前级别的键总数小于或等于 3*d，如果按原始顺序添加它们，它们仍然会正确分割。这将导致在某些级别上最后两个节点之间的键重新排列略有不同，但不会破坏任何所描述的要求，并且可能会使行为更容易理解。

也许找到一些动画并观察它是如何工作的是合理的，这是应该在 0..29 范围内生成的序列：0 1 4 5 6 9 10 11 24 25 26 29 /第一遍结束/ 2 3 7 8 14 15 16 19 20 21 12 13 17 18 22 23 27 28