23

给定固定数量的键或值（存储在数组或某些数据结构中）和 b-tree 的顺序，我们能否确定插入键的顺序以生成空间高效的 b-tree。

为了说明，考虑 3 阶的 b-tree。让键是 {1,2,3,4,5,6,7}。按以下顺序将元素插入树中

for(int i=1 ;i<8; ++i)
{
 tree.push(i);  
}

会创建一棵这样的树

        4
     2      6
   1  3   5   7

见http://en.wikipedia.org/wiki/B-tree

但是以这种方式插入元素

flag = true;
for(int i=1,j=7; i<8; ++i,--j)
{
    if(flag)
    {
        tree.push(i);
        flag = false;
    }
    else
    {
        tree.push(j);
        flag = true;
    }   
}

像这样创建一棵树

    3 5
1 2  4  6 7

我们可以看到水平下降。

那么有没有一种特殊的方法来确定可以减少空间消耗的插入顺序？

4

5 回答 5

7

假设要插入的数据是整数，以下技巧应该适用于大多数有序搜索树1..n。

考虑整数键的二进制表示 - 对于 1..7（用点表示零），这是......

Bit : 210
  1 : ..1
  2 : .1.
  3 : .11
  4 : 1..
  5 : 1.1
  6 : 11.
  7 : 111

第 2 位更改频率最低，第 0 位更改频率最高。这与我们想要的相反，所以如果我们颠倒这些位的顺序，然后按照这个位颠倒的值的顺序对我们的键进行排序......

Bit : 210    Rev
  4 : 1.. -> ..1 : 1
  ------------------
  2 : .1. -> .1. : 2
  6 : 11. -> .11 : 3
  ------------------
  1 : ..1 -> 1.. : 4
  5 : 1.1 -> 1.1 : 5
  3 : .11 -> 11. : 6
  7 : 111 -> 111 : 7

用不平衡的二叉搜索树来解释这一点是最容易的，它通过添加叶子来增长。第一项是死点——它正是我们想要的根项。然后我们为下一层添加键。最后，我们添加叶子层。在每一步，树都尽可能地平衡，因此即使您碰巧正在构建 AVL 或红黑平衡树，也不应调用重新平衡逻辑。

[编辑我刚刚意识到您不需要根据这些位反转值对数据进行排序，以便按该顺序访问键。诀窍是注意位反转是它自己的逆。除了将键映射到位置之外，它还将位置映射到键。因此，如果您从 1..n 循环，您可以使用此位反转值来决定接下来要插入哪个项目 - 第一个插入使用第 4 个项目，第二个插入使用第二个项目，依此类推。一个复杂的问题 - 您必须将 n 向上舍入到小于 2 的幂（7 可以，但使用 15 而不是 8）并且您必须对位反转值进行边界检查。原因是位反转可以将一些界内位置移出界外，反之亦然。]

实际上，对于红黑树，将调用一些重新平衡逻辑，但它应该只是重新着色节点 - 而不是重新排列它们。但是，我没有仔细检查，所以不要依赖这个说法。

对于 B 树，树的高度通过添加新根而增长。因此，证明这个工作有点尴尬（它可能需要比 B 树通常需要的更仔细的节点分割），但基本思想是相同的。尽管发生了重新平衡，但由于插入的顺序，它以平衡的方式发生。

这可以推广到任何一组预先知道的键，因为一旦对键进行了排序，您就可以根据该排序顺序分配合适的索引。

警告- 这不是从已知的已排序数据构建完美平衡树的有效方法。

如果您已经对数据进行了排序，并且知道它的大小，则可以在 O(n) 时间内构建一个完美平衡的树。这是一些伪代码...

if size is zero, return null
from the size, decide which index should be the (subtree) root
recurse for the left subtree, giving that index as the size (assuming 0 is a valid index)
take the next item to build the (subtree) root
recurse for the right subtree, giving (size - (index + 1)) as the size
add the left and right subtree results as the child pointers
return the new (subtree) root

基本上，这会根据大小决定树的结构并遍历该结构，沿途构建实际的节点。适应 B 树应该不会太难。

于 2013-05-15T02:34:24.257 回答
6

这就是我将元素添加到 b-tree 的方式。

感谢 Steve314，让我开始使用二进制表示，

