计算机应用研究

作者：王天宇,徐云,王彪,

单位：中国科学技术大学计算机科学与技术学院,合肥230000；

关键词：内存键值存储,索引结构,哈希表,位图,

基金：国家自然科学基金资助项目(61672480)；国家外专局“111”引智计划资助项目(BP0719016)；；

内存键值存储系统中索引方法决定了系统的时间性能和空间开销，是改进和优化的关键因素。哈希索引提供了O（1）时间复杂度的访问操作，但会产生存储冲突，引起访问性能下降。为此，提出了一种基于位图的键值存储哈希优化方法，可以避免存储冲突提升访问性能。该方法将共前缀的键哈希到同一个块，减少键存储空间；在块内使用层次位图结构，全域位图表示所有键的后缀部分来避免存储冲突，摘要位图支持快速定位和范围查询加速。实验结果表明，优化后的哈希索引在多种负载上均能取得较高吞吐量并具有良好的并发性能，同时内存占用较现有方案大大降低。

来源：2023年第7期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2023年第7期