尋找B +樹的中位數

Question

我需要實現一個B +樹。

，我需要創建以下方法：

1. 插入（X） - 0（log_t（X））。
2. 搜索 - 成功搜索 - O（log_t（x））。不成功的搜索 - O（1）{具有極高的可能罩}

於是我開始與執行插入（X） - 每次我有一個完整的葉子，我想它分裂成兩個獨立的樹葉。 一個鍵的鍵等於或低於中間鍵，第二個鍵包含鍵值高於中位數的鍵。

如何在不損害運行時間的情況下找到這個中值？

我想到：

1. 每個內部節點的代表和樹葉爲較小的B +樹，但隨後的中值是根（或在根中的元素之一）僅當樹是完全平衡。
2. 將每個內部節點和葉子表示爲一個雙向鏈表。並試圖在插入輸入時獲取中值密鑰，但輸入無法使用。
3. 表示爲數組可能會給我中間，但是當我將它分開時，我需要至少O（n/2）將鍵插入到一個新數組中。

我該怎麼辦？

關於搜索，明智之見：成功搜索和不成功搜索之間的區別在於搜索樹葉，但我仍然需要通過樹的不同鍵「運行」以確定密鑰是否在那個樹。那麼它怎麼可能是O（1）？

Answer 1

在B +樹中，所有的值都存儲在樹葉中。

請注意，您可以將每個葉的指針添加到以下葉，除了標準B +樹之外，還可以獲得一個有序鏈接列表，其中包含所有元素。

現在，請注意，假設你知道在這個鏈表當前正中是什麼 - 在插入/缺失可以廉價地計算新的平均（也可以是同一節點，下一個節點或前一個節點，沒有其他選擇）。
注意，修改此指針O(1)（雖然插入/缺失本身就是O(logn)

鑑於知識 - 一個可以緩存指向中間元素，並確保維持它在插入/缺失當你問。中值 - 只取中值從緩存 - O(1)

---

關於Unsuccessful search - O(1) {With a high likely-hood} - 這一個尖叫bloom filters，這是從來沒有的假陰性AA概率集實現（從來不說š雖然它沒有設置），但有一些誤報（說某事在高速緩存中，而事實上並非如此）。

Answer 2

我已經發布了一個答案（而且由於刪除了它），但有可能我誤解，所以這裏的另一個解釋的答案...

如果你需要隨時知道哪些產品在完成 B +樹容器的中位數。

正如阿米特所說，你可以保持一個指針（連同你的根指針）到包含中位數的當前葉節點。您還可以在該葉節點中保留索引。所以你通過直接跟蹤正確的節點和項目來獲得O（1）訪問權限。

問題在於保持這一點。當然，阿米特對於每一個插入物來說都是正確的，中位數也必須保持相同的物品，或者必須前進到前一個或後一個。如果你有一個通過葉節點的鏈表，即使這意味着步進到一個相鄰的葉節點，也可以有效地處理它。

雖然我不相信，但確定是否或者哪種方式可以步驟很小，除非在中位數和插入恰巧位於同一葉節點的特殊情況下。

如果您知道完整樹的大小（您可以使用根指針輕鬆存儲和維護），那麼您至少可以確定插入前後的中間項應位於哪個索引處。

但是，如果插入點位於中位數之前或之後，則需要知道以前的中位數項是否已將其索引向上移動。除非插入點和中位數恰好在同一個節點中，否則這是一個問題。

矯枉過正的方式 - 增加B +樹以支持計算項目的索引和搜索索引。這樣做的訣竅是每個節點在其子樹的葉節點中總共保留了項目的數量。這可以推高一個級別，以便每個分支節點都有一個子樹大小的數組以及其子節點指針數組。

這提供了兩種解決方案。您可以在搜索時使用這些信息來確定插入點的索引，或者（提供節點具有父指針）可以使用它在插入後重新確定先前中值項目的索引。

[其實三個。插入之後，您可以根據新的大小搜索新的中途索引，而無需參考之前的中間鏈接。]

儘管如此，就存儲用於增強的數據而言，事實證明這是過度殺傷。您不需要知道插入點的索引或之前的中位數 - 您可以在知道插入點的中間位置的哪一側做到。如果您知道從根到中間項的跟蹤路徑，那麼在搜索插入點時，應該能夠跟蹤它的哪一側。所以你只需要增加足夠的信息來找到並維護這條線索。

Answer 3

您不需要B +樹的中位數。您需要分裂節點中的中間密鑰。您必須在該中位數處分割以滿足每個節點具有的條件：N/2 < = n < = N鍵。節點中的中間密鑰只是中間的一個，在n/2，其中n是節點中的實際密鑰的數量。這就是你分割節點的地方。計算是O（1）：它不會損害運行時。

無法在不疊加其他數據結構的情況下從B +樹中獲取O（1）搜索失敗時間。