《基于闪存的浓缩数据立方存储研究》由会员分享，可在线阅读，更多相关《基于闪存的浓缩数据立方存储研究（51页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 硕士学位论文 基于闪存的浓缩数据立方存储研究 姓名：马学聪 申请学位级别：硕士 专业：软件工程 指导教师：陈长清 2011-05-10 I 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 摘摘 要要 OLAP 的快速多维响应查询需要预先进行数据立方的计算并将结果保存。 由于数 据立方的巨大尺寸，使其响应查询变慢。在内存实化数据立方，通过避免了大量的 I/O 操作来缩短查询响应时间， 但是数据立方的尺寸一般来说是内存空间的几个数量 级。浓缩数据立方将同一群基本单元组聚集的立方元组浓缩成一组，虽然有效地减 小了数据立方的尺寸，但是由于内
2、存空间的限制，仍不能满足较大数据立方的内存 实化要求。 SSD（固态硬盘）作为新型的二级存储设备，其空间和访问速度都能够得到很好 的保证。 本文根据 SSD 的特性， 结合内存实化和固态硬盘的高性能， 提出了内存-SSD 的两级存储结构。内存实化较粗粒度的小方，SSD 实化细粒度的元组，其中首先保 证所有最细粒度的小方在 SSD 实化。对于小方粒度的内存实化方法，其中的重新计 算的瓶颈问题，可以考虑将完整的立方保存在 SSD。点查询时先响应内存实化的小 方，如果没有需要查询的小方，然后在 SSD 上查询。范围查询直接在 SSD 上响应。 两级存储结构，保证了快速响应点查询和准确处理范围查询。
3、SSD 作为闪存的一种，必须考虑闪存的特性。闪存具有读写速度不对称性、不 可重复写以及擦除次数有限等特点。如果将传统索引直接移植到 SSD 上，绝对无法 充分利用 SSD 的容量及其高性能。 所以针对 SSD 的 I/O 特性以及目前基于 SSD 的索 引结构存在的问题，提出多级动态完美哈希索引结构，从而在保证高效率的查询响 应。 关键词：关键词：浓缩数据立方 固态硬盘 两级存储结构 多级动态哈希 II 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 Abstract The rapid response of a query OLAP mult
4、idimensional cube needs to pre-calculatedata and save the results. Due to the enormous size of the data cube， the response of a query is slowed down. Real data cube in memory， shortens the query response time by avoiding a large number of I /O operations， but the size of the data cube memory space i
5、s generally several orders of magnitude. Condensed Cube will condense gathered with a group of the cube of the basic unit of group into a set of tuples， while it effectively reduces the size of the data cube， but because of memories limitations，still can not satisfies the large memory data cube impl
6、ementation of requirements. SSD (solid state drive) as a new type of secondary storage device， and its space and the speed of access can be a very good guarantee. Based on SSD features， combined with solid-state memory and the performance of hard drive two-level memory-SSD storage structure is propo
7、sed. Coarse granularity of cuboids is materialized in memory， In SSD implementation of fine-grained meta-group is materialized， which first of all ensure that all the finest granularity tuples are materialized in SSD. Memory for the implementation of cuboids method， in which the bottleneck re-calcul
8、ation， consider the complete cubic stored in SSD. Point queries firstly response the cuboids materialized by memory， there is no cuboids queried in memory， then query in SSD. Range queries response directly in SSD. Two-level storage structure is used to make sure of the speed of point queries and th
9、e correctness of range queries. SSD as a flash， we must consider the characteristics of flash memory. Flash memory has asymmetric read and write in speed， it can not be repeated a limited number of write and erase characteristics. Transplanted directly to the SSD on the traditional index， certainly
10、can not take full advantage of SSDs high-performance features. So for the SSDs III 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 I/O features and the current index structure based SSD problems， we proposed multi-level dynamic hash index structure characteristic of the hybrid ，thus make sure the ef
11、ficient response of inquires. Key words：Condensed data cube SSD Two-level storage structure Multi-level dynamic hash 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书
12、学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密， 在 年解密后适用本授权书。 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 1 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论绪论 1.1 研究背景及
13、意义研究背景及意义 联机分析处理（Online Analytical Processing， OLAP）的概念是由 E. F. Codd 于 1993 年提出，为了给用户提供直观的多维考察和分析数据支持，通常将多维视图作 为各种前端分析工具的概念模型。数据立方（Data Cube）1 称源表中考察的目标属 性为度量，称用户观察角度的属性为维，因此我们采用数据立方作为这样一种多维 视图。数据立方对基本关系表中的数据在所有维属性组合上计算聚集。由于 OLAP 用来管理决策所需要的数据量巨大，而且往往还要满足用户的即时查询，及时地向 用户提供分析的数据，从而对查询响应速度提出了更高的要求。 为了提高
14、 OLAP 查询响应速度。一般将存储在数据立方中的原始数据进行聚集 计算，然后对数据立方进行存储，但是由于数据立方通常按照源表维数的指数增长， 其尺寸是相当庞大的。 内存实化数据立方虽然能够通过避免 I/O 加快响应速度， 但是 内存空间有限，完全内存实化数据立方是不现实的。而在传统的磁盘上实化又存在 令人头疼的 I/O 问题。SSD 作为一种纯电子设备，能够解决传统磁盘 I/O 操作中的机 械延迟，本文结合内存实化和 SSD 实化建立两级存储模型，即按照两种粒度进行内 存和 SSD 实化数据的选择，即小方级别的选择和元组级别的选择。在容量大的 SSD 中从最细粒度的元组开始实化，这样保证所有
15、查询都能响应，在容量小的内存中选 择实化较粗粒度的小方，从而保证了快速响应点查询和准确处理范围查询。但是由 于闪存的硬件特性使得读写速度不对称性，不可重复写以及擦除次数有限，直接采 用传统的索引给查询和更新维护带来了很大的的难度，因此如何根据闪存特性构建 在 SSD 上的索引将直接影响 OLAP 查询效率和数据质量，尤其是更新维护的效率。 在考虑应用于 SSD 环境的索引结构时， 还需要考虑 SSD 的 I/O 特性， 比如 SSD 的连 续写性能优于随机写性能等2。为解决上述问题，不少国内外研究者已经提出基于闪 存的多种索引结构，在总结现存的基于闪存的索引结构的优点及问题的基础上，本 文提出
16、了一种更加高效的闪存索引结构-多级动态完美哈希索引，将写操作转变为串 2 华 中 科 技 大 学 硕 士 学 位 论 文 华 中 科 技 大 学 硕 士 学 位 论 文 行化的操作序列，以逐一追加的方式解决了由数据插入引发的“频繁写”问题3，从而 提高数据立方的查询更新性能。 在国内外学者大量相关研究的基础上，本文将结合浓缩数据立方，探索两级存 储结构，充分利用 SSD 特性，构建在 SSD 上的索引，加快 OLAP 查询的响应速度和 更新效率，从而提高 OLAP 应用系统的整体性能。 1.2 国内外概况国内外概况 OLAP 作为一项为企业提供决策的数据分析处理技术， 涉及的查询通常需要巨大 计算量的聚集数据或者数据的趋势等结果。而查询的响应速度随着 OLAP 数据量的 急剧增长以及查询的复杂性而变慢。 这种延迟在大多数 OLAP
