技术摘要：
本申请涉及B 树操作方法及存储设备，其中，存储设备包括：CPU和B 树操作装置；CPU从操作B 树的命令中提取关键字，并用提取的关键字操作B 树操作装置对B 树进行搜索；B 树操作装置将搜索结果提供给CPU。本申请用硬件电路来协助软件完成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。 根据本申请的第一方面的第一存储设备，提供了根据本申请第一方面的第二存储 3 CN 111581440 A 说　明　书 2/15 页 设备，其中，B 树操作装置包括：一个或多个搜索单元；搜索单元根据接收的关键字在B 树 中寻找被命中的节点。 根据本申请的第一方面的第一或第二存储设备，提供了根据本申请第一方面的第 三存储设备，还包括存储器，存储器存储一个或多个B 树。 根据本申请的第一方面的第二或第三存储设备，提供了根据本申请第一方面的第 四存储设备，其中，搜索单元将提取的关键字与B 树的节点的各个关键字进行比较，以搜索 被命中的节点。 根据本申请的第一方面的第一至第四存储设备之一，提供了根据本申请第一方面 的第五存储设备，其中，若操作B 树的命令是搜索命令，CPU则根据搜索结果得到命令处理 结果，以将命令处理结果提供给发出操作B 树的命令的主机。 根据本申请的第一方面的第一至第四存储设备之一，提供了根据本申请第一方面 的第六存储设备，若操作B 树的命令是插入命令或删除命令，CPU则根据操作B 树的命令和 搜索结果，更新B 树。 根据本申请的第一方面的第六存储设备，提供了根据本申请第一方面的第七存储 设备，其中，若操作B 树的命令是插入命令或删除命令，则搜索结果指示待插入或删除的节 点，或待插入或删除的节点及其关键字。 根据本申请的第一方面的第六或第七存储设备，提供了根据本申请第一方面的第 八存储设备，其中，若操作B 树的命令是插入命令，并且搜索结果指示了被命中的节点的被 命中的关键字，则CPU将被命中的关键字对应的值更新为插入命令所指示的值。 根据本申请的第一方面的第六或第七存储设备，提供了根据本申请第一方面的第 九存储设备，其中，若操作B 树的命令是插入命令，搜索结果指示了命中节点且未命中关键 字，则CPU向被命中的节点中添加插入命令所指示的关键字或关键字连同对应的值。 根据本申请的第一方面的第九存储设备，提供了根据本申请第一方面的第十存储 设备，其中，若被命中的节点所包含的关键字数量不小于阈值，则CPU将被命中的节点分裂 为两个节点，将插入命令所指示的关键字或关键字连同对应的值添加两个节点之一。 根据本申请的第一方面的第十存储设备，提供了根据本申请第一方面的第十一存 储设备，其中，插入命令所指示的关键字依据其值在被命中的节点中排序的位置被添加至 分裂后的两个节点之一。 根据本申请的第一方面的第十或第十一存储设备，提供了根据本申请第一方面的 第十二存储设备，其中，响应于被命中的节点发生节点分裂，向分裂后的两个节点的共同父 节点添加索引了分裂的新节点的关键字。 根据本申请的第一方面的第十二存储设备，提供了根据本申请第一方面的第十三 存储设备，其中，响应于向父节点添加了索引分裂的新节点的关键字，CPU向发出操作B 树 的主机指示插入命令处理完成。 根据本申请的第一方面的第十二存储设备，提供了根据本申请第一方面的第十四 存储设备，其中，若被命中的节点或分裂后的两个节点的共同父节点是根节点，并且被命中 的节点或分裂后的两个节点的共同父节点所包含的关键字数量不小于阈值，则CPU向发出 操作B 树的主机指示插入命令处理失败。 根据本申请的第一方面的第六或第七存储设备，提供了根据本申请第一方面的第 4 CN 111581440 A 说　明　书 3/15 页 十五存储设备，其中，若操作B 树的命令是删除命令，搜索结果指示了被命中的节点的被命 中的关键字，则CPU从被命中的节点中删除被命中的关键字。 根据本申请的第一方面的第十五存储设备，提供了根据本申请第一方面的第十六 存储设备，其中，响应于被命中的节点中删除被命中的关键字，CPU向发出操作B 树的命令 的主机指示删除命令处理完成。 根据本申请的第一方面的第十五或第十六存储设备，提供了根据本申请第一方面 的第十七存储设备，其中，若被命中的节点的关键字数量不大于第一阈值，并且被命中的节 点与其右兄弟节点的关键字之和大于B 树的阶数，CPU则将右兄弟节点的排序最前的关键 字搬移到被命中的节点，从被命中的节点中删除被命中的关键字。 根据本申请的第一方面的第十七存储设备，提供了根据本申请第一方面的第十八 存储设备，其中，响应于将右兄弟节点的排序最前的关键字搬移到被命中的节点，更新右兄 弟节点的父节点中索引右兄弟节点的关键字。 根据本申请的第一方面的第十八存储设备，提供了根据本申请第一方面的第十九 存储设备，其中，响应于更新右兄弟节点的父节点中索引右兄弟节点的关键字，CPU向发出 操作B 树的命令的主机指示删除命令处理完成。 根据本申请的第一方面的第十七至第十九存储设备之一，提供了根据本申请第一 方面的第二十存储设备，其中，若被命中的节点与其右兄弟节点的关键字之和不大于B 树 的阶数，并且被命中的节点与其左兄弟节点的关键字数量之和大于B 树的阶数，则CPU将左 兄弟节点的排序最后的关键字搬移到被命中的节点，作为被命中的节点排序最前的关键 字，从被命中的节点中删除被命中的关键字。 根据本申请的第一方面的第二十存储设备，提供了根据本申请第一方面的第二十 一存储设备，其中，响应于将左兄弟节点的排序最后的关键字搬移到被命中的节点，作为被 命中的节点排序最前的关键字，更新被命中节点的父节点中索引被命中节点的关键字。 根据本申请的第一方面的第二十存储设备，提供了根据本申请第一方面的第二十 二存储设备，其中，响应于从被命中的节点中删除被命中的关键字以及更新被命中的节点 的父节点中索引被命中的节点的关键字，CPU向发出操作B 树的命令的主机指示删除命令 处理完成。 根据本申请的第一方面的第二十至第二十二存储设备之一，提供了根据本申请第 一方面的第二十三存储设备，其中，若被命中的节点与其左兄弟节点的关键字数量之和不 大于B 树的阶数，则合并被命中的节点与其兄弟节点之一。 根据本申请的第一方面的第二十三存储设备，提供了根据本申请第一方面的第二 十四存储设备，其中，若合并被命中的节点与其左兄弟节点，则被删除节点的父节点作为新 的被命中的节点，索引了被删除节点的关键字作为新的被命中的关键字，从新的被命中的 节点中删除新的被命中的关键字。 根据本申请的第一方面的第二十四存储设备，提供了根据本申请第一方面的第二 十五存储设备，其中，响应于从根节点中删除索引了被删除节点的关键字，CPU向发出操作B 树的命令的主机指示删除命令处理完成。 根据本申请的第一方面的第六或第七存储设备，提供了根据本申请第一方面的第 二十六存储设备，其中，若操作B 树的命令是删除命令，并且搜索结果指示B 树中不包括被 5 CN 111581440 A 说　明　书 4/15 页 搜索的关键字，则CPU向发出操作B 树的命令的主机指示删除命令处理失败。 根据本申请的第二方面，提供了根据本申请第二方面的第一B 树的操作方法，包 括如下步骤：从操作B 树的命令中提取关键字，并用提取的关键字操作B 树操作装置对B 树进行搜索；并且接收B 树操作装置提供的搜索结果。 根据本申请的第二方面的第一B 树操作方法，提供了根据本申请第二方面的第二 B 树操作方法，其中，根据提取的关键字在B 树中寻找被命中的节点。 根据本申请的第二方面的第一或第二B 树操作方法，提供了根据本申请第二方面 的第三B 树操作方法，其中，将提取的关键字与B 树的的节点的各个关键字进行比较，以搜 索被命中的节点。 根据本申请的第二方面的第三B 树操作方法，提供了根据本申请第二方面的第四 B 树操作方法，其中，若提取的关键字与B 树的的关键字比较命中的关键字是非叶节点，则 根据被命中的关键字获取下一节点的关键字；若命中的关键字是叶节点，则根据被命中的 关键字获得搜索结果。 根据本申请的第二方面的第一至第四B 树操作方法之一，提供了根据本申请第二 方面的第五B 树操作方法，其中，若操作B 树的命令是搜索命令，则根据搜索结果得到命令 处理结果，以将命令处理结果提供给发出操作B 树的命令的主机。 根据本申请的第二方面的第五B 树操作方法，提供了根据本申请第二方面的第六 B 树操作方法，其中，根据搜索结果指示搜索命令要获取数据的指针或地址获取数据，以得 到命令处理结果。 根据本申请的第二方面的第一至第六B 树操作方法之一，提供了根据本申请第二 方面的第七B 树操作方法，其中，若操作B 树的命令是插入命令或删除命令，则根据操作B 树的命令和搜索结果，更新B 树。 根据本申请的第二方面的第七B 树操作方法，提供了根据本申请第二方面的第八 B 树操作方法，其中，若操作B 树的命令是插入命令或删除命令，则搜索结果指示待插入或 删除的节点，或插入或删除的节点及其关键字。 根据本申请的第二方面的第七或第八B 树操作方法，提供了根据本申请第二方面 的第九B 树操作方法，其中，若操作B 树的命令是插入命令，并且搜索结果指示了被命中的 节点的被命中的关键字，则将被命中的关键字对应的值更新为插入命令所指示的值。 根据本申请的第二方面的第七或第八B 树操作方法，提供了根据本申请第二方面 的第十B 树操作方法，若操作B 树的命令是插入命令，搜索结果指示了命中节点且未命中 关键字，则向被命中的节点中添加插入命令所指示的关键字或关键字连同对应的值。 根据本申请的第二方面的第十B 树操作方法，提供了根据本申请第二方面的第十 一B 树操作方法，其中，若被命中的节点所包含的关键字数量不小于阈值，则将被命中的节 点分裂为两个节点，将插入命令所指示的关键字或关键字连同对应的值添加两个节点之 一。 根据本申请的第二方面的第十一B 树操作方法，提供了根据本申请第二方面的第 十二B 树操作方法，其中，插入命令所指示的关键字依据其值在被命中的节点中排序的位 置被添加至分裂后的两个节点之一。 根据本申请的第二方面的第十一或第十二B 树操作方法，提供了根据本申请第二 6 CN 111581440 A 说　明　书 5/15 页 方面的第十三B 树操作方法，其中，响应于被命中的节点发生节点分裂，向分裂后的两个节 点的共同父节点添加索引了分裂的新节点的关键字。 根据本申请的第二方面的第十三B 树操作方法，提供了根据本申请第二方面的第 十四B 树操作方法，其中，响应于向父节点添加了索引分裂的新节点的关键字，向发出操作 B 树的主机指示插入命令处理完成。 根据本申请的第二方面的第十三B 树操作方法，提供了根据本申请第二方面的第 十五B 树操作方法，其中，若被命中的节点或分裂后的两个节点的共同父节点是根节点，并 且被命中的节点或分裂后的两个节点的共同父节点所包含的关键字数量不小于阈值，则向 发出操作B 树的主机指示插入命令处理失败。 根据本申请的第二方面的第七或第八B 树操作方法，提供了根据本申请第二方面 的第十六B 树操作方法，其中，若操作B 树的命令是删除命令，搜索结果指示了被命中节点 的被命中的关键字，则从被命中的节点中删除被命中的关键字。 根据本申请的第二方面的第十六B 树操作方法，提供了根据本申请第二方面的第 十七B 树操作方法，其中，响应于被命中的节点中删除被命中的关键字，向发出操作B 树的 命令的主机指示删除命令处理完成。 根据本申请的第二方面的第十六或第十七B 树操作方法，提供了根据本申请第二 方面的第十八B 树操作方法，其中，若被命中的节点的关键字数量不大于第一阈值，并且被 命中的节点与其右兄弟节点的关键字之和大于B 树的阶数，则将右兄弟节点的排序最前的 关键字搬移到被命中的节点，从被命中的节点中删除被命中的关键字。 根据本申请的第二方面的第十八B 树操作方法，提供了根据本申请第二方面的第 十九B 树操作方法，其中，响应于将右兄弟节点的排序最前的关键字搬移到被命中的节点， 更新右兄弟节点的父节点中索引右兄弟节点的关键字。 根据本申请的第二方面的第十九B 树操作方法，提供了根据本申请第二方面的第 二十B 树操作方法，其中，响应于更新右兄弟节点的父节点中索引右兄弟节点的关键字，向 发出操作B 树的命令的主机指示删除命令处理完成。 根据本申请的第二方面的第十八至第二十B 树操作方法之一，提供了根据本申请 第二方面的第二十一B 树操作方法，其中，若被命中的节点与其右兄弟节点的关键字之和 不大于B 树的阶数，并且被命中的节点与其左兄弟节点的关键字数量之和大于B 树的阶 数，则将左兄弟节点的排序最后的关键字搬移到被命中的节点，为被命中的节点排序最前 的关键字，从被命中的节点中删除被命中的关键字。 根据本申请的第二方面的第二十一B 树操作方法，提供了根据本申请第二方面的 第二十二B 树操作方法，其中，响应于将左兄弟节点的排序最后的关键字搬移到被命中的 节点，作为被命中的节点排序最前的关键字，更新被命中节点的父节点中索引被命中节点 的的关键字。 根据本申请的第二方面的第二十一B 树操作方法，提供了根据本申请第二方面的 第二十三B 树操作方法，响应于从被命中的节点中删除被命中的关键字，以及更新被命中 的节点的父节点中索引被命中的节点的关键字，向发出操作B 树的命令的主机指示删除命 令处理完成。 根据本申请的第二方面的第二十一至第二十三B 树操作方法之一，提供了根据本 7 CN 111581440 A 说　明　书 6/15 页 申请第二方面的第二十四B 树操作方法，其中，若被命中的节点与其左兄弟节点的关键字 数量之和不大于B 树的阶数，则合并被命中的节点与其兄弟节点之一。 根据本申请的第二方面的第二十四B 树操作方法，提供了根据本申请第二方面的 第二十五B 树操作方法，若合并被命中的节点与其左兄弟节点，则被删除节点的父节点作 为新的被命中的节点，索引了被删除节点的关键字作为新的被命中的关键字，从新的被命 中的节点中删除新的被命中的关键字。 根据本申请的第二方面的第二十五B 树操作方法，提供了根据本申请第二方面的 第二十六B 树操作方法，其中，响应于从根节点中删除索引了被删除节点的关键字，向发出 操作B 树的命令的主机指示删除命令处理完成。 根据本申请的第二方面的第七或第八B 树操作方法，提供了根据本申请第二方面 的第二十七B 树操作方法，其中，若操作B 树的命令是删除命令，并且搜索结果指示B 树中 不包括被搜索的关键字，则向发出操作B 树的命令的主机指示删除命令处理失败。 附图说明 为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现 有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本 申请中记载的一些实施例，对于本领域普通技术人员来讲，还可以根据这些附图获得其他 的附图。 图1展示了B 树； 图2展示了根据本申请实施例的B 树操作装置的框图； 图3A展示了使用根据本申请实施例的B 树操作装置操作B 树的示意图； 图3B展示了使用根据本申请实施例的B 树操作装置操作B 树的流程图； 图4是根据本申请实施例的B 树操作装置操作多个B 树的流程图； 图5A展示了根据本申请实施例的B 树操作装置框图； 图5B展示了根据本申请又一实施例的B 树操作装置框图； 图5C展示了根据图5A或图5B的实施例处理搜索命令的流程图； 图6A展示了根据本申请再一实施例的B 树操作装置框图； 图6B展示了根据图6A的实施例处理插入命令的流程图； 图7A展示了根据本申请依然再一实施例的B 树操作装置框图； 图7B展示了根据图7A的实施例处理删除命令的流程图； 图8展示了根据本申请又一实施例的B 树操作装置框图； 图9展示了根据图8的实施例的流程图； 图10是根据图8的实施例的处理B 树插入命令的流程图； 图11是根据图8的实施例的处理B 树删除命令的流程图。