[發明專利]B+樹操作裝置

在審

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

本申請涉及B+樹操作裝置，其中，所述B+樹操作裝置同CPU耦合，所述CPU從操作B+樹的命令中提取關鍵字，并用提取的關鍵字操作所述B+樹操作裝置對B+樹進行搜索；所述B+樹操作裝置將搜索結果提供給CPU；所述B+樹操作裝置包括：一個或多個搜索單元；搜索單元根據接收的關鍵字在存儲器中存儲的B+樹中尋找被命中的節點。

技術領域

本申請涉及信息處理技術，特別地，涉及在SoC中利用軟件與硬件結合方式操作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+樹的每個非根節點的元素數量不少于m/2。

B+樹的非根節點的各個元素按關鍵字排序，排序最前的元素在例如最左邊，并且該元素的關鍵字存在于該節點的父節點中。

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

發明內容

需要更快的實現B+樹操作。需要用硬件電路來協助軟件完成B+樹操作。將B+樹操作的搜索過程由硬件完成，而由軟件控制B+樹搜索硬件，并完成B+樹的完整操作。從而有效降低執行軟件的CPU的任務負載，并提高B+樹操作的執行效率。

根據本申請的第一方面，提供了根據本申請第一方面的第一存儲設備，包括：CPU和B+樹操作裝置；CPU從操作B+樹的命令中提取關鍵字，并用提取的關鍵字操作B+樹操作裝置對B+樹進行搜索；B+樹操作裝置將搜索結果提供給CPU。

根據本申請的第一方面的第一存儲設備，提供了根據本申請第一方面的第二存儲設備，其中，B+樹操作裝置包括：一個或多個搜索單元；搜索單元根據接收的關鍵字在B+樹中尋找被命中的節點。

根據本申請的第一方面的第一或第二存儲設備，提供了根據本申請第一方面的第三存儲設備，還包括存儲器，存儲器存儲一個或多個B+樹。

根據本申請的第一方面的第二或第三存儲設備，提供了根據本申請第一方面的第四存儲設備，其中，搜索單元將提取的關鍵字與B+樹的節點的各個關鍵字進行比較，以搜索被命中的節點。

根據本申請的第一方面的第一至第四存儲設備之一，提供了根據本申請第一方面的第五存儲設備，其中，若操作B+樹的命令是搜索命令，CPU則根據搜索結果得到命令處理結果，以將命令處理結果提供給發出操作B+樹的命令的主機。