中国高校第一本闪存数据库研究专著
历时两年，倾心之作 内容原创，品质保证
网络发布，免费共享 版权所有，侵权必究
243页，40余万字，系统研究闪存数据库
作者介绍|著作权声明|公益学术行为历史|前言|目录|阅读网页版|下载专著PDF文件
《闪存数据库概念与技术》
（版本号：2015年9月13日全国首发）
厦门大学数据库实验室 林子雨 编著
扫一扫手机访问本网页
林子雨博士，厦门大学计算机科学系助理教授，中国高校首个“数字教师”提出者和建设者（http://www.cs.xmu.edu.cn/linziyu）。于2001年获得福州大学水利水电专业学士学位，2005年获得厦门大学计算机专业硕士学位，2009年获得北京大学计算机专业博士学位。主要研究方向为数据库、数据仓库、数据挖掘、大数据和云计算，发表期刊和会议学术论文多篇。曾作为志愿者翻译了Google Spanner、BigTable和《Architecture of a Database System》等大量英文学术资料，与广大网友分享，深受欢迎。2013年在厦门大学开设《大数据技术基础》课程，并因在教学领域的突出贡献和学生的认可，成为2013年度厦门大学教学类奖教金获得者。编著出版了中国高校第一本系统介绍大数据知识的专业教材《大数据技术原理与应用——概念、存储、处理、分析与应用》，2015年8月由人民邮电出版社正式出版发行，并成为当当、京东等网店畅销书籍。
E-mail: ziyulin@xmu.edu.cn
个人主页：http://www.cs.xmu.edu.cn/linziyu/
数据库实验室网站：https://dblab.xmu.edu.cn
本书共243页，40余万字，为原创内容，由林子雨在大量文献阅读和研究基础上撰写，林子雨享受本书的著作权。本书仅供学术交流之用，未经许可，不得用于商业用途，侵权必究！
声明人：林子雨
2015年9月于厦门大学数据库实验室
《大数据技术原理与应用——概念、存储、处理、分析与应用》，由厦门大学计算机科学系助理教授林子雨博士编著，是中国高校第一本系统介绍大数据知识的专业教材。2015年8月由人民邮电出版社出版发行，并成为京东、当当等网店畅销书籍。
本书定位为大数据技术入门教材，为读者搭建起通向“大数据知识空间”的桥梁和纽带。本书系统梳理总结大数据相关技术，介绍大数据技术的基本原理和大数据主要应用，帮助读者形成对大数据知识体系及其应用领域的轮廓性认识，为读者在大数据领域“深耕细作”奠定基础、指明方向。在本书的基础上，感兴趣的读者可以通过其他诸如《Hadoop权威指南》等工具书，继续深入学习和实践大数据相关技术。
全书共有13章，系统地论述了大数据的基本概念、大数据处理架构Hadoop、分布式文件系统HDFS、分布式数据 库HBase、NoSQL数据库、云数据库、分布式并行编程模型MapReduce、流计算、图计算、数据可视化以及大数据在互联网、生物医学和物流等各个领域的应用。在Hadoop、HDFS、HBase和MapReduce等重要章节，安排了入门级的实践操作，让读者更好地学习和掌握大数据关键技术。
本书可以作为高等院校计算机专业、信息管理等相关专业的大数据课程教材，也可供相关技术人员参考、学习、培训之用。
欢迎访问教材官方网站：https://dblab.xmu.edu.cn/post/bigdata
林子雨将自己花费大量时间整理的研究资料，全部免费发布到网络与广大网友分享：
l 2010年7月，翻译《Google BigTable》英文学术论文，并免费发布
l 2012年5月，翻译第1届、第2届和第5届超大数据库会议英文大会报告（XLDB），并免费发布；
l 2012年9月，全国第一个翻译了《Google Spanner》英文学术论文，并免费发布；
l 2013年9月，全国第一个翻译了《Architecture of a Database System》英文学术论文，并免费发布。
更多资源欢迎访问林子雨个人主页和数据库实验室网站获取：
个人主页：http://www.cs.xmu.edu.cn/linziyu/
数据库实验室网站：https://dblab.xmu.edu.cn
在过去的几十年里，传统的机械式硬盘（或称为普通硬盘）一直都是企业广泛采用的存储介质。但是，随着闪存技术的不断发展，基于闪存的存储设备被认为具有很大的潜力可以取代机械式硬盘，并为企业的各种应用获得更高的性能。闪存具有速度快、体积小、质量轻、能耗低、抗震等特点，而且是非易失的，即使断电也不会丢失信息。由于闪存的优良特性，它已经广泛应用于消费类电子产品中，比如PDA、MP3播放器、移动电话和数码相机。闪存芯片还被封装成不同的产品，比如CF卡、SD卡、迷你SD卡、微型SD卡和USB棒，或者有些闪存芯片会被封装成闪存存储设备（比如基于闪存的固态盘），配备了标准的ATA总线，可以连接到其他宿主设备上面。市场上也已经出现一些新型的个人计算机产品，完全抛弃了机械式硬盘，转而采用基于闪存的固态盘。
图灵奖得主Jim Gray在2008年曾经作出预测：“闪存是磁盘，磁盘是磁带，磁带将消亡”，目前，这个预测在许多应用中已经成为现实。闪存被认为具有很大潜力可以取代机械式硬盘，主要有以下几个方面的原因：
（1）机械式硬盘自身的局限性：机械式硬盘包含了磁头和转动部件，在读取数据时有一个寻道的过程，通过转动盘片和移动磁头的位置，来找到数据在机械式硬盘中的存储位置，然后，才能进行读写。因此，机械式硬盘具有很高的顺序读写性能，但是，在面对随机读写负载时，性能就会变得很差，因为，随机读写需要不断反复移动磁头进行寻址。而且，顺序读写速度和随机读写速度二者之间的差距还在不断扩大。在I/O开销中，机械式硬盘的寻址时间是最耗时的部分。基于机械式硬盘存储的操作系统都会采用不同的优化策略来分摊寻址代价，比如预抓取和磁盘调度计划，但是，无法从根本上解决这个问题。因此，对于企业应用而言，如果包含明显的随机读写负载或者缺少数据访问的局部性，那么，采用机械式硬盘存储数据将会严重制约应用系统的整体性能。
（2）闪存的优良特性：与机械式硬盘相比，基于闪存的存储设备具有更快的数据访问速度，更小的体积，更低的能耗，抗震性也更好。闪存在这个方面的优良特性，是机械式硬盘所无法媲美的，很好地满足了掌上电子产品对存储介质的要求。
（3）闪存的容量增加和价格下降：随着技术和制造工艺的改进，闪存的存储容量不断提高。据预计，直到2012年，NAND闪存的存储密度都会每年翻一倍。闪存芯片之所以遵循摩尔定律，是因为它和集成电路一样都使用了类似的制造技术和工艺。在容量不断提高的同时，闪存的“每字节价格”却在不断下降，这使得闪存和低端、低容量的机械式硬盘设备的竞争力逐渐加强。
数据库是企业构建各种高级应用的基础，经过多年的发展，市场上已经存在可以满足不同企业应用需求的各种数据库产品，比如Teredata、Oralce、SQL Server和MySQL等等。当前的数据库产品大都采用基于磁盘的存储系统。随着闪存技术的发展，一些存储系统制造商，开始提供TB级别的、基于闪存的存储解决方案，其中一个主要目的就是应用于大规模数据库服务器[LeeMPKK08]。另外，随着闪存容量的不断提高，在移动设备中使用嵌入式DBMS已经变得越来越普遍[GanesanMS07][NathK07]，可以用来高效地对设备中的文件进行存储、检索和导航。
但是，由于闪存的读写特性和磁盘具有很大的区别，如果直接把传统的数据库应用到基于闪存的存储设备上，是无法获得好的性能的。虽然在实际应用中，硬件都是隐藏在接口后面，比如SCSI协议或块设备API，但是，在过去三十年里，数据库应用都是为机械式硬盘这类旋转磁盘设备而优化的，这类旋转设备的特点是：具有固定的顺序带宽，但是，具有很大的机械延迟，它严重影响了随机I/O的性能。数据库系统被认为是专门为磁盘量身定制的一种非常典型的应用，从查询优化到SQL操作，再到底层的磁盘管理，都假设底层存储采用了具有较长随机访问延迟的旋转磁盘设备。比如，对于基于磁盘行为而设计的查询优化器而言，它所做出的查询优化决定，可能很不适合用在闪存上。因此，数据库自身的特性和闪存的特性，决定了必须开展相关的研究，使得数据库应用在闪存上能够取得好的性能。
作者多年来在国家自然科学基金、福建省自然科学基金和中央高校基金科研业务费的支持下，以企业级数据库和数据仓库为应用背景，针对闪存环境下的数据库技术进行了深入研究。同时，作者一直承担厦门大学计算机科学系本科生专业课程《数据库系统原理》和研究生专业课程《分布式数据库技术》《大数据技术基础》的教学工作。本书是在丰富的教学实践和扎实的科研工作的基础上撰写的。
本书重点介绍闪存数据库的基本理论和关键技术。本书共分为12章，内容包括闪存和固态盘、闪存文件系统、闪存转换层、闪存数据库概述、闪存数据库存储管理、闪存数据库缓冲区管理、闪存数据库索引、闪存数据库查询处理、闪存数据库事务管理、基于混合存储系统的数据库、闪存数据库实验环境的搭建和基于闪存的键值存储。
第1章主要介绍闪存和固态盘的基础知识，包括闪存的原理、分类、特性和应用，固态盘的特性、产品、应用，固态盘的内部并行结构，以及固态盘性能分析。
第2章主要介绍闪存文件系统，包括JFFS2和Yaffs。
第3章主要介绍闪存转换层（FTL），包括FTL的基本功能，页级别、块级别和混合FTL机制，以及双模式FTL。
第4章给出闪存数据库概述，包括设计面向闪存的DBMS的必要性、闪存特性对DBMS设计的影响、面向闪存的DBMS的设计考虑因素和技术路线。
第5章主要介绍闪存数据库存储管理，包括基于页的方法、基于日志的方法、基于页差异的日志方法和StableBuffer方法。
第6章主要介绍闪存数据库缓冲区管理，包括重新设计面向闪存的缓冲区替换策略的必要性、设计面向闪存的缓冲区替换策略的考虑因素和关键技术，并描述一些具有代表性的方法，比如CFLRU、CFDC、LRU-WSR、CCF-LRU、AD-LRU、FOR、CASA等。
第7章主要介绍闪存数据库索引，包括基于日志的B-树索引、B+-树索引、自适应B+-树索引、FD-树和LA-树等。
第8章主要介绍闪存数据库查询处理，包括PAX页布局模型、连接索引和Jive连接算法、基于PAX的RARE连接算法、基于PAX模型和连接索引的FlashJoin、DigestJoin等。
第9章主要介绍闪存数据库事务管理，描述传统的事务恢复机制及其在闪存数据库中的表现，并给出一些具有代表性的闪存数据库事务管理方法，比如Transactional FTL、TxFlash、Flag Commit、IPL和OPL等。
第10章主要介绍基于混合存储系统的数据库，包括闪存可以代替磁盘作为特种数据的存储介质、闪存可以作为介于磁盘和内存之间的缓存、基于数据访问模式的混合存储系统、基于语义信息的系统框架hStoreage-DB等。
第11章主要介绍闪存数据库实验环境的搭建，包括如何使用闪存模拟器开展实验和如何在PostgreSQL开源数据库的真实环境下开展实验。
第12章介绍基于闪存的键值存储。
闪存数据库是一个比较新的领域，目前缺乏关于这个领域的全面系统的介绍，作者通过阅读和分析国内外大量相关论文和课题资料，并结合自己的研究，撰写了本书，以期尽力跟踪该领域的最新技术进展情况。但由于作者学识有限，本书难免存在一些不足之处，敬请专家和学者批评指正。
林子雨
厦门大学数据库实验室
2015年9月
（注：网页版可以在本网站打开网页在线浏览每章内容）
| 章节 | 内容 | 阅读网页版 |
| 第1章 闪存和固态盘 | 主要介绍闪存和固态盘的基础知识，包括闪存的原理、分类、特性和应用，固态盘的特性、产品、应用，固态盘的内部并行结构，以及固态盘性能分析 | 阅读 |
| 第2章 闪存文件系统 | 主要介绍闪存文件系统，包括JFFS2和Yaffs | 阅读 |
| 第3章 闪存转换层 | 主要介绍闪存转换层（FTL），包括FTL的基本功能，页级别、块级别和混合FTL机制，以及双模式FTL | 阅读 |
| 第4章 闪存数据库概述 | 给出闪存数据库概述，包括设计面向闪存的DBMS的必要性、闪存特性对DBMS设计的影响、面向闪存的DBMS的设计考虑因素和技术路线 | 阅读 |
| 第5章 闪存数据库存储管理 | 主要介绍闪存数据库存储管理，包括基于页的方法、基于日志的方法、基于页差异的日志方法和StableBuffer方法 | 阅读 |
| 第6章 闪存数据库缓冲区管理 | 主要介绍闪存数据库缓冲区管理，包括重新设计面向闪存的缓冲区替换策略的必要性、设计面向闪存的缓冲区替换策略的考虑因素和关键技术，并描述一些具有代表性的方法，比如CFLRU、CFDC、LRU-WSR、CCF-LRU、AD-LRU、FOR、CASA等 | 阅读 |
| 第7章 闪存数据库索引 | 主要介绍闪存数据库索引，包括基于日志的B-树索引、B+-树索引、自适应B+-树索引、FD-树和LA-树等 | 阅读 |
| 第8章 闪存数据库查询处理 | 主要介绍闪存数据库查询处理，包括PAX页布局模型、连接索引和Jive连接算法、基于PAX的RARE连接算法、基于PAX模型和连接索引的FlashJoin、DigestJoin等 | 阅读 |
| 第9章 闪存数据库事务管理 | 主要介绍闪存数据库事务管理，描述传统的事务恢复机制及其在闪存数据库中的表现，并给出一些具有代表性的闪存数据库事务管理方法，比如Transactional FTL、TxFlash、Flag Commit、IPL和OPL等 | 阅读 |
| 第10章 基于混合存储系统的数据库 | 主要介绍基于混合存储系统的数据库，包括闪存可以代替磁盘作为特种数据的存储介质、闪存可以作为介于磁盘和内存之间的缓存、基于数据访问模式的混合存储系统、基于语义信息的系统框架hStoreage-DB等 | 阅读 |
| 第11章 闪存数据库实验环境的搭建 | 主要介绍闪存数据库实验环境的搭建，包括如何使用闪存模拟器开展实验和如何在PostgreSQL开源数据库的真实环境下开展实验 | 阅读 |
| 第12章 基于闪存的键值存储 | 介绍基于闪存的键值存储 | 阅读 |
第一篇 基础篇… 1
第1章 闪存和固态盘… 2
1.1 计算机存储技术… 2
1.2 闪存的原理、分类、特性和应用… 3
1.2.1 闪存的工作原理… 3
1.2.2 闪存的分类… 4
1.2.3 闪存的结构… 6
1.2.4 闪存的特性… 7
1.2.5 闪存产品和应用… 9
1.3 基于闪存的固态盘… 10
1.3.1 固态盘特性… 10
1.3.2 固态盘产品… 11
1.3.3 固态盘应用… 12
1.3.4 固态盘结构… 13
1.3.5 固态盘内部并行特性… 14
1.3.6 固态盘内部特性的探测… 15
1.3.6.1 探测模型… 16
1.3.6.2 探测方法和结果… 16
1.3.6.2.1 块大小的探测… 16
1.3.6.2.2 交织度的探测… 18
1.3.6.2.3 映射策略的探测… 18
1.3.7 固态盘性能… 19
1.3.8 固态盘IO特性实验测试分析… 21
1.4 本章小结… 23
1.5 习题… 23
第2章 闪存文件系统… 24
2.1 闪存文件系统和闪存转换层的比较… 24
2.2 闪存文件系统JFFS2. 25
2.2.1 JFFS2概述… 25
2.2.2 JFFS2的不足之处… 27
2.3 闪存文件系统Yaffs. 27
2.3.1 Yaffs概述… 27
2.3.2 Yaffs体系架构… 28
2.3.3 Yaffs1如何存储文件… 29
2.3.4 垃圾回收… 31
2.3.5 Yaffs1序列号… 32
2.3.6 Yaffs2 NAND模型… 32
2.3.7 坏块和NAND错误的处理… 34
2.3.8 内存数据结构… 34
2.3.8.1 目录结构… 35
2.3.8.2 文件对象… 36
2.3.9 不同机制是如何工作的… 37
2.3.9.1 块和厚片的管理… 37
2.3.9.1.1 块状态… 37
2.3.9.1.2 块和厚片的分配… 38
2.3.9.1.3 关于磨损均衡… 38
2.3.9.2 内部缓存… 38
2.3.9.3 扫描… 39
2.3.9.3.1 Yaffs1扫描… 39
2.3.9.3.2 Yaffs2扫描… 39
2.3.9.3.3 检查点… 40
2.4 本章小结… 40
2.5 习题… 40
第3章 闪存转换层… 41
3.1 FTL的功能… 41
3.1.1 功能概述… 41
3.1.2 地址映射… 42
3.1.3 垃圾回收… 43
3.1.4 磨损均衡… 44
3.1.5 断电恢复… 44
3.2 FTL的映射机制… 45
3.2.1 页级别的FTL机制… 45
3.2.1.1 机制概述… 45
3.2.1.2 典型研究… 46
3.2.2 块级别的FTL机制… 47
3.2.2.1 机制概述… 47
3.2.2.2 相关研究… 48
3.2.2.2.1 NFTL-1机制… 48
3.2.2.2.2 NFTL-N机制… 50
3.2.2.2.3 针对NFTL-1的改进… 51
3.2.2.2.3.1 查找表… 52
3.2.2.2.3.2 页缓存… 52
3.2.3 混合FTL机制… 53
3.2.3.1 机制概述… 53
3.2.3.2 典型研究… 56
3.2.3.2.1 BAST. 56
3.2.3.2.1.1 BAST机制的写操作过程… 57
3.2.3.2.1.2 BAST的缺陷… 58
3.2.3.2.2 FAST. 59
3.2.3.2.3 LAST. 59
3.2.3.2.4 SuperBlock. 60
3.2.3.3 其他相关研究… 60
3.2.4 变长映射… 61
3.2.5 关于不同映射机制的讨论… 61
3.3 双模式FTL. 61
3.4 本章小结… 63
3.5 习题… 64
第二篇 闪存数据库篇… 65
第4章 闪存数据库概述… 66
4.1 基于磁盘的DBMS的存储性能优化技术… 66
4.2 设计面向闪存的DBMS的必要性… 67
4.3 闪存特性对DBMS设计的影响… 69
4.3.1 对IO单位的影响… 69
4.3.2 对页布局的影响… 69
4.3.3 对数据分簇的影响… 69
4.3.4 对查询处理和优化的影响… 70
4.3.5 对缓冲区替换策略的影响… 70
4.3.6 对索引的影响… 70
4.3.7 对事务管理的影响… 70
4.4 面向闪存的DBMS的设计考虑因素… 71
4.5 设计面向闪存的DBMS的技术路线… 72
4.6 进一步讨论… 72
4.7 本章小结… 73
4.8 习题… 73
第5章 闪存数据库存储管理… 74
5.1 数据存储方法概述… 74
5.1.1 基于页的方法… 74
5.1.2 基于日志的方法… 75
5.2 基于页的方法… 76
5.2.1 面向文件系统的FTL机制无法直接应用于DBMS. 76
5.2.2 面向DBMS的FTL机制… 77
5.3 基于日志的方法… 79
5.3.1 日志文件系统原理… 79
5.3.2 LGeDBMS. 80
5.3.3 A/P方法… 81
5.3.4 IPL方法… 82
5.3.4.1 IPL方法概述… 82
5.3.4.2 IPL方法的核心思想… 82
5.3.4.3 IPL的设计… 83
5.3.4.4 IPL方法的缺陷… 84
5.3.5 ICL方法… 84
5.3.5.1 ICL方法概述… 85
5.3.5.2 ICL日志… 85
5.3.5.3 采用ICL日志以后读取DBMS数据页的过程… 87
5.4 基于页差异的日志方法… 87
5.4.1 PDL方法概述… 87
5.4.2 PDL方法的一个实例… 88
5.4.3 PDL方法的设计原则… 91
5.5 StableBuffer 91
5.5.1 StableBuffer的基本原理… 92
5.5.2 StableBuffer的设计位置… 93
5.5.3 StableBuffer管理器… 94
5.5.3.1 StableBuffer管理器的体系架构… 94
5.5.3.2 StableBuffer管理器的数据结构… 94
5.5.3.3 StableBuffer管理器的读写操作… 95
5.5.3.4 StableBuffer管理器的模式识别操作… 95
5.5.3.5 StableBuffer管理器的刷新操作… 97
5.6 本章小结… 97
5.7 习题… 98
第6章 闪存数据库缓冲区管理… 99
6.1 缓冲区管理策略概述… 99
6.2 面向闪存的缓冲区管理… 100
6.2.1 重新设计面向闪存的缓冲区替换策略的必要性… 100
6.2.2 设计面向闪存的缓冲区替换策略的考虑因素… 101
6.2.3 设计面向闪存的缓冲区替换策略的关键技术… 102
6.3 代表性方法… 104
6.3.1 CFLRU.. 104
6.3.2 CFDC.. 106
6.3.3 LRU-WSR.. 107
6.3.4 CCF-LRU.. 109
6.3.5 AD-LRU.. 110
6.3.6 FOR.. 112
6.3.7 CASA.. 114
6.3.8 综合实例… 115
6.4 本章小结… 117
6.5 习题… 117
第7章 闪存数据库索引… 118
7.1 基于日志的B-树索引… 118
7.1.1 B-树… 118
7.1.2 闪存中基于日志的B-树索引… 119
7.2 B+-树索引… 122
7.2.1 B+-树… 122
7.2.2 闪存中的B+-树索引… 123
7.2.3 自适应B+-树索引… 124
7.2.3.1 FlashDB概述… 124
7.2.3.2 自适应B+-树… 125
7.2.3.3 B+-树节点大小的选择… 127
7.2.3.3.1 B+-树节点大小对性能的影响… 127
7.2.3.3.2 FlashDB中确定B+-树节点大小的方法… 129
7.3 FD-树… 130
7.4 LA-树… 131
7.4.1 LA-树的设计思想… 131
7.4.2 LA-树索引结构… 132
7.5 本章小结… 133
7.6 习题… 134
第8章 闪存数据库查询处理… 135
8.1 PAX页布局模型… 135
8.1.1 NSM和DSM模型… 135
8.1.1.1 NSM和DSM模型概述… 135
8.1.1.2 NSM模型存储原理… 136
8.1.1.3 DSM模型存储原理… 137
8.1.2 PAX模型… 137
8.1.2.1 PAX模型存储原理… 137
8.1.2.2 PAX、NSM和DSM的特性比较… 139
8.1.2.3 PAX模型在闪存上可以发挥更好的性能… 140
8.2 连接索引和Jive连接算法… 140
8.2.1.1 概述… 140
8.2.1.2 Jive连接算法的步骤… 141
8.2.1.3 Jive连接算法的一个实例… 142
8.3 基于PAX的RARE连接算法… 146
8.3.1.1 一趟扫描… 146
8.3.1.2 多趟扫描… 147
8.3.1.3 (1+ε)趟RARE连接算法… 148
8.3.1.4 2趟RARE连接算法… 149
8.4 基于PAX模型和连接索引的FlashJoin. 150
8.5 DigestJoin. 151
8.5.1 概述… 151
8.5.2 算法代价分析… 152
8.5.3 页抓取问题复杂度分析… 155
8.5.4 解决页抓取问题的启发式算法… 156
8.6 本章小结… 157
8.7 习题… 157
第9章 闪存数据库事务管理… 158
9.1 事务的概念… 158
9.2 传统的事务恢复机制… 158
9.2.1 基于日志的恢复方法… 159
9.2.2 基于影子页的恢复方法… 159
9.3 传统的事务恢复机制在闪存数据库中的表现… 159
9.4 代表性方法… 159
9.4.1 Transactional FTL. 160
9.4.2 TxFlash. 161
9.4.3 Flag Commit 164
9.4.4 IPL. 167
9.4.5 HV-Recovery. 169
9.5 本章小节… 171
9.6 习题… 171
第10章 基于混合存储系统的数据库… 173
10.1 闪存代替磁盘作为特种数据的存储介质… 173
10.1.1 存储事务日志… 173
10.1.1.1 同步事务日志成为数据库性能的瓶颈… 173
10.1.1.2 用闪存存储事务日志可以明显改进事务吞吐量… 174
10.1.2 存储回滚段… 174
10.1.3 存储中间结果… 175
10.1.3.1 连接算法介绍… 176
10.1.3.1.1 块嵌套循环连接… 176
10.1.3.1.2 归并排序连接… 177
10.1.3.1.3 哈希连接… 178
10.1.3.1.3.1 内存中的哈希连接… 178
10.1.3.1.3.2 Grace哈希连接… 178
10.1.3.1.3.3 混合哈希连接… 179
10.1.3.2 采用固态盘存储连接算法的临时结果… 179
10.1.3.3 采用固态盘可以提升归并排序连接算法性能的原因分析… 180
10.2 闪存作为介于磁盘和内存之间的缓存… 181
10.2.1 典型应用… 181
10.2.1.1 作为数据库系统的二级缓存… 181
10.2.1.2 作为数据仓库的更新缓存… 183
10.2.2 5分钟规则… 184
10.2.3 FaCE. 185
10.2.3.1 相关研究工作的不足之处… 186
10.2.3.2 FaCE的设计思想… 186
10.2.3.3 FaCE的基本框架… 187
10.2.3.4 FaCE的设计策略… 188
10.2.3.5 FaCE的恢复… 190
10.3 基于数据访问模式的混合存储系统… 191
10.3.1 基于对象放置顾问的混合存储系统… 191
10.3.2 基于双状态任务系统的混合存储系统… 192
10.3.3 基于垂直分区的混合存储系统… 194
10.3.3.1 系统概述… 194
10.3.3.2 离线分区系统… 194
10.3.3.2.1 工作负载统计… 194
10.3.3.2.2 NP-完全问题的证明… 195
10.3.3.2.3 解决分区问题的动态规划算法… 197
10.4 基于语义信息的系统框架hStoreage-DB.. 197
10.4.1 其他混合存储系统的不足… 197
10.4.2 hStoreage-DB的设计思路… 198
10.4.3 hStoreage-DB的技术挑战和解决方案… 199
10.4.4 QoS策略… 199
10.4.4.1 QoS策略概述… 199
10.4.4.2 混合存储系统的QoS策略… 200
10.4.4.3 针对不同类型的请求的QoS策略… 200
10.4.4.3.1 顺序请求… 200
10.4.4.3.2 随机请求… 200
10.4.4.3.3 临时数据请求… 201
10.4.4.3.4 更新请求… 201
10.5 本章小结… 201
10.6 习题… 201
第11章 闪存数据库实验环境的搭建… 202
11.1 使用闪存模拟器开展实验… 202
11.1.1 Flash-DBSim介绍… 202
11.1.2 Flash-DBSim体系架构… 202
11.1.3 Flash-DBSim的下载和简要说明… 204
11.1.4 使用Flash-DBSim模拟器开展相关实验… 204
11.1.4.1 使用Visual Studio开发工具打开解决方案… 204
11.1.4.2 模拟器的参数设置… 205
11.1.4.3 实例：测试LRU算法的性能… 205
11.1.4.3.1 LRU算法性能测试的基本步骤… 205
11.1.4.3.2 LRU算法的数据结构… 206
11.1.4.3.3 LRU算法的成员函数… 207
11.1.4.4 测试自己的缓冲区替换算法的性能… 208
11.2 在PostgreSQL开源数据库的真实环境下开展实验… 208
11.2.1 在DBMS真实环境下开展实验的必要性和可行性… 208
11.2.2 在PostgreSQL下开展实验之前需要回答的一些问题… 209
11.2.3 使用PostgreSQL 开展缓冲区替换算法的步骤… 209
11.2.4 PostgreSQL的下载和安装… 210
11.2.4.1 PostgreSQL的下载… 210
11.2.4.2 PostgreSQL的安装和配置… 210
11.2.5 使用BenchmarkSQL测试性能… 211
11.2.5.1 BenchmarkSQL的下载和安装… 211
11.2.5.2 BenchmarkSQL的使用方法… 211
11.2.5.3 获取测试结果数据… 212
11.2.6 删除 PostgreSQL数据库… 213
11.2.7 修改PostgreSQL的缓冲区替换算法… 213
11.2.7.1 修改PostgreSQL缓冲区替换算法的预备知识… 213
11.2.7.1.1 PostgreSQL 缓存替换算法的核心函数… 214
11.2.7.1.2 PostgreSQL 中LRU算法的实现… 214
11.2.7.2 修改PostgreSQL 缓冲区替换算法的步骤… 215
11.2.7.3 修改PostgreSQL实现CFLRU 算法… 215
11.3 本章小结… 217
11.4 习题… 217
第三篇 基于闪存的其他存储篇… 218
第12章 基于闪存的键值存储… 219
12.1 基于闪存的键值存储的应用领域… 219
12.2 相关研究… 219
12.2.1 FlashStore. 219
12.2.2 SkimpyStash. 221
参考文献… 223