混合索引结构构建方法及其访问方法、闪存设备及存储介质与流程

摘要: 本技术实施方式涉及数据存储,特别是涉及一种混合索引结构的构建方法及其访问方法、闪存设备及存储介质。背景技术:1、索引是现代数据管理和存储系统中不可或缺的核心组件...
混合索引结构构建方法及其访问方法、闪存设备及存储介质与流程

本技术实施方式涉及数据存储,特别是涉及一种混合索引结构的构建方法及其访问方法、闪存设备及存储介质。

背景技术:

1、索引是现代数据管理和存储系统中不可或缺的核心组件,其性能直接决定了系统在处理海量数据时的效率。当前广泛应用的两类索引结构——树索引和哈希索引,虽然各自具备显著优势,但在应对复杂负载和优化性能方面仍存在诸多不足。

2、目前,现有的技术方案是采用树索引(如b+树)或哈希索引对数据进行存储及访问。然而,随着数据插入量的增加,树的高度不断增长,导致访问复杂度维持在o(l ogn)。这使得树索引在插入和查询操作中的性能逐渐下降,难以满足高负载场景的需求。哈希索引通过哈希映射实现常数级的高效点查询,适用于键值存储和高频事务处理,然而,由于传统哈希函数的随机性,数据插入时往往破坏了负载中的局部性特征。局部性的输入数据分散到随机位置,不利于缓存优化,从而降低了性能。

3、综上所述,上述现有的技术方案存在以下问题:①局部性优化不足:哈希节点采用随机性强的哈希函数,未能充分利用输入数据的局部性特征,导致局部性负载下性能提升有限。②树结构扩展性不足:混合索引中树的单棵结构在插入数据量增多时,访问路径迅速增加,影响性能扩展性。

技术实现思路

1、本技术实施例提供一种混合索引结构的构建方法及其访问方法、闪存设备及存储介质,通过引入全局范围表,将键空间划分为多个子树,并将键值对存储至子树中的叶节点,从而构建混合索引结构,本技术能够降低单棵树的插入数据量,通过降低树的高度来优化索引的访问路径和性能,同时优化哈希函数来提升索引在局部性负载下的整体效率。

2、本技术实施例提供以下技术方案:

3、第一方面,本技术实施例提供一种混合索引结构的构建方法,混合索引结构包括全局范围表和多个子树,全局范围表包括全局范围,全局范围被等分为多个地址范围,其中,一个地址范围对应一个子树,方法包括:

4、获取待插入的键值对,其中,键值对包括一个插入键及其对应的值;

5、根据待插入的键值对,计算子树下标,其中,一个子树对应一个子树下标;

6、通过全局范围表,根据子树下标,确定子树下标对应的子树地址;

7、根据子树地址,确定子树地址对应的目标子树,并在目标子树中查询插入键对应的目标插入叶节点;

8、基于目标插入叶节点,通过哈希函数,确定目标插入叶节点对应的目标插入哈希桶;

9、将键值对插入至目标插入哈希桶,以构建子树。

10、在一些实施例中,根据待插入的键值对,计算子树下标,包括:

11、获取地址范围的范围长度;

12、对范围长度和待插入的插入键进行整除计算,得到第一数值,其中,第一数值为整数,第一数值=待插入的插入键/范围长度;

13、根据第一数值,确定子树下标,其中,子树下标等于第一数值。

14、在一些实施例中,子树包括根节点和多个非叶节点,根据子树地址,确定子树地址对应的目标子树,并在目标子树中查询插入键对应的目标插入叶节点,包括:

15、根据子树地址,确定子树地址对应的目标子树;

16、从目标子树的根节点开始逐层搜索目标子树的非叶节点,以根据非叶节点对应的关键字和插入键,确定第一节点,其中,非叶节点用于存储关键字;

17、若第一节点为叶节点,则将第一节点确定为目标插入叶节点。

