(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211045963.4 (22)申请日 2022.08.29 (71)申请人 钟士平 地址 410000 湖南省长 沙市雨花区井湾路 19号东联名园13 栋503 (72)发明人 钟士平　钟芮　谭剑辉　罗莽　 梁庆　胡宗平　吴智强　蒋震东　 岳奕作　李智　舒采伟　邓振华　 彭奥宸　刘明哲　伍康为　钟生鹏　 (74)专利代理 机构 长沙智勤知识产权代理事务 所(普通合伙) 43254 专利代理师 曾芳琴 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2455(2019.01) (54)发明名称 基于A+树数据结构存 储的数据查询方法 (57)摘要 本发明涉及计算机数据结构及数据查询方 法技术领域， 尤其涉及基于A+树数据结构 存储的 数据查询方法， 包括： 将数据的关键字 Key值进行 有序分割后， 获得数字排列特征序列； 将序列中 的数字有序的与树结构各层级节点内的数组下 标进行关联， 构成树形结构与数 组相结合表示的 链路； 将数据地址或数据页地址存储至树叶子节 点的数组中， 非叶子节点的数 组中存储次级节点 地址， 构建基于A+树数据结构 存储的数据查询方 法。 相对Hash算 法， 通过将动、 静态树节点相结合 的方式， 实现数据高效查询， 支持数据遍历， 且无 Hash冲突； 在外存储器中应用时， A+树通过将链 路与数据页结合的方式有效降低I/O请求， 相对B +树算法， 提高了数据查询及应用效率。 权利要求书4页 说明书15页 附图7页 CN 115374124 A 2022.11.22 CN 115374124 A 1.基于A+树数据结构存 储的数据查询方法， 其特 征在于， 包括以下步骤： 将数据的关键字Key值按预设定的分割策略进行有序分割， 获得由多个数字组成的数 字排列特 征序列； 将树形结构与数组结合生成A+树数据结构， 基于所述A+树数据结构构 建A+树， 其中， 所 述A+树的树节点类型包括动态 节点和/或静态 节点； 将所述数字排列特征序列中的数字对应作为所述A+树中各层级节点的节点特征数字， 有序与所述A+树中各层 级节点内的数组下标进 行关联， 构成树形结构与数组相结合表示的 链路； 将数据地址或数据页地址存储至所述A+树中 叶子节点的数组中， 以及将次级节点地址 存储到所述A+树中非叶子节点的数组； 根据所述A+树中树节点类型的不同， 通过所述链路进行数据查询， 以及通过所述A+树 中的所述叶子节点将所述链路与数据页结构相结合， 构成A+树链路页， 通过所述A+树链路 页进行数据查询。 2.如权利要求1所述的方法， 其特征在于， 所述将数据的关键字Key值按预设定的分割 策略进行有序分割， 获得由多个数字组成的数字排列特 征序列， 包括： 检查数据的所述关键字Key值的长度是否小于所述分割策略中预设的所述Key值最大 长度， 其中， 所述K ey值最大长度为预设的应用数据集中最大关键 字Key值位数； 若小于， 则基于所述Key值最大长度与所述关键字Key值的长度之间的位数差进行补位 0， 使所述关键 字Key值的长度等于所述K ey值最大长度； 将补位后的所述关键字Key值基于所述分割策略中预设的分割长度进行有序分割， 得 到由多个数字组成的所述数字排列特 征序列。 3.如权利要求1所述的方法， 其特征在于， 所述动态节点包括头部指针、 引导数组和指 针数组， 所述静态节点包括头部指针和指针数组， 所述将所述数字排列特征序列中的数字 对应作为A+树中各层 级节点的节 点特征数字， 有序与所述A+树中各层级节 点内的数组下标 进行关联， 构成树形 结构与数组相结合表示的链路， 包括： 根据当前节点的所述节点特征数字的位数长度， 一 次性申请并初始化所述静态节点中 的所述指针数组以及所述动态节点中的所述引导数组对应长度的存储空间， 其中， 所述动 态节点中的所述指 针数组长度基于需求动态增减， 所述引导数组存储同一节点内所述指 针 数组的下 标， 所述头 部指针在所述A+树的同层级节点间形成单向有序链 表； 设置根节点作为当前节点， 从所述关键字Key值的所述数字排列特征序列中获取对应 当前节点的所述节点特 征数字； 若所述A+树中树节点为所述动态节点， 将当前节点的所述节点特征数字作为当前节点 中的所述引导数组的下标定位并读取引导数组元素， 将读取的所述引导数组元素作为当前 节点中的所述指针数组的下 标， 定位指针数组元 素； 基于当前节点中定位到的指针数组元素获取次级节点地址， 直至定位到所述叶子节 点， 构成与所述关键 字Key值对应的通过树形 结构与数组相结合表示的链路； 若所述A+树中树节点为所述静态节点， 则直接将对应当前节点的所述节点特征数字作 为当前节点中的所述指针数组的下标， 定位指针数组元素并获取次级节点地址， 直至定位 到所述叶子节点；权　利　要　求　书 1/4 页 2 CN 115374124 A 2构建从所述根节点到所述叶子节点通过树形结构与数组相结合表示的链路， 构 成与所 述关键字Key值对应的通过树形 结构与数组相结合表示的链路。 4.如权利要求3所述的方法， 其特征在于， 所述根据所述A+树中树节点类型的不同， 通 过所述链路进行 数据查询， 包括： 当所述A+树中各层级节点的树节点类型为所述静态节点时， 或所述A+树中各层级节点 的树节点类型为所述动态节点时， 则基于当前节点的所述节点特征数字定位指针数组元 素， 基于定位到的指针数组元素提取次级节点地址进行寻址， 直至所述叶子节点， 其中， 数 据查询的时间 复杂度为O(Htree)， Htree为所述A+树的高度； 当所述A+树中各层级节点的树节点类型包括所述动态节点与所述静态节点 时， 则进行 数据混合查询， 其中， 当所述A+树的高度为H， 且从根节 点至第L层为所述静态节 点， 第H‑L层 为所述动态节点， 则从根节点开始到第L层节点为所述静态节点的数据查询， 从L+1层节点 至叶子节点层为所述动态 节点的数据查询， 且所述数据混合 查询的时间 复杂度为O(H ‑L)。 5.如权利要求4所述的方法， 其特征在于， 在所述基于当前节点的所述节点特征数字定 位指针数组元 素之前， 包括： 若所述A+树中从当前节点层至根节点层均为所述静态节点， 且在节点初始化时， 当前 节点层至根节点层在 存储介质中横向、 纵向有序排列， 则采用地址推算方式， 根据当前节 点 所在的节 点层的首地址、 当前节 点的所述节 点特征数字、 当前节点在所述关键字Key值中截 取的数字， 计算当前节点 地址， 其中， 地址推算公式为： Pn＝P0+Snode×Nn×10L+Nf×Sp 其中， Pn为当前节点地址， P0为当前节点所在的节点层的首地址， Snode为节点占用空间， Nn为截取的数字， 在所述关键字Key值的数列特征序列中， 将当前节点之前的节点特征数字 组拼合得到， L为当前节点的所述节点 特征数字长度， Nf为当前节点的所述节点特征数字； Sp 为数组元 素占用空间。 6.如权利要求3所述的方法， 其特 征在于， 方法还 包括对链路进行节点插 入， 包括步骤： 在次级节点寻址过程中， 若判断出获得的所述 次级节点地址无效， 则新建节点， 并将所 述新建节点作为当前节点继续进行次级节点 寻址过程； 在所述新建节点的过程中， 若当前节点为所述静态节点， 则直接将所述新建节点的地 址写入当前节点所定位的指针数组元素中， 若当前节点为所述动态节点， 则将当前节点的 所述指针数组扩展一个数组元素， 并将所述新建节点的地址写入所述指 针数组扩展的元素 中， 再将所述指针数组的长度写入定位的所述定位的引导数组元 素中； 若当前节点为所述叶子节点， 则将所述关键字Key值对应的数据地址或数据页地址写 入当前节点中定位的指针数组元 素中， 实现对应所述关键 字Key值的链路节点插 入。 7.如权利要求6所述的方法， 其特 征在于， 方法还 包括对链路进行节点删除， 包括 步骤： 在所述A+树中， 根据所述关键字Key值对应的链路， 从叶子节点开始， 以当前节点的所 述节点特 征数字定位待删除的指针数组元 素； 若当前节点 为所述静态 节点， 则将所定位到的指针数组元 素置空； 若当前节点为所述动态节点， 则先删除定位到的指针数组元素， 并将所述指针数组发 生变化的数组下标在所述引导数组中进行更新， 其中， 删除定位到的指针数组元素指将所 述定位的数组元 素之后的数组元 素向前覆盖， 并将所述指针数组长度减一个元 素；权　利　要　求　书 2/4 页 3 CN 115374124 A 3