支持快速索引的高效大数据存储结构  

AN EFFICIENT BIG DATA STORAGE STRUCTURE SUPPORTING FAST INDEXING

作　　者：肖英 赵林洁 张宇 屈晓芳 Xiao Ying;Zhao Linjie;Zhang Yu;Qu Xiaofang(College of Information Engineering,China Jiliang University,Hangzhou 310018,Zhejiang,China)

机构地区：[1]中国计量大学信息工程学院,浙江杭州310018 [2]浙江省电磁波信息技术与计量检测重点实验室,浙江杭州310018 [3]杭州代码鸽智能科技有限公司,浙江杭州310018

出　　处：《计算机应用与软件》2024年第3期28-33,共6页Computer Applications and Software

基　　金：浙江省自然科学基金项目(Y20F010069)。

摘　　要：Trie树为处理字符串数据提供了高效的存储和索引。然而,当字符串数据很大时,利用Trie树进行数据存储会导致空间效率变得很低。因此,提出一种支持快速索引的高效大数据存储结构,称为16-bit Trie树,该结构使用16位表示子节点信息,同时用映射表帮助快速索引至指定的子节点,使得16-bit Trie树在处理大数据时仍然具有高效的空间效率。结果表明,16-bit Trie树保留了传统Trie树较高的索引速度,同时提高了其空间效率。与红黑树和B+树相比,16-bit Trie树的插入时间和空间消耗基本相同,但在索引速度上比其快了2倍左右。Trie tree provides efficient storage and indexing to handle string data.However,the data storage using Trie tree will lead to lower spatial efficiency when the String data is large.Therefore,an efficient big data storage structure supporting fast indexing,named as 16-bit Trie tree,is proposed.The structure used 16 bits to represent child nodes information,and mapping table was used to help quickly index to the specified child nodes,which made higher spatial efficiency for 16-bit Trie tree as processing big data.The results show that the 16-bit Trie tree retains the higher indexing speed of the traditional Trie tree and improves its space efficiency.Compared with the Red-black tree and the B+tree,the 16-bit Trie tree has the same insertion time and space consumption,but the index speed is about 2 times faster than the Red-black tree and B+tree.

关 键 词：字符串检索 Trie树结构 字符串处理及索引 快速检索 

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]