[發(fā)明專利]基于支持重復(fù)鍵值樹數(shù)據(jù)結(jié)構(gòu)管理磁盤數(shù)據(jù)的方法和裝置

有效

• 申請?zhí)枺?/td>: 201810826999.3
• 申請日: 2018-07-25
• 公開（公告）號: CN108984780B
• 公開（公告）日: 2021-10-22
• 發(fā)明（設(shè)計）人: 鄒虎
• 申請（專利權(quán)）人: 鄭州云海信息技術(shù)有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 王寶筠

本申請實施例公開一種基于支持重復(fù)鍵值樹數(shù)據(jù)結(jié)構(gòu)管理數(shù)據(jù)的方法和裝置，該方法用于樹數(shù)據(jù)結(jié)構(gòu)，樹數(shù)據(jù)結(jié)構(gòu)包括至少兩級節(jié)點，每級節(jié)點包括至少一個節(jié)點，每個節(jié)點中存儲鍵值，鍵值包括關(guān)鍵字和關(guān)鍵字對應(yīng)的值，該樹數(shù)據(jù)結(jié)構(gòu)支持一個關(guān)鍵字對應(yīng)多個值。在插入鍵值過程中，獲取待處理鍵值，判斷待處理鍵值中的關(guān)鍵字是否與目標(biāo)節(jié)點中已存儲的關(guān)鍵字匹配，目標(biāo)節(jié)點為樹數(shù)據(jù)結(jié)構(gòu)中任一節(jié)點；若匹配，根據(jù)待處理鍵值中的關(guān)鍵字對應(yīng)的值將待處理鍵值插入到目標(biāo)節(jié)點中。可見，該樹數(shù)據(jù)結(jié)構(gòu)可以支持重復(fù)鍵值，即使待處理鍵值中的關(guān)鍵字與樹數(shù)據(jù)結(jié)構(gòu)中已存儲的關(guān)鍵字相同，也可以在保留已存儲的關(guān)鍵字的情況下插入待處理鍵值，滿足用戶對存儲系統(tǒng)的需求。

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

本申請涉及數(shù)據(jù)處理領(lǐng)域，特別是涉及一種基于支持重復(fù)鍵值樹數(shù)據(jù)結(jié)構(gòu)管理數(shù)據(jù)的方法和裝置。

背景技術(shù)

在存儲系統(tǒng)中，通常采用樹數(shù)據(jù)結(jié)構(gòu)作為元數(shù)據(jù)在內(nèi)存中建立邏輯區(qū)塊地址(Logical Block Address，簡稱LBA)到磁盤地址的映射，例如B+樹。

傳統(tǒng)的B+樹中存儲有鍵值(Key Value，簡稱KV)，其中，Key是關(guān)鍵字，Value是關(guān)鍵字對應(yīng)的值，Value用于表示磁盤地址，一個key對應(yīng)一個Value，這樣，根據(jù)B+樹可以實現(xiàn)對磁盤地址對應(yīng)存儲位置的數(shù)據(jù)進(jìn)行管理。

然而，傳統(tǒng)的B+樹只能支持單一的鍵值，在插入鍵值的過程中，一旦B+樹中已經(jīng)存在該key，會直接對其進(jìn)行覆蓋或者返回錯誤。因此，傳統(tǒng)的B+樹無法支持重復(fù)鍵值的特殊情況，難以滿足用戶對存儲系統(tǒng)的需求。

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

為了解決上述技術(shù)問題，本申請?zhí)峁┝艘环N基于支持重復(fù)鍵值樹數(shù)據(jù)結(jié)構(gòu)管理數(shù)據(jù)的方法和裝置，該方法可以支持重復(fù)鍵值，即使待處理鍵值中的關(guān)鍵字與樹數(shù)據(jù)結(jié)構(gòu)中已存儲的關(guān)鍵字相同，也可以在保留已存儲的關(guān)鍵字的情況下插入待處理鍵值，滿足用戶對存儲系統(tǒng)的需求。

本申請實施例公開了如下技術(shù)方案：

第一方面，本申請實施例提供了一種基于支持重復(fù)鍵值樹數(shù)據(jù)結(jié)構(gòu)管理數(shù)據(jù)的方法，應(yīng)用于樹數(shù)據(jù)結(jié)構(gòu)，所述樹數(shù)據(jù)結(jié)構(gòu)包括至少兩級節(jié)點，每級節(jié)點包括至少一個節(jié)點，每個節(jié)點中存儲鍵值，所述鍵值包括關(guān)鍵字和關(guān)鍵字對應(yīng)的值，所述樹數(shù)據(jù)結(jié)構(gòu)支持一個關(guān)鍵字對應(yīng)多個值，所述方法包括：

獲取待處理鍵值；

判斷所述待處理鍵值中的關(guān)鍵字是否與目標(biāo)節(jié)點中已存儲的關(guān)鍵字匹配，所述目標(biāo)節(jié)點為所述樹數(shù)據(jù)結(jié)構(gòu)中任一節(jié)點；

若匹配，則根據(jù)所述待處理鍵值中的關(guān)鍵字對應(yīng)的值將所述待處理鍵值插入到所述目標(biāo)節(jié)點中。

可選的，所述根據(jù)所述待處理鍵值中的關(guān)鍵字對應(yīng)的值將所述待處理鍵值插入到所述目標(biāo)節(jié)點中，包括：

在所述目標(biāo)節(jié)點中，將所述待處理鍵值中的關(guān)鍵字對應(yīng)的值與所述目標(biāo)節(jié)點中目標(biāo)關(guān)鍵字對應(yīng)的值按照從小到大的順序排列，所述目標(biāo)關(guān)鍵字與所述待處理鍵值中的關(guān)鍵字相同。

可選的，所述目標(biāo)關(guān)鍵字包括多個，在所述目標(biāo)節(jié)點中，按照所述多個目標(biāo)關(guān)鍵字分別對應(yīng)的值從小到大的順序排列所述多個目標(biāo)關(guān)鍵字，所述將所述待處理鍵值中的關(guān)鍵字對應(yīng)的值與所述目標(biāo)節(jié)點中目標(biāo)關(guān)鍵字對應(yīng)的值按照從小到大的順序排列，包括：

將所述待處理鍵值插入到所述多個目標(biāo)關(guān)鍵字中任意位置；

分別判斷所述待處理鍵值中的關(guān)鍵字對應(yīng)的值與相鄰的兩個目標(biāo)關(guān)鍵字對應(yīng)的值是否滿足從小到大的順序要求；

若不滿足，則將所述待處理鍵值中的關(guān)鍵字與不滿足順序要求的目標(biāo)關(guān)鍵字交換順序，重新執(zhí)行所述分別判斷所述待處理鍵值中的關(guān)鍵字對應(yīng)的值與相鄰的兩個目標(biāo)關(guān)鍵字對應(yīng)的值是否滿足從小到大的順序要求的步驟。

可選的，所述方法還包括：

獲取待查詢關(guān)鍵字；