闪存环境下B^+树索引重访

Revisit of B^+-tree index in flash-based environment

闪存容量的增大使在其上构建大型系统成为可能,如何构建闪存数据库也成为数据库的热点研究领域之一。索引结构是数据库中必不可少的结构之一,而B+树是最广泛使用的索引结构。这里对存储在闪存芯片模拟器及固态硬盘上的B+树性能进行了测试及分析。首先介绍了闪存的IO特点,并测试了固态硬盘的基本IO特性。接着,对B+树的插入和查询效率进行了详细测试。测试发现节点大小、缓存大小以及数据值的分布方式都会对B+树的性能带来很大影响。例如由于闪存的读取速度不对称,闪存的更新和查询操作最优块大小相差较大。这些测试结果为更好地在闪存上使用B+树索引,并进一步设计出更适合闪存的索引提供了指导。

The increment of flash memory devices provides opportunity for large flash-based applications, and hence flash based database has become one of the promising research areas. B ＋ -tree is the most widely adopted index, which is a fundamental structure for DBMS. The performance of B ＋ -tree stored on both flash chip simulator and SSD is both evaluated. The authors evaluated the basic IO features of SSD and compared it with the traditional hard disk, followed by the detailed testing result on the B＋ -tree. The results show that node size, buffer and data distribution have great effect on the performance of B ＋ -tree. Due to the asymmetry of flash input and output speed, the optimal node size of query and insertion are different from each other. These testing results will be a meaningful guidance for both application and improvement of B ＋ -tree.