(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210501500.8 (22)申请日 2022.05.10 (71)申请人 珠海迈科智能科技股份有限公司 地址 519000 广东省珠海市金湾区红旗 镇 永达路66号2厂房 (72)发明人 杨坚　李淼　汪宏　谭龙根　 吴建宏　高杨　 (74)专利代理 机构 广州三环 专利商标代理有限 公司 44202 专利代理师 牛丽霞 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/23(2019.01) (54)发明名称 一种B+树批量 顺序删除的方法及系统 (57)摘要 本发明提供一种B+树批量顺序删除的方法， 包括以下步骤： 将一个B+树分为多个； 定义一个 链表， 将树根节点指针和树的最大值存入所述链 表； 为每个B+树定义一个p_tree_h ead指针， 所述 p_tree_h ead指针用于标记顺序删除后的首个有 效节点的位置； 插入和查询时， 先遍历所述链表 找到要插入的B+树， 依次比较链表中树的最大 值， 比该值小即查询或插入到 该B+树； 删除操作， 从链表中找到第一个节点的p_tree_head指针， 顺序的向后取B+树， 然后指针后移； 直到该p_ tree_head指针对应的键值为该B+树的最大值； 删除整个B+树， 同时删除掉链表中对应的节点。 在批量顺序删除的前提下， 本发 明可以极大的提 升删除操作的效率。 权利要求书1页 说明书3页 附图1页 CN 114969033 A 2022.08.30 CN 114969033 A 1.一种B+树批量 顺序删除的方法， 其特 征在于， 包括以下步骤： S1、 将一个B+树分为多个； S2、 定义一个链表， 将树根节点指针和树的最大值存 入所述链 表； S3、 为每个B+树定义一个p_tree_head指针， 所述p_tree_head指针用于标记顺序删除 后的首个有效节点的位置； S4、 插入和查询时， 先遍历所述链表找到要插入的B+树， 依次比较链表中树的最大值， 比所述链 表中树的最大值小即查询或插 入到该B+树； S5、 删除操作时， 从链表中找到第一个节点的p_tree_head指针， 顺序的向后取B+树， 然 后指针后移， 直到该p_t ree_head指针对应的键值 为该B+树的最大值； S6、 删除整个B+树， 同时删除掉链 表中对应的节点。 2.根据权利 要求1所述的方法， 其特征在于， 所述S1中， 将一个B+树分为多个的方法， 是 根据键大小分。 3.一种B+树批量 顺序删除的系统， 其特 征在于， 包括： B+树拆分单 元， 其用于将一个B+树分为多个； 链表生成单 元， 用于定义一个链表， 将树根节点指针和树的最大值存 入所述链 表； 指针定义单元， 用于为每个B+树定义一个p_tree_head指针， 所述p_tree_head指针用 于标记顺序删除后的首个有效节点的位置； 插入和查询单元， 用于先遍历所述链表找到要插入的B+树， 依次比较链表中树的最大 值， 比链表中树的最大值小即查询或插 入到该B+树； 删除单元， 用于从链表中找到第一个节点的p_tree_head指针， 顺序的向后取B+树， 然 后指针后移， 直到该p_t ree_head指针对应的键值 为该B+树的最大值； 删除单元， 删除整个B+树， 同时删除掉链 表中对应的节点。 4.根据权利要求3所述的系统， 其特征在于， 所述B+树拆分单元， 具体用于将一个B+树 根据键大小分为多个。权　利　要　求　书 1/1 页 2 CN 114969033 A 2一种B+树批量顺序删除的方 法及系统 技术领域 [0001]本发明涉及软件领域， 具体提供一种B+树批量 顺序删除的方法及系统。 背景技术 [0002]B+树是一种树数据结构， 通常用于数据库和操作系统的文件索引系统中。 B+树的 特点是能够保持数据稳定有序， 其插入与删除拥有较稳定的对数时间复杂度。 B+树是一种 平衡查找树， 所有记录节点都是按键值的大小顺序存放在同一层的叶节点中， 各叶节点指 针进行连接。 [0003]现有技术中， B+树删除操作， 一般是针对单个键值， 并没有对节点或者多个节点进 行批量删除的有效方法。 有 些专利提供了批量删除的操作， 是针对磁盘删除效率低， 将B+树 读取到内存中操作后批量修改磁盘的操作。 其缺点是： 先在内存中批量删除， 然后再批量写 入磁盘， 因为删除的节点并非连续， 所以操作磁盘的时候， 还是需要一个一个的操作， 时间 复杂度还是 过高。 [0004]场景一： 直播场景， 主播客户端的采集码率极高， 开启了多线程上传到服务器， 每 个线程上传的节目分片都不一样， 每个分片按照时间可以排序。 键： 时间片； 值： 节目数据的 指针。 由于多线程上传到服务器， 服务器接收到的分片是杂乱的， 这时如果采用B+树排序， 并按照时间片的顺序取 出键值， 最后得到一个顺序的节目流。 [0005]场景二： P2P下载场景， 客户端从多个P2P节点下载数据， 得到的数据为不确定且重 复的， 就需要排序后输出。 这时如果采用B+树排序， 然后按照顺序取键值， 得到一个顺序的 节目流。 [0006]当然还有其他很多特定 的应用场景， 都是需要顺序的删除键值。 如果按照当前的 方式一个一个节点 地删除效率过低。 发明内容 [0007]有鉴于背景技术的不足， 本发明的主要目的在于提供一种解决B+树批量顺序删除 键值的方法， 所述删除是按照B+树叶子节 点的大小顺序， 从而提高删除的效率， 尤其是对于 频繁的插入删除的场景。 且本发明所提供的删除键值方法是适用于按照B+树叶子节点的大 小顺序删除的情况。 [0008]本发明的目的是由以下技 术方案实现的： [0009]一种B+树批量 顺序删除的方法， 包括以下步骤： [0010]S1、 将一个B+树分为多个； [0011]S2、 定义一个链表， 将树根节点指针和树的最大值存 入所述链 表； [0012]S3、 为每个B+树定义一个p_tree_head指针， 所述p_tree_head指针用于标记顺序 删除后的首个有效节点的位置； [0013]S4、 插入和查询时， 先遍历所述链表找到要插入的B+树， 依次比较链表中树的最大 值， 比所述链 表中树的最大值小即查询或插 入到该B+树；说　明　书 1/3 页 3 CN 114969033 A 3