[發(fā)明專利]區(qū)塊鏈中的MPT樹批量更新方法、電子設(shè)備及存儲介質(zhì)

有效

• 申請?zhí)枺?/td>: 202211611522.6
• 申請日: 2022-12-15
• 公開（公告）號: CN115617818B
• 公開（公告）日: 2023-03-24
• 發(fā)明（設(shè)計）人: 鄒小川;姚子丹;秦明;尹立東
• 申請（專利權(quán)）人: 深圳市邁科龍電子有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F16/25;G06F16/27
• 代理公司: 深圳市恒程創(chuàng)新知識產(chǎn)權(quán)代理有限公司 44542
• 代理人: 鐘永翠

本申請公開了一種區(qū)塊鏈中的MPT樹批量更新方法、電子設(shè)備及存儲介質(zhì)，所述區(qū)塊鏈中的MPT樹批量更新方法包括：獲取待更新鍵值數(shù)據(jù)，將所述待更新鍵值數(shù)據(jù)轉(zhuǎn)換成字典樹；通過遍歷匹配所述字典樹中各節(jié)點與原MPT樹中各子節(jié)點，將所述字典樹中的鍵值數(shù)據(jù)插入所述原MPT樹中，以將所述原MPT樹中的各子節(jié)點進(jìn)行更新；將所述原MPT樹中更新過的子節(jié)點進(jìn)行哈希運算，得到更新后的MPT樹。本申請解決了MPT樹中數(shù)據(jù)批量更新效率低的技術(shù)問題。

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

本申請涉及區(qū)塊鏈技術(shù)領(lǐng)域，尤其涉及一種區(qū)塊鏈中的MPT樹批量更新方法、電子設(shè)備及存儲介質(zhì)。

背景技術(shù)

隨著區(qū)塊鏈技術(shù)的不斷發(fā)展，以太坊中應(yīng)用到一種重要的數(shù)據(jù)結(jié)構(gòu)MPT（MerklePatricia Tree，梅克爾帕特里夏樹），MPT樹是一種經(jīng)過改良的、融合了默克爾樹和字典樹兩種樹結(jié)構(gòu)優(yōu)點的數(shù)據(jù)結(jié)構(gòu)。當(dāng)前區(qū)塊鏈中的MPT樹中的各字節(jié)點中有一個flag（標(biāo)志）字段，所述字段用于保存各節(jié)點中的用戶數(shù)據(jù)通過默克樹路徑生成的哈希值。當(dāng)所述MPT樹中的各子節(jié)點中的用戶數(shù)據(jù)發(fā)生更新或者插入新的用戶數(shù)據(jù)時，每插入一個數(shù)據(jù)便需要重新計算并更新幾乎整棵默克樹的哈希值。尤其是在需要插入大批量數(shù)據(jù)時，哈希計算次數(shù)更會線性增長，其中計算過程耗時較長，更新實時性低，因此導(dǎo)致MPT樹中數(shù)據(jù)批量更新效率較低。

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

本申請的主要目的在于提供一種區(qū)塊鏈中的MPT樹批量更新方法、電子設(shè)備及存儲介質(zhì)，旨在解決MPT樹中數(shù)據(jù)批量更新效率低的技術(shù)問題。

為實現(xiàn)上述目的，本申請?zhí)峁┮环N區(qū)塊鏈中的MPT樹批量更新方法，所述區(qū)塊鏈中的MPT樹批量更新方法包括：

獲取待更新鍵值數(shù)據(jù)，將所述待更新鍵值數(shù)據(jù)轉(zhuǎn)換成字典樹；

通過遍歷匹配所述字典樹中各節(jié)點與原MPT樹中各子節(jié)點，將所述字典樹中的鍵值數(shù)據(jù)插入所述原MPT樹中，以將所述原MPT樹中的各子節(jié)點進(jìn)行更新；

將所述原MPT樹中更新過的子節(jié)點進(jìn)行哈希運算，得到更新后的MPT樹。

可選地，所述通過遍歷匹配所述字典樹中各節(jié)點與原MPT樹中各子節(jié)點，將所述字典樹中的鍵值數(shù)據(jù)插入所述原MPT樹中的步驟包括：

若所述原MPT樹為空，則將所述字典樹轉(zhuǎn)換成MPT樹；

若所述原MPT樹不為空，則將所述字典樹中各節(jié)點與所述原MPT樹中各子節(jié)點進(jìn)行匹配，以更新所述原MPT樹中各子節(jié)點。

可選地，所述MPT樹中至少包括分支節(jié)點、擴展節(jié)點以及葉子節(jié)點中的一種，所述將所述字典樹轉(zhuǎn)換成MPT樹的步驟包括：

若所述字典樹中的節(jié)點包括不少于兩個子節(jié)點，則將所述節(jié)點轉(zhuǎn)換成分支節(jié)點；

若所述字典樹中的節(jié)點僅包括一個子節(jié)點且所述子節(jié)點不為葉子節(jié)點，則將所述節(jié)點與對應(yīng)的子節(jié)點共同轉(zhuǎn)換成更新擴展節(jié)點，其中，所述更新擴展節(jié)點的鍵值由所述節(jié)點的鍵值與所述子節(jié)點的鍵值拼接得到；

其中，若存在連續(xù)的節(jié)點均僅包括一個子節(jié)點，則將各所述節(jié)點以及所述子節(jié)點共同轉(zhuǎn)換成所述更新擴展節(jié)點；

若所述字典樹中的節(jié)點僅包括一個子節(jié)點，且所述子節(jié)點為葉子節(jié)點，則將所述節(jié)點與所述葉子節(jié)點共同轉(zhuǎn)換成更新葉子節(jié)點，其中，所述更新葉子節(jié)點的鍵值由所述節(jié)點的鍵值與所述子節(jié)點的鍵值拼接得到；

其中，若存在連續(xù)的節(jié)點均僅包括一個子節(jié)點，則將各所述節(jié)點以及所述子節(jié)點共同轉(zhuǎn)換成所述更新葉子節(jié)點。

可選地，所述將所述字典樹中各節(jié)點與所述原MPT樹中各子節(jié)點進(jìn)行匹配，以更新所述原MPT樹中各子節(jié)點的步驟包括：

當(dāng)所述字典樹中的節(jié)點的鍵值匹配到所述原MPT樹的分支節(jié)點時，且所述分支節(jié)點的子節(jié)點為空時，將所述字典樹的節(jié)點下的所有子節(jié)點轉(zhuǎn)換成更新MPT樹并插入到所述分支節(jié)點下；