18、在一些实施例中,哈希函数包括第一哈希函数和第二哈希函数,目标插入叶节点包括多个哈希桶,哈希桶包括多个槽位,基于目标插入叶节点,通过哈希函数,确定目标插入叶节点对应的目标插入哈希桶,包括:

19、根据第一哈希函数和第二哈希函数,确定第一桶标号及其对应的第一哈希桶和第二桶标号及其对应的第二哈希桶;

20、判断第一哈希桶或第二哈希桶中是否存在空闲槽位;

21、若第一哈希桶或第二哈希桶中存在空闲槽位,则将存在空闲槽位的哈希桶确定为目标插入叶节点对应的目标插入哈希桶。

22、在一些实施例中,方法还包括:

23、若第一哈希桶和第二哈希桶中不存在空闲槽位,则根据第一桶标号和第二桶标号,确定多个第三桶标号和多个第四桶标号,其中,第三桶标号的范围为[第一桶标号+1,第一桶标号+预设桶数量],第四桶标号的范围为[第二桶标号+1,第二桶标号+预设桶数量];

24、根据多个第三桶标号和多个第四桶标号,确定多个第三哈希桶和多个第四哈希桶,其中,一个第三桶标号对应一个第三哈希桶,一个第四桶标号对应一个第四哈希桶;

25、按照桶标号从小到大的顺序,依次遍历第三哈希桶和第四哈希桶,以判断是否存在某一个第三哈希桶或第四哈希桶中存在空闲槽位;

26、若存在某一个第三哈希桶或第四哈希桶中存在空闲槽位,则将存在空闲槽位的哈希桶确定为目标插入叶节点对应的目标哈希桶。

27、在一些实施例中,方法还包括:

28、若第三哈希桶和第四哈希桶中不存在空闲槽位,则根据目标插入叶节点中的键值对的数量和插入键,得到目标插入叶节点对应的第一中位值;

29、根据目标插入叶节点对应的第一中位值,确定分裂后的地址范围;

30、根据分裂后的地址范围,对目标插入叶节点进行分裂,得到分裂后的第一目标叶节点和第二目标叶节点;

31、将第一目标叶节点和第二目标叶节点添加至子树,得到更新后的子树;

32、基于更新后的子树,确定插入键对应的目标插入叶节点,其中,插入键对应的目标插入叶节点为第一目标叶节点或第二目标叶节点;

33、基于目标插入叶节点,通过哈希函数,确定目标插入叶节点对应的目标插入哈希桶,并将键值对插入至目标叶节点中的目标插入哈希桶。

34、在一些实施例中,根据目标插入叶节点中的键值对的数量和插入键,得到目标插入叶节点对应的第一中位值,包括:

35、获取目标插入叶节点对应的当前中位值;

36、根据当前目标插入叶节点中的键值对的数量、当前中位值和插入键,计算中位值的影响因子,其中,中位值的影响因子=(当前中位值-插入键)/当前目标插入叶节点中的键值对的数量;

37、根据中位值的影响因子和插入键,对当前中位值进行更新,得到目标插入叶节点对应的第一中位值。

38、在一些实施例中,根据中位值的影响因子和插入键,对当前中位值进行更新,得到目标插入叶节点对应的第一中位值,包括:

39、若插入键小于当前中位值,则将当前中位值与影响因子的差值确定为目标插入叶节点对应的第一中位值;

40、若插入键大于或等于当前中位值,则将当前中位值与影响因子的累加值确定为目标插入叶节点对应的第一中位值。

41、第二方面,本技术实施例提供一种基于混合索引结构的访问方法,混合索引结构包括全局范围表和多个子树,全局范围表包括全局范围,全局范围被等分为多个地址范围,其中,一个地址范围对应一个子树,子树包括多个叶节点,方法包括:

42、获取待查找的键;

43、根据待查找的键,计算子树下标,其中,一个子树对应一个子树下标;

44、通过全局范围表,根据子树下标,确定子树下标对应的子树地址;

45、根据子树地址,确定子树地址对应的目标子树,并在目标子树中查询待查找的键对应的目标查找叶节点;