给定 n 个要按顺序添加的元素。我们必须将它添加到 m-order b-tree 中。取它们的索引 (1...n) 并将其转换为基数 m。这种插入的主要思想是插入当前具有最高 m-radix 位的数字，并将其保持在树中添加的较小 m-radix 数字之上，尽管节点分裂。

1,2,3.. 是索引，因此您实际上插入了它们指向的数字。

For example, order-4 tree
      4       8         12           highest radix bit numbers
1,2,3   5,6,7   9,10,11    13,14,15

现在取决于订单中位数可以是：

  • 顺序为偶数 -> 键数为奇数 -> 中位数为中间（中位数）
  • 顺序为奇数 -> 键数为偶数 -> 左中位数或右中位数

要提升的中位数（左/右）的选择将决定我应该插入元素的顺序。这必须为 b-tree 修复。

我向桶中的树添加元素。首先，我添加存储桶元素，然后按顺序添加下一个存储桶。如果中值已知，则可以轻松创建存储桶，存储桶大小为 m 阶。

I take left median for promotion. Choosing bucket for insertion.
    |  4     |  8      |   12       |    
1,2,|3   5,6,|7   9,10,|11    13,14,|15  
        3       2          1             Order to insert buckets.
  • 对于左中值选择，我从右侧开始将桶插入树，对于右中值选择，我从左侧插入桶。选择左中位数，我们首先插入中位数，然后先插入其左侧的元素，然后再插入桶中的其余数字。

例子

Bucket median first
12,
Add elements to left
11,12,
Then after all elements inserted it looks like,
|   12       | 
|11    13,14,| 
Then I choose the bucket left to it. And repeat the same process.
Median
     12        
8,11    13,14, 
Add elements to left first
       12        
7,8,11    13,14, 
Adding rest
  8      |   12        
7   9,10,|11    13,14, 
Similarly keep adding all the numbers,
  4     |  8      |   12        
3   5,6,|7   9,10,|11    13,14, 
At the end add numbers left out from buckets.
    |  4     |  8      |   12       |   
1,2,|3   5,6,|7   9,10,|11    13,14,|15

  • 对于中位数（甚至顺序 b 树），您只需插入中位数，然后插入桶中的所有数字。

  • 对于右中位数，我从左侧添加桶。对于桶中的元素，我首先插入中值，然后插入右元素，然后插入左元素。

在这里，我们添加了最高的 m 基数，在这个过程中，我添加了具有较小 m 基数位的数字，确保最高的 m 基数保持在顶部。这里我只有两个级别，对于更多级别，我按照基数的降序重复相同的过程。

最后一种情况是当剩余元素具有相同的基位并且没有具有较小基位的数字时，只需将它们插入并完成该过程。

我会举一个 3 个级别的例子，但是太长了，无法展示。所以请尝试使用其他参数并判断它是否有效。

于 2013-05-20T05:34:18.327 回答
1

那么有没有一种特殊的方法来确定可以减少空间消耗的插入顺序？

编辑说明：由于这个问题很有趣，我尝试用一​​些 Haskell 来改进我的答案。

让我们k成为 B-Tree 的 Knuth 顺序和list键列表

空间消耗最小化有一个简单的解决方案：

-- won't use point free notation to ease haskell newbies
trivial k list = concat $ reverse $ chunksOf (k-1) $ sort list

这种算法将有效地产生一个时间效率低的B-Tree，左侧不平衡，但空间消耗最小。

存在许多非平凡的解决方案，它们的生成效率较低，但显示出更好的查找性能（较低的高度/深度）。如您所知，这都是关于权衡的！

一个最小化 B-Tree 深度和空间消耗的简单算法（但它不会最小化查找性能！），如下所示

-- Sort the list in increasing order and call sortByBTreeSpaceConsumption 
-- with the result
smart k list = sortByBTreeSpaceConsumption k $ sort list

