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

在審

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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