按照什麼順序將一組已知密鑰插入B樹中以獲得最小高度？

Question

給定固定數量的鍵或值（存儲在數組中或某些數據結構中）和b樹的順序，我們可以確定插入關鍵字的順序，從而生成一個節省空間的b-樹。

爲了說明，考慮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 

我們可以看到在那裏有降低的水平。

那麼是否有一種確定插入順序的特定方法來減少空間消耗？

Answer 1

不幸的是，所有的樹木表現出他們的最壞的情況下運行時間，並且需要剛性平衡技術時一樣，爲了提高輸入的數據。二叉樹很快變成鏈表，等等。

對於典型的B-Tree用例（數據庫，文件系統等），您通常可以指望您的數據自然更分散，從而生成更像您的第二個示例的樹。

雖然如果真的是一個問題，你可以散列每個鍵，保證更廣泛的值分佈。

for(i=1; i<8; ++i) 
    tree.push(hash(i)); 

Answer 2

下面的技巧應適用於大多數下令查找樹，假設數據插入都是整數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，您可以使用此位反轉值決定下一個要插入的項目 - 第一個插入使用第四個項目，第二個插入使用第二個項目，依此類推。一個複雜因素 - 你必須向上舍入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樹適應它不應該太難。

Answer 3

要構建使用插入（），其爲黑盒的特定的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 

et cetera。

Answer 4

這是我想補充的元素b樹。

感謝Steve314，讓我開始用二進制表示，

給出的是n個元素的添加，爲了。我們必須將它添加到m階B樹中。取其索引（1 ... n）並將其轉換爲基數m。這種插入的主要思想是插入當前具有最高m-radix位的數字，並將其保持在樹中添加的較小m-基數之上，儘管分割節點。

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樹修復。

我在桶中添加樹元素。首先我添加桶元素，然後按順序完成下一個桶。如果中位數已知，剷鬥可以很容易地創建，剷鬥大小爲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. 

• 對於左位選擇，我插入水桶樹從右側開始，右位選擇，我從插入左側桶。選擇left-median，我們先插入中位數，然後首先插入它的左邊的元素，然後插入桶中的其餘數字。

例

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-基數號碼留在上面。這裏我只有兩個級別，對於更多級別，我按照基數位的降序重複相同的過程。

最後一種情況是當其餘元素的基數相同，並且沒有小數位的數字時，只需插入它們並完成該過程即可。

我會舉三個級別的示例，但顯示時間太長。所以請嘗試與其他參數，並告訴它是否工作。

Answer 5

那麼，有沒有確定插入的序列，將減少空間消耗一種特殊的方式？

編輯注：因爲這個問題很有意思，我盡力提高我帶着幾分哈斯克爾的答案。

設k是B樹和list鍵

空間消耗的最小化有一個平凡解的列表的Knuth的順序：

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

這種算法將有效產生時間效率低下 B-Tree，左側不平衡，但最小空間消耗。

存在許多不平凡的解決方案，其生產效率較低，但顯示更好的查找性能（較低的高度/深度）。如您所知，這全是關於權衡！

一個簡單的算法，能夠最大限度地減少B樹的深度和空間消耗（但並不減少查找性能！），是以下

-- 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]和B樹與Knuth的順序= 3，我們應該得到[18, 5, 9, 1, 2, 6, 7, 12, 16, 21]用所得的B樹等

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

顯然，這是從性能POIN次優的觀點噸，但應該是可以接受的，因爲獲得一個更好的（如以下）將更爲昂貴的（計算上和經濟上）：

  [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