-- Sort list so that inserting in a B-Tree with Knuth order = k 
-- will produce a B-Tree  with minimal space consumption minimal depth 
-- (but not best performance)
sortByBTreeSpaceConsumption :: Ord a => Int -> [a] -> [a]
sortByBTreeSpaceConsumption _ [] = []
sortByBTreeSpaceConsumption k list
    | k - 1 >= numOfItems = list  -- this will be a leaf
    | otherwise = heads ++ tails ++ sortByBTreeSpaceConsumption k remainder
    where requiredLayers = minNumberOfLayersToArrange k list
          numOfItems = length list
          capacityOfInnerLayers = capacityOfBTree k $ requiredLayers - 1
          blockSize = capacityOfInnerLayers + 1 
          blocks = chunksOf blockSize balanced
          heads = map last blocks
          tails = concat $ map (sortByBTreeSpaceConsumption k . init) blocks
          balanced = take (numOfItems - (mod numOfItems blockSize)) list
          remainder = drop (numOfItems - (mod numOfItems blockSize)) list

-- Capacity of a layer n in a B-Tree with Knuth order = k
layerCapacity k 0 = k - 1
layerCapacity k n = k * layerCapacity k (n - 1)

-- Infinite list of capacities of layers in a B-Tree with Knuth order = k
capacitiesOfLayers k = map (layerCapacity k) [0..]

-- Capacity of a B-Tree with Knut order = k and l layers
capacityOfBTree k l = sum $ take l $ capacitiesOfLayers k

-- Infinite list of capacities of B-Trees with Knuth order = k 
-- as the number of layers increases
capacitiesOfBTree k = map (capacityOfBTree k) [1..]

-- compute the minimum number of layers in a B-Tree of Knuth order k 
-- required to store the items in list
minNumberOfLayersToArrange k list = 1 + f k
    where numOfItems = length list
          f = length . takeWhile (< numOfItems) . capacitiesOfBTree

使用这个smart函数给定一个list = [21, 18, 16, 9, 12, 7, 6, 5, 1, 2]和一个 knuth order = 3 的 B-Tree，我们应该得到[18, 5, 9, 1, 2, 6, 7, 12, 16, 21]一个类似的 B-Tree

              [18, 21]
             /
      [5 , 9]
     /   |   \
 [1,2] [6,7] [12, 16]

显然，从性能的角度来看，这是次优的，但应该可以接受，因为获得更好的（如下所示）会更加昂贵（计算和经济）：

          [7 , 16]
         /   |   \
     [5,6] [9,12] [18, 21]
    /
[1,2]

如果要运行它，请将前面的代码编译到 Main.hs 文件中，并在前置后使用 ghc 进行编译

import Data.List (sort)
import Data.List.Split
import System.Environment (getArgs)

main = do
    args <- getArgs
    let knuthOrder = read $ head args
    let keys = (map read $ tail args) :: [Int]
    putStr "smart: "
    putStrLn $ show $ smart knuthOrder keys
    putStr "trivial: "
    putStrLn $ show $ trivial knuthOrder keys
于 2013-05-22T02:17:11.707 回答
1

不幸的是，所有的树都表现出它们最坏情况下的运行时间，并且当数据以这样的递增顺序输入时需要严格的平衡技术。二叉树很快变成链表等。

对于典型的 B-Tree 用例（数据库、文件系统等），您通常可以指望您的数据自然分布得更加分散，从而生成更像您的第二个示例的树。

虽然如果它真的是一个问题，你可以散列每个键，保证更广泛的值分布。

for( i=1; i<8; ++i )
    tree.push(hash(i));
于 2013-05-13T06:25:41.843 回答
1

要使用 Insert() 作为黑盒来构建特定的 B 树，请向后工作。给定一个非空的 B 树，找到一个节点，其子节点数超过最小数量，并且尽可能靠近叶子节点。根被认为具有最小值 0，因此始终存在具有最小子节点数的节点。从此节点中删除要添加到 Insert() 调用列表的值。朝着叶子工作，合并子树。

例如，给定 2-3 树

       8
   4       c
 2   6   a   e
1 3 5 7 9 b d f,

我们选择8并进行合并以获得前任

   4      c
 2   6  a   e
1 3 5 79 b d f.

然后我们选择9。

   4     c
 2   6 a   e
1 3 5 7 b d f

然后一个。

    4    c
 2    6    e
1 3  5 7b d f

然后 B.

   4   c
 2   6   e
1 3 5 7 d f

然后 C.

   4
 2   6  e
1 3 5 7d f

等等。

于 2013-05-15T14:15:46.597 回答