论文部分内容阅读
闪存是一种新型的电可擦除可编程只读存储器，具有非易失、读写速度快、抗震性能好、低功耗、体积小等特性。随着闪存容量的不断增加和价格的逐渐下降，闪存相对于传统机械硬盘具有了更加明显的竞争优势，已经广泛应用于嵌入式系统、航空航天、消费电子等领域。目前，随着闪存的不断发展，已经有越来越多的企业开始使用闪存作为底层的存储设备。 但是，闪存设备自身也存在一些缺点:(1)闪存的单位容量价格仍然高于传统的机械硬盘且生命周期更短;(2)闪存中数据的擦除是以块为单位的，一个数据块中包含固定数量的连续页，而闪存数据的读写是以页为单位的;(3)闪存更新数据的方式为异地更新;(4)闪存的读写速度是不一致的，其读操作由于不需要寻道时间，因而具有良好的读取数据的性能，但其写操作和擦除操作相对于读操作而言则很慢。数据库系统在选择闪存作为存储设备时，如果使用传统的数据库B+树索引结构，往往无法充分发挥闪存的优势，因而需要针对闪存独有的特性而进行一定的优化。已有的基于闪存的数据库索引结构，如BFTL、IBSF以及LA-Tree等，都没有考虑闪存的异地更新以及写前擦除等特性，因而无法使闪存数据库系统中获得更好的整体性能。 本文首先提出了一种朴素的HNLBI(Head Node List B+-Tree Indexing)索引，该索引结构大量减少了缓冲区中的冗余信息，提高了缓冲区的利用效率，同时通过头节点的使用更好地组织了缓冲区中的更新信息，降低了缓冲区相关操作的时间损耗，并且提出了基于最长更新信息链表的缓冲区替换算法，减少了闪存写操作的次数。但是HNLBI索引并没有考虑到数据访问局部性的特点，当B+树索引中某些结点被多次访问时，有可能造成该结点被频繁换入换出缓冲区的情况。因此本文提出了针对HNLBI的改进的索引结构，即CF-HNLBI(Cold-First HeadNode List B+-Tree Indexing)索引，它将缓冲区分为冷区和热区，当缓冲区满时，替换操作仅发生在冷区，这使得被频繁访问的节点有更多的机会驻留在缓冲区中，避免了该类节点被频繁地换入和换出，提高了缓冲区的利用效率，也有效地减少了闪存写操作的次数。本文也通过大量实验证明，CF-HNLBI索引相对于其它已有的索引结构，可以使基于闪存的数据库系统获得更好的性能。