基于NAND闪存的数据库索引机制研究与改进

发布时间：2018-05-12 15:28

本文选题：NAND闪存 + BFTL　；参考：《东北大学》2013年硕士论文

【摘要】：在过去的几十年,CPU的处理速度提高近600倍,而磁盘的读写速度只提升了不足10倍,低速的磁盘(毫秒级)已经成为制约系统性能提升的瓶颈。高速的NAND闪存(微秒级)已经成为磁盘的理想替代设备。然而由于NAND闪存具有读写速度不对称、块擦除次数有限等特性,现有的数据库索引无法充分发挥闪存的存储优势。因此,基于NAND闪存的物理特性重新构建一种高效的数据库索引结构是一个急需解决的问题。本文在参阅大量国内外相关文献的基础上,针对B-Tree“级联更新”导致的低性能问题和BFTL“随机存取”导致的大量闪存写操作问题,提出了一种更适合闪存的Optimized BFTL索引机制。Optimized BFTL是对BFTL的改进,该机制包含3个策略：通过暂存更新、冗余消除的思路,Optimized BFTL改进了索引缓存区Index Buffer的存储策略；提出了待提交序列选择算法,通过批量提交节点序列,消除了BFTL的“随机存取”现象,从而大大减少了闪存写操作次数；设计并实现的叶子节点头及其相关算法,提高了搜索算法的性能。此外,对Optimized BFTL的全局查询、更新算法进行了设计和实现。最后,依次对上述策略进行模拟实验,仿真结果表明,与之前的BFTL相比,该索引机制插入操作所引起的闪存写次数仅为前者的22.3%,因此本文实现的索引机制能够大量减少闪存写次数,具有进一步研究和应用的价值。
[Abstract]:In the past few decades, the processing speed of CPU has increased nearly 600 times, while the read and write speed of disk has increased by less than 10 times. Low speed disk (millisecond level) has become the bottleneck of system performance improvement. High-speed NAND flash memory (micro-second) has become an ideal alternative to disk. However, due to the asymmetry of reading and writing speed of NAND flash memory and the limited number of block erasures, the existing database indexes can not give full play to the storage advantages of flash memory. Therefore, it is an urgent problem to reconstruct an efficient database index structure based on the physical properties of NAND flash memory. Based on a large number of domestic and foreign literatures, this paper aims at the problems of low performance caused by B-Tree cascading update and a large number of flash write operations caused by BFTL random access. In this paper, a more suitable Optimized BFTL index mechanism, optimized BFTL, is proposed, which is an improvement on BFTL. The mechanism consists of three strategies: the storage strategy of index cache Index Buffer is improved by using temporary memory update, redundancy elimination and optimized BFTL; This paper proposes an algorithm for selecting the sequence to be submitted, which eliminates the "random access" phenomenon of BFTL by submitting node sequences in batches, thus greatly reduces the number of flash write operations, and designs and implements the leaf nods and their related algorithms. The performance of search algorithm is improved. In addition, the global query and update algorithm of Optimized BFTL are designed and implemented. Finally, the simulation results show that, compared with the previous BFTL, the simulation results show that, The number of flash writes caused by the insertion operation of this indexing mechanism is only 22.3 times of that of the former, so the index mechanism implemented in this paper can greatly reduce the number of flash memory writes, which has the value of further research and application.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP333

【相似文献】