具有可變長度密鑰的B +樹

Question

在B +樹的常見實現中，我們可以假定密鑰具有固定長度（例如25字節）。然後我們可以定義每個節點必須具有最少數量的鍵和最大數量。

如果我想樹接受可變長度的鍵，我應該修改什麼？如果我說節點必須至少有2個密鑰，但是我試圖插入的密鑰太大，以至於它不適合保存該節點的塊？

Answer 1

的簡單的解決方案是存儲密鑰作爲指針（包裹在覆蓋相對運營商等類型），而不是值，但當然損害了局部性即使用B +樹的點的一部分。

這就是說，項越大，更少它很重要的項目是在存儲器中相鄰的。巨大的項目甚至不適合一個緩存頁面，更不用說在同一頁面中的多個項目。

另一種比較簡單的方法是使用一個聯合類型或放置新的或任何一個內存爲項目型這對你可能會使用所有項目類型足夠大的內分配的項目。每個項目仍有固定的字節數，但項目不一定使用所有這些字節。

如果你願意做這項工作，你可以有可變大小的節點。當然，根據您如何安排節點內數據結構來應對這些問題，您會遇到一些麻煩。例如，您可能在節點中有少量的項目指針，指向也在節點內部的項目（未單獨分配到堆上）。

此外，每次更改節點時都需要重新分配節點。即使你正在做的是重新平衡，這可能會將一個巨大的項目從一個節點移動到另一個節點，並且即使目標節點有一個空閒空間用於某個項目的空閒位置，它可能沒有足夠的字節來存儲值。

從某種意義上說，每個節點都是一個小堆，您可以在其中分配或釋放空間用於大或小的項目，但有時您必須返回到適當的堆以將小堆替換爲一個更大或更小的一個。

又到了值得一提的是，如果該項目是巨大的，在節點內地方可能不是不相干。

我實現了B +我之前在內存式的多路樹，但我從來沒有去過這種極端。

Answer 2

使用散列。哈希是密鑰的固定大小表示。要獲得更好的散列函數，請參閱http://www.cse.yorku.ca/~oz/hash.html。

Answer 3

你可以把一大關鍵其餘溢出頁面，像there。