[發明專利]多B+樹操作裝置及其方法

在審

• 申請號: 202110551387.X
• 申請日: 2019-03-15
• 公開（公告）號: CN113094375A
• 公開（公告）日: 2021-07-09
• 發明（設計）人: 周鵬飛;介百瑞;萬義才;孫唐
• 申請（專利權）人: 北京憶芯科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2453
• 代理公司: 北京卓特專利代理事務所(普通合伙) 11572
• 代理人: 段旺

本申請涉及信息處理技術，特別地，涉及多B+樹操作裝置及其方法，其中，B+樹操作裝置，包括：命令接口、存儲器和多個搜索單元；存儲器存儲多個B+樹；命令接口根據待處理命令要訪問的B+樹，將待處理命令添加到同要訪問的B+樹對應的搜索單元關聯的命令隊列；多個搜索單元根據每個搜索單元關聯的命令隊列中待處理命令指示的關鍵字并行搜索存儲器中存儲的多個B+樹，并將搜索結果提供給命令接口。本申請用硬件電路來實現B+樹操作，利用多棵B+樹來分別存儲索引，實現高效處理各B+樹的操作。

技術領域

本申請涉及信息處理技術，特別地，涉及利用集成電路硬件提供多B+樹操作裝置以及使用該裝置操作多棵B+樹的方法。

背景技術

B+樹是一種數據結構，在文件系統、數據庫等常使用B+樹存儲索引。圖1展示了B+樹。B+樹包括一個根節點、多個中間節點以及多個葉節點。節點120是根節點。節點130、節點132與節點134是中間節點，中間節點是既非根節點也非葉節點的節點。節點(140、142、144……150、152、154)是葉節點。

B+樹的中間節點包括不超過m個元素，將m稱為B+樹的階。B+樹的根節點與中間節點的每個元素，記錄了關鍵字(Key)與指向下級節點的指針。例如，節點130包括3個元素，第一個元素的關鍵字為5，其指針指向節點140，第二個元素的關鍵字為10，其指針指向節點142，第三個元素的關鍵字為20，其指針指向節點144。節點的各個元素按關鍵字排序。

在一些實施方式中，根節點與中間節點的每個元素記錄了指向下級節點的指針，但并非每個元素都包括關鍵字，而是根節點與中間節點包括的關鍵字數量比其包括的元素少一個。例如，在節點120中，可以不包括關鍵字“K:5”，以及在搜索節點120時，對于小于關鍵字“K：28”的關鍵字，在搜索結果中指示下級節點130，而對于不小于關鍵字“K：28”且小于關鍵字“K：65”的關鍵字，在搜索結果中指示下級節點134。

B+樹的葉節點包括不超過m個元素。葉節點的每個元素記錄了關鍵字(Key)與同關鍵字對應的值(Value)。葉節點的各個元素按關鍵字排序。從而B+樹的所有關鍵字都在葉節點中有記錄，并且只有從葉節點中才能獲得同關鍵字對應的值。

現有技術中，由軟件在內存中構建并操作B+樹，采用例如二分法在B+樹中查找關鍵字。二分法是軟件所能獲得的性能幾乎最好的查找算法，但在大數據時代，數據項數量的增長，使得軟件操作B+樹的查找算法的性能以不能滿足要求。

發明內容

需要更快的實現B+樹操作。需要用硬件電路來實現B+樹操作。以及一些信息處理設備中，利用多棵B+樹來分別存儲索引。例如，每個B+樹存儲各自的文件系統的索引。這些文件系統被并發或獨立地訪問。B+樹操作裝置需要能高效處理各B+樹的操作。

根據本申請的第一方面，提供了根據本申請第一方面的第一B+樹操作方法，包括如下步驟：根據待處理命令要訪問的B+樹，將待處理命令提供給同所述B+樹對應的搜索單元；搜索單元根據待處理命令指示的關鍵字搜索待訪問的B+樹，并得到搜索結果。

根據本申請的第一方面的第一B+樹操作方法，提供了根據本申請第一方面的第二B+樹操作方法，其中，若待處理命令是搜索命令，則搜索單元提供的搜索結果為命令的處理結果。

根據本申請的第一方面的第一或第二B+樹操作方法，提供了根據本申請第一方面的第三B+樹操作方法，其中，若待處理命令是插入命令或刪除命令，則根據搜索結果對所述待處理命令進行再次處理，以得到命令的處理結果。

根據本申請的第一方面的第三B+樹操作方法，提供了根據本申請第一方面的第四B+樹操作方法，其中，若待處理命令是插入命令，將插入命令指定的關鍵字或關鍵字連同對應的值添加到搜索結果指示的節點，以對待處理命令進行再次處理。