基于闪存的数据库存储结构研究

摘要

闪存作为一种新的存储介质，正在逐步取代磁盘的主导地位。
　　 但是由于历史原因，关系数据库的页面存储结构主要是针对于磁盘的特点设计的，未能充分发挥闪存的性能优势。因此基于闪存的数据库研究成为当前的一个重要课题。现阶段对闪存数据库的研究主要集中在以传统页面存储结构为基础进行优化，其性能仍然受到传统架构的制约。
　　 本文提出一种基于闪存的数据库存储结构(FBSS)，主要针对于闪存读写速度不均衡的特性，将数据分成块(Block)与页面(Page)。在Block中存储若干个Page。Block为最小的数据写入单位，即NAND型闪存的擦除单位。Page为最小的数据读取单位。
　　 为了进一步优化读写性能，本文提出了一种针对新型数据库存储结构的压缩算法。该压缩算法的主要特点是，将数据按照Block压缩，在读取时，只需要以Page为单位解压即可。这样在保证数据有良好压缩率的前提下，在读取时不会因为只需要一小部分数据而整块的解压，既减小了读取时的I0量，又降低了解压带来的CPU开销。
　　 通过实验验证，应用FBSS数据库存储结构使得数据体积大幅缩减，并且具有较好的随机访问性能，对改善数据库的I0瓶颈具有重大意义。

目录

摘要

第1章 绪论

1．1 课题背景

1．2 研究动机

1．3 研究内容

1．3．1 基于闪存的数据库存储结构

1．3．2 支持按页解压的成块压缩算法

1．4 论文结构

1．5 本章小结

第2章 基础理论

2．1 闪存

2．1．1 闪存简介

2．1．2 闪存缺陷

2．1．3 闪存特性

2．2 数据库分页存储结构

2．2．1 名词介绍

2．2．2 分页存储结构

2．3 闪存数据库相关研究概述

2．4 本章小结

第3章 基于闪存的数据库存储结构

3．1 设计准则

3．2 整体框架

3．2．1 物理存储结构

3．2．2 支持按页解压的成块压缩算法

3．3 基本操作实现

3．3．1 读取

3．3．2 插入

3．3．3 更新

3．3．4 删除

3．4 存在问题与解决方案

3．4．1 Block空间不足

3．4．2 重新压缩

3．5 未来工作方向

3．6 本章小结

第4章 支持按页解压的成块压缩算法

4．1 设计准则

4．2 压缩算法选择

4．2．1 字典压缩算法

4．2．2 熵编码

4．3 算法描述

4．4 本章小结

第5章 实验结果与分析

5．1 实验环境

5．2 数据集

5．3 FBSS与应用主流压缩算法的传统分页结构对比

5．3．1 压缩率对比

5．3．2 压缩时间对比

5．3．3 解压缩时间对比

5．3．4 读取性能对比

5．3．5 写入性能对比

5．4 页面大小对FBSS的影响

5．4．1 对压缩性能的影响

5．4．2 对访问性能的影响

5．5 本章小结

第6章 总结与展望

6．1 本文主要工作

6．2 未来工作展望

参考文献

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

致谢