(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210711424.3 (22)申请日 2022.06.22 (71)申请人 华侨大学 地址 362000 福建省泉州市丰泽区城东城 华北路269号 (72)发明人 潘玉彪　林鑫伟　张惠臻　 (74)专利代理 机构 厦门市首创君 合专利事务所 有限公司 3 5204 专利代理师 连耀忠 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2455(2019.01) (54)发明名称 一种基于多树转换机制的键值存 储方法 (57)摘要 本发明提出一种基于多树转换机制的键值 存储方法， 具体包括： 对于写入的键值数据， 首先 保存至写入跳表， 当大小达到限制后， 转换为只 读跳表插入至内存设备中的B+树； 当B+树大小达 到一定限制时， 根据热度策略遍历键值数据， 将 热度低的键值数据持久化至外存设备中的冷树0 层； 若冷树0层中的键值数据文件数量达到大小 限制， 则触发0层分区操作； 当B+树中的键值数据 执行持久化操作时， 0层分区只接收符合设定范 围的键值数据； 若冷树中特定范围内的键值数据 达到一定热度时， 则转移至外存设备的热树中； 同时热树中低热度的键值数据将转移至冷树中。 本发明提供的方法使用热度策略减少读放大的 同时， 保证写入性能， 实现键值存储系统性能的 整体提升 。 权利要求书2页 说明书5页 附图2页 CN 114996275 A 2022.09.02 CN 114996275 A 1.一种基于多树 转换机制的键值存 储方法， 其特 征在于， 包括： 对于写入的键值数据， 首先保存至写入跳表中， 当大小达到限制后， 转换为只读跳表插 入至内存设备中的B+树； 当B+树的大小达 到一定限制时， 遍历键值数据； 根据热度策略进行判断， 将热度低的键值数据持久化至外存设备中的冷树的0层， 热度 高的键值数据则继续留存在 B+树中； 若冷树的0层中的键值数据文件数量达到大小限制， 则触发0层分区操作， 0层分区操作 依据层中现有的键值数据范围进行均分， 若0层中某一分区的键值数据文件数量达到大小 限制， 则再次触发分区操作； 当B+树中热度较低的键值数据执行持久化操作时， 0层分区只接收符合设定范围的键 值数据； 若冷树中范围内的键值数据经热度策略判断后达到一定热度时， 则将这一范围内 的键值数据转移至 外存设备的热树中， 并使用内存设备中的B+树索引热树中的键值数据； 当热树的大小达到一定限制时， 对键值数据根据热度策略进行判断， 将一个或多个低 热度范围内的键值数据转移至冷树分区中， 并从B+树中删除这些 数据的索引。 2.根据权利要求1所述的一种基于多树转换机制的键值存储方法， 其特征在于， 所述热 度策略具体为： 将只读跳表中的键值数据插入至B+树结构中时， 保存插入时间字段， 用于判断键值数 据的热度情况； 根据节点中记录的时间字段判断该键值数据是否需要保留在B+树中， 若不需保留， 则 持久化至 外存设备的冷树分区内； 对于外存设备中的键值数据， 使用全局热度表来记录键值数据的操作数， 当执行冷树 中的合并操作时， 若一个位于冷树内的范围单位的操作数达到阈值， 则将此范围单位内的 所有键值数据转移至热树中； 当热树达到一定大小限制时， 使用全局热度表对热树内的键值数据执行热度判断， 根 据键值数据的范围热度情况， 判断该范围内的键值数据是否需要保留热树中， 若不需保留， 则将热树中这些 范围内的键值数据转移至冷树中。 3.根据权利要求1或2所述的一种基于多树转换机制的键值存储方法， 其特征在于， 还 包括数据读取步骤， 具体为： S11： 首先在缓存区中查找目标 数据， 若找到， 到步骤S12； 若未找到， 到步骤S13； S12： 系统完成用户的读取请求， 向用户发送读取到的目标 数据； S13： 在B+树中查找目标键及值类型， 若找到且值类型为实际值， 到步骤S12， 若找到且 值类型为 地址信息， 到步骤S14； 若未找到， 到步骤S15； S14： 在外存设备的热树中根据上步得到的地址读取目标 数据， 到步骤S12； S15： 在外存设备的冷树中自顶向下按层查找目标数据， 若找到， 到步骤S12； 若未找到， 到步骤S16； S16： 系统完成用户的读取请求， 向用户发送结果， 未找到目标 数据。 4.根据权利要求1或2所述的一种基于多树转换机制的键值存储方法， 其特征在于， 还 包括数据写入步骤， 具体为： S21： 首先写入跳表结构中， 如果达 到大小限制， 到步骤S2 2； S22： 将此跳表的转换为只读跳表， 并创建新的写入跳表结构用于数据写入；权　利　要　求　书 1/2 页 2 CN 114996275 A 2S23： 若B+树大小未达 到限制， 到步骤S25； 若达 到限制， 到步骤S24； S24： 遍历B+树中的键值数据， 将热度较低的键值数据持久化至外存设备的冷树中， 到 步骤S25； S25： 将只读跳表结构内的键值数据与当前时间保存至B+树结构中； S26： 系统完成用户的写入请求， 向用户发送写入成功的信息 。 5.根据权利要求1或2所述的一种基于多树转换机制的键值存储方法， 其特征在于， 应 用的存储结构具体为： 写入跳表、 只读跳表、 B+树以及磁盘中的冷树结构与热树结构； 其中所述冷树结构为3 层日志结构合并树， 包括0层日志结构、 1层日志结构、 2层日志结构， 且0层日志结构存在分 区结构； 热树结构为单层日志结构合并树。权　利　要　求　书 2/2 页 3 CN 114996275 A 3