Research And Improvement Of Database Index Based On NAND Flash

In the past decades, CPU speed increased nearly 600 times, but disk speed only improved 10 times, disk has become the bottleneck of system performance. Owing to its microsecond speed, flash memory has become an ideal substitution of disk. However, flash memory has several critical drawbacks such as long latency of write operation and a short life cycle. Directly deploying the traditional index to flash memory fails to take full advantage of NAND flash. How to build an efficient database index based on the flash memory is becoming an urgent problem that needs to be solved.Firstly, this thesis deeply studied the traditional mechanism of database index based on NAND flash. After pointing out the defects and shortcomings of BFTL, this thesis proposes a new index structure named Optimized BFTL which is an improvement of BFTL.Optimized BFTL designs three improved policies:through temporarily storing update operations and redundancy elimination method, Optimized BFTL improves the Index Buffer's storage strategy which can effectively reduce redundant update operations and page write operations; this thesis designs a CS(the commit index unit set selection algorithm) algorithm based on greedy strategy, CS algorithm eliminates the "random access" phenomenon of BFTL and greatly reduces the count of page write operation; thirdly, in order to enhance the efficiency of search algorithm, this thesis proposes a LNH structure and implements its related algorithms. Through the above three improvements, Optimized BFTL can better adapt to physical properties of NAND flash.Finally, the simulation experiment shows that the count of page-write operation caused by Optimized BFTL is only 22.3% of BFTL. Optimized BFTL can significantly reduce the page-write count and has a better search performance than BFTL, which has the further research and application value.