KSTORE数据库中数据立方的设计、研究与实现

摘要

近年来，随着计算机的普及以及互联网行业的快速发展，人们对于计算机的依赖程度越来越高，存储在计算机中的数据量急速增长，特别是通信、金融、电子商务等领域每天都会产生大量数据，如何存储这些数据并快速查询已经成为研究热点。海量数据管理系统KSTORE基于压缩技术，有效缩减了数据存储空间以及读写产生的IO。但是，在实现高效存储和查询的同时，如何深入挖掘数据的内在信息并利用这些历史数据进行分析决策已经变得越来越困难，这也对数据库以及数据仓库的设计提出了新的挑战与要求。为了在大数据环境下对联机分析处理应用有更好的支持，我们在KSTORE中引入了数据立方技术，设计并实现了与存储引擎深度结合的压缩立方体，大幅提升了上层的聚集分析查询性能。
　　本文提出了支持高效查询的扩展数据立方，称为BDwarf。通过前缀冗余和后缀冗余的消除，可以人幅减少数据立方的体积。B+树结构的引入极大提高了大数据量情况下的查询效率。本文作者通过在BDwarf中额外存储了COUNT，扩展了数据立方的应用面，使其对于聚集查询SUM、COUNT和AVG都有良好的支持。
　　本文给出了计算BDwarf的创建合并算法，这是一种高效率的创建算法，但是需要预排序。根据指针是否指向自己创建的数据块将指针分为实指针和虚指针，在此基础上提出了不需要预排序的插入算法。插入算法更适用于数据量大的情况。分析了BDwarf对于点查询、范围查询以及冰山查询的支持。
　　在建立了数据立方体后，数据的插入、删除、更新操作会使已经物化的数据立方体结果不准确。频繁的更新操作会导致BDwarf上事务冲突明显，性能下降。本文提出了高并发更新维护方案。首先定义了归一化处理，将删除和更新操作对数据的改变统一成和插入一样的格式保存在缓冲区。接着介绍了双缓冲区以及两阶段更新维护机制，有效提高了系统的并发度。

目录

摘要

图目录

表目录

第1章 绪论

1．1 课题背景

1．2 KSTORE简介

1．3 主要贡献和研究内容

1．4 本文结构

1．5 本章小结

第2章 相关工作与研究进展

2．1 数据立方技术

2．1．1 联机分析处理

2．1．2 OLAP与数据立方

2．1．3 数据立方技术

2．2 数据立方物化技术

2．2．1 部分物化

2．2．2 近似数据立方

2．2．3 压缩数据立方

2．3 本章小结

第3章 支持高效查询的扩展数据立方

3．1 引言

3．2 支持高效查询的BDwarf

3．2．1 Dwarf数据立方

3．2．2 扩展数据立方BDwarf

3．3 BDwarf相关分析

3．3．1 冗余消除

3．3．2 BDwarf的大小

3．3．3 BDwarf的高度

3．4 本章小结

第4章 BDwarf的创建与查询

4．1 引言

4．2 BDwarf的创建

4．2．1 创建合并算法

4．2．2 不需预排序的插入算法

4．3 使用BDwarf加速查询

4．3．1 查询类型

4．3．2 查询效率分析

4．4 本章小结

第5章 高并发更新维护

5．1 引言

5．2 高并发更新维护概述

5．3 延迟更新技术

5．3．1 归一化处理

5．3．2 双缓冲区机制

5．4 两阶段更新维护

5．4．1 两阶段更新维护简介

5．4．2 归并算法

5．5 本章小结

第6章 实验结果与分析

6．1 实验准备

6．2 BDwarf的存储空间

6．2．1 存储空间与记录数的关系

6．2．2 存储空间与属性维度的关系

6．3 BDwarf创建算法比较

6．3．1 创建时间与数据量的关系

6．3．2 创建时间与属性维度的关系

6．4 BDwarf查询性能分析

6．4．1 点查询

6．4．2 范围查询

6．5 BDwarf的更新

6．5．1 更新算法效率比较

6．5．2 更新对存储空间的影响

6．6 本章小结

第7章 总结与展望

7．1 本文总结

7．2 未来工作展望

参考文献

攻读硕士学位期间主要的研究成果

致谢