[發明專利]一種B+樹節點的批量插入和刪除方法及裝置

有效

• 申請號: 201811231305.8
• 申請日: 2018-10-22
• 公開（公告）號: CN109522271B
• 公開（公告）日: 2021-05-18
• 發明（設計）人: 劉丹;鄒虎;何孝金
• 申請（專利權）人: 鄭州云海信息技術有限公司
• 主分類號: G06F16/13
• 分類號: G06F16/13
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 王寶筠

本申請公開一種B+樹節點的批量插入和刪除方法及裝置，該方法包括：從內存B+樹節點中抽取第一key?value，從磁盤B+樹節點中抽取第二key?value，第一key?value為內存B+樹中最小的key?value，第二key?value為磁盤B+樹中待插入或刪除的最小的key?value，再按序將內存B+樹中的key?value組成的有序集合與磁盤B+樹中第二key?value后面的所有key?value組成的有序集合逐個進行比較，再根據比較結果和內存B+樹節點中所有key?value的操作類型，將內存B+樹與磁盤B+樹合并，生成新的磁盤B+樹。可見，本申請是通過從內存B+樹和磁盤B+樹抽取最小的節點生成新的磁盤B+樹，相比較將內存元數據先落盤后再合并的方法，本方法可以提高元數據訪問的讀性能，避免大量插入和刪除節點帶來的大量讀磁盤操作和刪除結點時頻繁的變換，節省內存開支。

技術領域

本申請涉及計算機技術領域，具體涉及一種B+樹節點的批量插入和刪除方法及裝置。

背景技術

隨著移動互聯網、社交網絡、電子商務的飛速發展，人類在生產和生活中產生的數據呈現指數型增長，導致數據處理量也與日俱增，同時需要的存儲容量也越來越大。

由此，在云計算時代，海量數據的存儲需要文件系統的支持，并且，文件系統的元數據性能已成為影響文件訪問性能的關鍵。B+樹是為磁盤或其他直接存取輔助設備而設計的一種平衡查找樹，通常用于數據庫和操作系統的文件系統中。比如NTFS、ReiserFS、NSS、XFS、JFS、ReFS以及BFS等文件系統都在使用B+樹作為元數據索引。B+樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間復雜度。B+樹元素的插入方式為自底向上插入。并且，在需要進行內存和磁盤換入換出時，通常都是需要批量操作來提升元數據性能，但如果按照傳統的B+樹的插入和刪除做法不僅會涉及大量的磁盤訪問還會占用大量的內存空間。

因此，如何利用更先進的B+樹節點的批量插入和刪除方式取代傳統的批量插入和刪除方式，來避免大量插入和刪除節點帶來的大量讀磁盤操作和刪除結點時頻繁的變換，以節省內存開支，已成為亟待解決的問題。

發明內容

為解決上述問題，本申請提供了一種B+樹節點的批量插入和刪除方法及裝置，具體技術方案如下：

第一方面，本申請提供了一種B+樹節點的批量插入和刪除方法，所述方法包括：

從內存B+樹節點中抽取第一key-value，以及從磁盤B+樹節點中抽取第二key-value，所述第一key-value為所述內存B+樹中最小的key-value，所述第二key-value為所述磁盤B+樹中待插入或刪除的最小的key-value；

從所述第一key-value和所述第二key-value所在位置，按序將所述內存B+樹中所有的key-value組成的有序集合與所述磁盤B+樹中第二key-value后面的所有待插入或刪除的key-value組成的有序集合逐個進行比較，得到比較結果；

根據所述比較結果，以及所述內存B+樹節點中所有key-value的操作類型，將所述內存B+樹與所述磁盤B+樹進行合并，生成一棵新的磁盤B+樹，以實現B+樹節點的批量插入和刪除。

在一種可選的實現方式中，所述從內存B+樹節點中抽取第一key-value，以及從磁盤B+樹節點中抽取第二key-value，包括：

將所述內存B+樹最左側的葉子節點設置為其游標位置，所述游標位置的游標為0；

從所述內存B+樹中游標對應的節點中抽取出所述節點中最小的key-value，作為所述第一key-value；

根據所述內存B+樹中游標指向的key-value，查詢出所述磁盤B+樹中對應的key-value及其所屬節點，并將所述key-value的位置設置為所述磁盤B+樹的游標位置；