46、基于目标查找叶节点,通过哈希函数,确定目标查找叶节点对应的目标查找哈希桶,并在目标查找哈希桶中获取待查找的键对应的值。

47、在一些实施例中,哈希函数包括第一哈希函数和第二哈希函数,目标查找叶节点包括多个哈希桶,哈希桶用于存储键值对,基于目标查找叶节点,通过哈希函数,确定目标查找叶节点对应的目标查找哈希桶,包括:

48、根据第一哈希函数和第二哈希函数,确定第一桶标号及其对应的第一哈希桶和第二桶标号及其对应的第二哈希桶;

49、判断第一哈希桶或第二哈希桶中是否存在某一个键值对的键与待查找的键一致;

50、若第一哈希桶或第二哈希桶中存在某一个键值对的键与待查找的键一致,则获取键值对,并根据键值对获取待查找的键对应的值。

51、在一些实施例中,若第一哈希桶和第二哈希桶中不存在某一个键值对的键与待查找的键一致,则根据第一桶标号和第二桶标号,确定多个第三桶标号和多个第四桶标号,其中,第三桶标号的范围为[第一桶标号+1,第一桶标号+预设桶数量],第四桶标号的范围为[第二桶标号+1,第二桶标号+预设桶数量];

52、根据多个第三桶标号和多个第四桶标号,确定多个第三哈希桶和多个第四哈希桶,其中,一个第三桶标号对应一个第三哈希桶,一个第四桶标号对应一个第四哈希桶;

53、按照桶标号从小到大的顺序,依次遍历第三哈希桶和第四哈希桶,以判断第三哈希桶或第四哈希桶中是否存在某一个键值对的键与待查找的键一致;

54、若第三哈希桶或第四哈希桶中存在某一个键值对的键与待查找的键一致,则获取键值对,并根据键值对获取待查找的键对应的值。

55、在一些实施例中,方法还包括:

56、接收用户发出的删除指令;

57、根据删除指令,在子树中查找删除指令对应的键值对;

58、将键值对所在的槽位清空,以对键值对进行删除操作,并将槽位置为空闲槽位。

59、在一些实施例中,方法还包括:

60、接收用户发出的更新指令,其中,更新指令包括第一更新值;

61、根据更新指令,在子树中查找更新指令对应的键值对,并将键值对中的值更新为第一更新值。

62、第三方面,本技术实施例提供一种闪存设备,包括:

63、至少一个处理器;和

64、与至少一个处理器通信连接的存储器;其中,

65、存储器存储有可被至少一个处理器执行的指令,指令被至少一个处理器执行,以使至少一个处理器能够执行如第一方面的混合索引结构的构建方法,或者,第二方面的基于混合索引结构的访问方法。

66、第四方面,本技术实施例提供一种非易失性计算机可读存储介质,非易失性计算机存储介质中存储有计算机程序或指令,当计算机程序或指令被执行时,实现如第一方面的混合索引结构的构建方法,或者,第二方面的基于混合索引结构的访问方法。

67、本技术实施方式的有益效果是:区别于现有技术的情况,本技术实施方式提供一种混合索引结构的构建方法,混合索引结构包括全局范围表和多个子树,全局范围表包括全局范围,全局范围被等分为多个地址范围,其中,一个地址范围对应一个子树,子树包括多个叶节点,叶节点用于存储键值对,方法包括:获取待插入的键值对,其中,键值对包括一个插入键及其对应的值;根据待插入的键值对,计算子树下标,其中,一个子树对应一个子树下标;通过全局范围表,根据子树下标,确定子树下标对应的子树地址;根据子树地址,确定子树地址对应的目标子树,并在目标子树中查询插入键对应的目标插入叶节点;基于目标插入叶节点,通过哈希函数,确定目标插入叶节点对应的目标插入哈希桶;将键值对插入至目标插入哈希桶,以构建子树。本技术能够降低单棵树的插入数据量,通过降低树的高度来优化索引的访问路径和性能,同时优化哈希函数来提升索引在局部性负载下的整体效率。