适用于范围查询的列存储数据桶划分算法

摘要：

范围查询是数据库中一项重要的操作.列存储数据库中,能否有效查找一个范围内的属性值,获取对应的行号集合,将极大影响元组重构的效率.与树型结构相比,Hash表对数据的精确查找具有更高的效率,但是范围查找的效率比较低.针对这种情况,提出了一种改进的可用于范围查询的数据桶划分算法.为了能够更好地对算法进行描述,首先提出了可用于范围查询的Hash存储模型(ranged Hash,RH),并给出了桶的值域和序列化的定义.其次针对列存储等“读优先”特性,在RH模型的基础上,提出一种改进的桶划分算法.该算法生成可序列化的哈希函数把属性值划分到桶中,能够同时提高属性值的范围查询效率和存储效率.最后,通过实验结果验证算法的有效性.

关键词：列存储、范围查询、Hash表、可序列化、桶划分

所属期刊栏目：50

分类号：TP311.1(计算技术、计算机技术)

资助基金："核高基"重大科技专项基金项目2010ZX01042-001-003-004;国家自然科学基金项目61070031,61070032;上海市自然科学基金项目11ZR1401200

在线出版日期：2013-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：594-601