[發(fā)明專利]一種樹結(jié)構(gòu)數(shù)據(jù)的存儲方法、系統(tǒng)及相關(guān)裝置

在審

• 申請?zhí)枺?/td>: 202010844595.4
• 申請日: 2020-08-20
• 公開（公告）號: CN111984650A
• 公開（公告）日: 2020-11-24
• 發(fā)明（設(shè)計）人: 剛亞州
• 申請（專利權(quán)）人: 蘇州浪潮智能科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2455
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 高勇

本申請?zhí)峁┮环N樹結(jié)構(gòu)數(shù)據(jù)的存儲方法，包括：獲取鍵值對；所述鍵值對包括物理塊地址和對應的邏輯塊地址；判斷同一物理塊地址對應的邏輯塊地址數(shù)量是否大于樹結(jié)構(gòu)中葉子節(jié)點的存儲閾值；若否，將所述鍵值對存于所述樹結(jié)構(gòu)；若是，將超過所述存儲閾值的鍵值對存于所述葉子節(jié)點的溢出頁。本申請使得每個物理塊地址在樹結(jié)構(gòu)中僅對應一個中間節(jié)點，避免在物理塊地址對應邏輯塊地址過多時同一物理塊地址存在多個中間節(jié)點導致的查找錯誤率高的問題，提高系統(tǒng)的數(shù)據(jù)縮減比，從而提高元數(shù)據(jù)訪問效率，數(shù)據(jù)組織可用性更高。本申請還提供一種樹結(jié)構(gòu)數(shù)據(jù)的存儲系統(tǒng)、計算機可讀存儲介質(zhì)和電子設(shè)備，具有上述有益效果。

技術(shù)領(lǐng)域

本申請涉及數(shù)據(jù)存儲領(lǐng)域，特別涉及一種樹結(jié)構(gòu)數(shù)據(jù)的存儲方法、系統(tǒng)及相關(guān)裝置。

背景技術(shù)

在全閃存儲中包括重刪功能，重刪功能指重復的數(shù)據(jù)在SSD上只存儲一份，因此重刪功能可以大大節(jié)省SSD空間，達到容量縮減的功能。重刪功能會產(chǎn)生多個LBA地址(Logical Block Address，邏輯塊地址)與一個PBA地址(Physical Block Address，物理塊地址)的映射關(guān)系。由于這種P-L，即PBA地址和LBA地址一對多的映射關(guān)系，使得標準的B+樹操作不能滿足快速的查找P-L鍵值對的對應關(guān)系。

因此如何改變數(shù)據(jù)的存儲方式以提高數(shù)據(jù)的查找效率是本領(lǐng)域技術(shù)人員亟需解決的技術(shù)問題。

發(fā)明內(nèi)容

本申請的目的是提供一種樹結(jié)構(gòu)數(shù)據(jù)的存儲方法、系統(tǒng)、計算機可讀存儲介質(zhì)和電子設(shè)備，能夠提高邏輯塊數(shù)據(jù)的查找效率。

為解決上述技術(shù)問題，本申請?zhí)峁┮环N樹結(jié)構(gòu)數(shù)據(jù)的存儲方法，具體技術(shù)方案如下：

獲取鍵值對；所述鍵值對包括物理塊地址和對應的邏輯塊地址；

判斷同一物理塊地址對應的邏輯塊地址數(shù)量是否大于樹結(jié)構(gòu)中葉子節(jié)點的存儲閾值；

若否，將所述鍵值對存于所述樹結(jié)構(gòu)；

若是，將超過所述存儲閾值的鍵值對存于所述葉子節(jié)點的溢出頁。

可選的，將超過所述存儲閾值的邏輯塊地址存于所述葉子節(jié)點的溢出頁之前，還包括：

生成所述葉子節(jié)點的溢出頁；

其中，所述葉子結(jié)點的最后一個存儲單元用于保存所述溢出頁的地址。

可選的，還包括：

當所述溢出頁存儲飽和時，分裂所述溢出頁得到第二溢出頁；

將所述邏輯塊地址存于所述第二溢出頁；

其中，所述溢出頁的最后一個存儲單元用于保存所述第二溢出頁的地址。

可選的，還包括：

從緩存請求預設(shè)大小空間，生成所述溢出頁或所述第二溢出頁。

可選的，將所述鍵值對存于所述樹結(jié)構(gòu)包括：

將所述鍵值對中的物理塊地址存于所述樹結(jié)構(gòu)中的中間節(jié)點；

將所述鍵值對中物理塊地址對應的邏輯塊地址存于所述中間節(jié)點對應的葉子節(jié)點。

可選的，若將所述鍵值對中的物理塊地址存于所述樹結(jié)構(gòu)中的中間節(jié)點，則將超過所述存儲閾值的鍵值對存于所述葉子節(jié)點的溢出頁包括：

將未超過所述存儲閾值的邏輯塊地址存于所述葉子節(jié)點，將剩余邏輯塊地址存于所述葉子節(jié)點的溢出頁。

可選的，所述葉子節(jié)點、所述溢出頁和所述第二溢出頁的存儲單元數(shù)量相同。

本申請還提供一種樹結(jié)構(gòu)數(shù)據(jù)的存儲系統(tǒng)，包括：