(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210001913.X (22)申请日 2022.01.04 (71)申请人 武汉大学 地址 430072 湖北省武汉市武昌区珞珈山 (72)发明人 朱彤　何水兵　宋伟　 (74)专利代理 机构 武汉智权专利代理事务所 (特殊普通 合伙) 42225 代理人 张凯 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/23(2019.01) G06F 16/2455(2019.01) G06F 16/248(2019.01) (54)发明名称 持久内存动态哈希索引方法、 系统、 设备及 存储介质 (57)摘要 本发明公开了一种持久内存动态哈希索引 方法、 系统、 设备及存储介质， 所述方法通过预设 数据指纹插入算法定位动态哈希结构中的目标 数据桶， 将哈希键插入目标数据桶， 动态哈希结 构包括指针数组、 数据桶和段； 在目标数据桶中 不存在空闲位置时， 将逻辑上的下一个数据桶作 为备用数据桶， 将哈希键插入备用数据桶； 在插 入成功时， 判断备用数据桶中是否有匹配的数据 指纹， 若匹配， 再将待更新key和数据指纹匹配的 数据槽的key值进行比较， 根据键比较结果进行 刷新； 在插入备用数据桶失败时， 将发生哈希冲 突的段的局部深度与全局深度进行比较， 根据深 度比较结果进行分裂操作， 能够提高持久内存动 态哈希索引速度和效率， 提升了持久内存哈希索 引的性能。 权利要求书2页 说明书14页 附图7页 CN 114385636 A 2022.04.22 CN 114385636 A 1.一种持久内存动态 哈希索引方法， 其特征在于， 所述持久内存动态 哈希索引方法包 括： 根据预设数据指纹插入算法定位动态哈希结构中的目标数据桶， 将哈希键插入所述目 标数据桶， 所述动态哈希结构包括指针数组、 数据桶和段； 在所述目标数据桶中不存在空闲位置时， 将逻辑上的下一个数据桶作为备用数据桶， 将所述哈希键插 入所述备用数据桶； 在插入所述备用数据桶成功时， 判断所述备用数据桶中是否有匹配的数据指纹， 若匹 配， 再将待更新key和所述数据指纹匹配的相应数据槽的key值进行比较， 根据键比较结果 进行刷新操作； 在插入所述备用数据桶失败时， 将发生哈希冲突的段的局部深度与全局深度进行比 较， 根据深度比较结果进行分裂操作。 2.如权利要求1所述的持久 内存动态哈希索引方法， 其特征在于， 所述根据预设数据指 纹插入算法定位动态哈希结构中的目标 数据桶， 将哈希键插 入所述目标 数据桶， 包括： 获取动态哈希结构中的指针数组的前缀和后缀； 基于数据指纹构建预设数据指纹插入算法， 对所述前缀和所述后 缀的索引根据 所述预 设数据指纹插入算法通过哈希函数定位动态哈希结构中的目标数据桶， 将哈希键插入所述 目标数据桶。 3.如权利要求1所述的持久 内存动态哈希索引方法， 其特征在于， 所述在插入所述备用 数据桶成功时， 判断所述备用数据桶中是否有匹配的数据指纹， 若匹配， 再将待更新key和 所述数据指纹匹配的相应数据槽的key值进行比较， 根据键比较结果进行刷新操作， 包括： 在插入所述备用数据桶成功时， 判断所述备用数据桶中是否有匹配的数据指纹， 若匹 配， 再通过最高位定位目录项， 找到所述目录项所指向的目标 段； 根据所述目标段确定对应的目标数据指纹， 对所述目标数据指纹进行检索， 将所述目 标数据指纹中待 更新key和所述数据指纹匹配的相应数据槽的key值进 行比较， 生成键比较 结果； 根据所述键比较结果进行刷新操作。 4.如权利要求3所述的持久 内存动态哈希索引方法， 其特征在于， 所述根据所述键比较 结果进行刷新操作， 包括： 在所述键比较结果为所述待更新key和每个槽存放的key相同时， 更新当前key对应的 值； 在所述键比较结果为所述待更新key和每个槽存放的key不同， 且当前数据桶有空闲位 置时， 将哈希键按顺序插 入。 5.如权利要求1所述的持久 内存动态哈希索引方法， 其特征在于， 所述在插入所述备用 数据桶失败时， 将发生哈希冲突的段的局部深度与全局深度进行比较， 根据深度比较结果 进行分裂操作， 包括： 在插入所述备用数据桶失败时， 将发生哈希冲突的段的局部深度与全局深度进行比 较， 生成深度比较结果； 在所述深度比较结果为所述局部深度小于所述全局深度时， 额外创建新的段进行段内 部分数据迁移；权　利　要　求　书 1/2 页 2 CN 114385636 A 2在所述深度比较结果为所述局部深度等于所述全局深度时， 进行目录扩张， 并切换当 前目录项。 6.如权利要求1所述的持久 内存动态哈希索引方法， 其特征在于， 所述在插入所述备用 数据桶失败时， 将发生哈希冲突的段的局部深度与全局深度进行比较， 根据深度比较结果 进行分裂操作之后， 所述持久内存动态哈希索引方法还 包括： 在接收到删除指令时， 删除当前数据桶的数据， 将逻辑上下一个数据桶里的标志位置 为1的数据迁移至已删除空 闲位置， 并且将所述标志位置为0 。 7.如权利要求1所述的持久 内存动态哈希索引方法， 其特征在于， 所述持久性内存的目 录项有且仅有一个指向某个段的指 针； 所述段内有若干数据桶， 所述数据桶里有若干槽， 一 个槽存放一条数据， 所述动态哈希结构使用全局深度和局部深度来表示段和指向段的指 针 之间的数量关系， 其中， 所述全局深度用于确定目录项的位数， 所述局部深度用于指示段中 公共哈希键的长度。 8.一种持久内存动态 哈希索引系统， 其特征在于， 所述持久内存动态 哈希索引系统包 括： 插入模块， 用于根据预设数据指纹插入算法定位动态哈希结构中的目标数据桶， 将哈 希键插入所述目标 数据桶， 所述动态哈希结构包括指针数组、 数据桶和段； 备用模块， 用于在所述目标数据桶中不存在空闲位置时， 将逻辑上的下一个数据桶作 为备用数据桶， 将所述哈希键插 入所述备用数据桶； 刷新模块， 用于在插入所述备用数据桶成功时， 判断所述备用数据桶中是否有匹配的 数据指纹， 若匹配， 再将待更新key和所述数据指纹匹配的相应数据槽的key值进 行比较， 根 据键比较结果进行刷新操作； 分裂模块， 用于在插入所述备用数据桶失败时， 将发生哈希冲突的段的局部深度与全 局深度进行比较， 根据深度比较结果进行分裂操作。 9.一种持久内存动态 哈希索引设备， 其特征在于， 所述持久内存动态 哈希索引设备包 括： 存储器、 处理器及存储在所述存储器上并可在所述处理器上运行 的持久内存动态哈希 索引程序， 所述 持久内存动态哈希索引程序配置为实现如权利要求 1至7中任一项 所述的持 久内存动态哈希索引方法的步骤。 10.一种存储介质， 其特征在于， 所述存储介质上存储有持久内存动态 哈希索引程序， 所述持久内存动态哈希索引程序被处理器执行时实现如权利要求1至7中任一项所述的持 久内存动态哈希索引方法的步骤。权　利　要　求　书 2/2 页 3 CN 114385636 A 3