主存B +樹的持久性策略

我正在嘗試爲使用C++的鍵值對開發主存索引。我需要確保索引在崩潰後可恢復。我正在使用我發現的CSB +樹實現（BSD許可證）here 我面臨的主要挑戰是在重新實例化節點後維護父子關係數據。我已經搜索了各種策略來保存和恢復到/從磁盤「樹結構」。其中一些是：主存B +樹的持久性策略

將節點對象保存在預訂中，併爲空子指針寫入NULLS。
在將寫入磁盤時，將IDS賦予節點並保存節點的ID而不是指針，然後在使用ID重新實例化期間解析指針。
保存時使用文件偏移量值（物理內存中的地址）而不是子節點的主內存地址。這可能意味着我不得不從葉子開始保存。

我也看了幾個序列化庫。 Google ProtocolBuffers和Boost Serialization。

現在實現中的「節點」有許多指針變量。其中一些是指向其他節點的指針，而另一些則是指向「鍵值」的指針。下面的代碼是簡化版本以保留本質。

struct NodeHead 
{ 
    NodeHead *null; // null indicates internal node 
    char *children; // ptr to children 
    NodeEntry entries[1]; // entry array 
} 

struct NodeEntry 
{ 
    uint16_t offset; // offset to NodeHead of the key in byte 
    uint8_t next; // index of the next entry; 0xff means null 
    uint8_t num; // [0]: number of entries in use 
};

我想直接寫入條目值到數據的nodehead而不是節約了link.And給每個NodeHead實例ID和用它來維持「孩子們」的關係。如果這可以以更好的方式完成，我希望得到一些建議。

來源

2011-03-24 AjP

如果發生崩潰，你說的是墮胎或任何硬性中斷，你將無法序列化任何東西...所以你的策略是什麼使你的數據在你崩潰之前持久化？在每次修改時序列化所有內容不太可行。 – 2011-03-25 07:46:36

我不會在每次修改時序列化。我會定期檢查一下。在檢查點期間，我更願意將索引的「快照」（以及葉子中的數據）保存到磁盤。所以，啓動後我可以恢復索引結構。在2個檢查點之間，我將保留所有事務的日誌，以便在恢復到最新的已提交操作後更新索引快照。關於將快照保存到磁盤，我發現一個類似的問題，問http://stackoverflow.com/questions/872070/saving-btrees-to-a-disk-file-and-read-it。我一直在堅持如何繼續 – AjP 2011-03-25 18:12:31

你也可以做選項3，讓自己擁有索引引用（沒有指針只是引用頁面偏移量 - 在頁面中分配索引），然後當你快速索引索引時，你可以檢查索引'髒位「，並檢查索引的該頁是否已更新，並將整個髒索引頁複製到磁盤。無需走樹，只需索引頁面的索引。 [我提出了類似於CUDA內存複製問題的東西 - 我必須是一個小技巧小馬:)] – PAntoine 2011-04-05 18:04:24

數據（鍵，值）對是分開保存在磁盤上，還是需要將它們與索引一起保存？數據存儲在內存中，還是隻保存索引內存，而數據在磁盤上？如果整個數據集都是駐留內存的，那麼不要堅持樹結構。只需保存（鍵，值）對的有序列表並重新加載樹。我從來沒有使用過這個庫，但任何合理的B樹實現應該能夠非常有效地從預先分類的記錄流中構建一個內存中的B樹。

來源

2011-04-18 04:59:17

主存B +樹的持久性策略

回答

相關問題