[發(fā)明專利]B+樹操作裝置

在審

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

1.一種B+樹操作裝置，所述B+樹操作裝置同CPU耦合，所述CPU從操作B+樹的命令中提取關鍵字，并用提取的關鍵字操作所述B+樹操作裝置對B+樹進行搜索；所述B+樹操作裝置將搜索結果提供給CPU；

所述B+樹操作裝置包括：一個或多個搜索單元；搜索單元根據(jù)接收的關鍵字在存儲器中存儲的B+樹中尋找被命中的節(jié)點。

2.根據(jù)權利要求1所述的B+樹操作裝置，其中，若操作B+樹的命令是插入命令或刪除命令，CPU則根據(jù)操作B+樹的命令和搜索結果，更新B+樹；

其中，所述搜索結果指示待插入或刪除的節(jié)點，或所述搜索結果指示待插入或刪除的節(jié)點及其關鍵字。

3.根據(jù)權利要求2所述的B+樹操作裝置，其中，若操作B+樹的命令是插入命令，搜索結果指示了命中節(jié)點且未命中關鍵字，則CPU向被命中的節(jié)點中添加插入命令所指示的關鍵字或關鍵字連同對應的值；或者，

若操作B+樹的命令是插入命令，搜索結果指示了命中節(jié)點且未命中關鍵字，則CPU向被命中的節(jié)點中添加插入命令所指示的關鍵字或關鍵字連同對應的值。

4.根據(jù)權利要求3所述的B+樹操作裝置，其中，若被命中的節(jié)點所包含的關鍵字數(shù)量不小于閾值，則CPU將被命中的節(jié)點分裂為兩個節(jié)點，將插入命令所指示的關鍵字或關鍵字連同對應的值添加兩個節(jié)點之一。

5.根據(jù)權利要求4所述的B+樹操作裝置，其中，響應于被命中的節(jié)點發(fā)生節(jié)點分裂，向分裂后的兩個節(jié)點的共同父節(jié)點添加索引了分裂的新節(jié)點的關鍵字。

6.根據(jù)權利要求2所述的B+樹操作裝置，其中，若操作B+樹的命令是刪除命令，搜索結果指示了被命中的節(jié)點的被命中的關鍵字，則CPU從被命中的節(jié)點中刪除被命中的關鍵字。

7.根據(jù)權利要求要求6所述的B+樹操作裝置，其中，若被命中的節(jié)點的關鍵字數(shù)量不大于第一閾值，并且被命中的節(jié)點與其右兄弟節(jié)點的關鍵字之和大于B+樹的階數(shù)，CPU則將右兄弟節(jié)點的排序最前的關鍵字搬移到被命中的節(jié)點，從被命中的節(jié)點中刪除被命中的關鍵字。

8.根據(jù)權利要求7所述的B+樹操作裝置，其中，響應于將右兄弟節(jié)點的排序最前的關鍵字搬移到被命中的節(jié)點，更新右兄弟節(jié)點的父節(jié)點中索引右兄弟節(jié)點的關鍵字。

9.根據(jù)權利要求7或8所述的B+樹操作裝置，其中，若被命中的節(jié)點與其右兄弟節(jié)點的關鍵字之和不大于B+樹的階數(shù)，并且被命中的節(jié)點與其左兄弟節(jié)點的關鍵字數(shù)量之和大于B+樹的階數(shù)，則CPU將左兄弟節(jié)點的排序最后的關鍵字搬移到被命中的節(jié)點，作為被命中的節(jié)點排序最前的關鍵字，從被命中的節(jié)點中刪除被命中的關鍵字。

10.根據(jù)權利要求9所述的B+樹操作裝置，其中，若被命中的節(jié)點與其左兄弟節(jié)點的關鍵字數(shù)量之和不大于B+樹的階數(shù)，則合并被命中的節(jié)點與其兄弟節(jié)點之一。

11.根據(jù)權利要求10所述的B+樹操作裝置，若合并被命中的節(jié)點與其左兄弟節(jié)點，則被刪除節(jié)點的父節(jié)點作為新的被命中的節(jié)點，索引了被刪除節(jié)點的關鍵字作為新的被命中的關鍵字，從新的被命中的節(jié)點中刪除新的被命中的關鍵字。

12.根據(jù)權利要求6和8-9中任一項所述的B+樹操作裝置，其中，

響應于被命中的節(jié)點中刪除被命中的關鍵字，CPU向發(fā)出操作B+樹的命令的主機指示刪除命令處理完成；或者，

響應于更新右兄弟節(jié)點的父節(jié)點中索引右兄弟節(jié)點的關鍵字，CPU向發(fā)出操作B+樹的命令的主機指示刪除命令處理完成；或者，

響應于從被命中的節(jié)點中刪除被命中的關鍵字以及更新被命中的節(jié)點的父節(jié)點中索引被命中的節(jié)點的關鍵字，CPU向發(fā)出操作B+樹的命令的主機指示刪除命令處理完成；或者，

響應于從根節(jié)點中刪除索引了被刪除節(jié)點的關鍵字，CPU向發(fā)出操作B+樹的命令的主機指示刪除命令處理完成。

13.根據(jù)權利要求5所述的B+樹操作裝置，其中，

響應于向父節(jié)點添加了索引分裂的新節(jié)點的關鍵字，CPU向發(fā)出操作B+樹的主機指示插入命令處理完成；和/或，

若被命中的節(jié)點或分裂后的兩個節(jié)點的共同父節(jié)點是根節(jié)點，并且被命中的節(jié)點或分裂后的兩個節(jié)點的共同父節(jié)點所包含的關鍵字數(shù)量不小于閾值，則CPU向發(fā)出操作B+樹的主機指示插入命令處理失敗。