Tree indexing on solid state drives
Tree indexing on solid state drives
复制标题
DOI：
10.14778/1920841.1920990
复制
发表时间：
2010-09
影响因子：
2.5
通讯作者：
Yinan Li;Bingsheng He;Jun Yang;Qiong Luo;K. Yi
中科院分区：
文献类型：
--
作者：
Yinan Li;Bingsheng He;Jun Yang;Qiong Luo;K. Yi
大型闪存盘或固态驱动器（SSD）由于其高随机读取性能、低能耗和其他特性，已成为磁性硬盘的有吸引力的替代品。然而，由于写前擦除机制，闪存盘上的写入（尤其是小型随机写入）本质上比读取慢得多。为了解决这种不对称的读写速度在闪存盘上的树索引，我们提出了FD树，设计与对数方法和分数级联技术的树索引。使用对数方法，FD树由头树--位于顶部的小B+树和位于底部的几个级别的大小递增的排序运行组成。这种设计针对闪存盘进行了写优化;特别是，索引搜索可能会经过更多的级别或访问更多的节点，但随机写入仅限于一个小区域-头树，随后通过合并到较低的运行中转换为顺序写入。使用分数级联技术，我们在较低级别的运行中存储指针，称为围栏，以加快搜索速度。给定n个条目的FD树，我们分析表明，它执行O（logB n）的顺序I/O的更新，并完成O（logB n）的随机I/O的搜索，其中B是闪存页面大小。我们评估FD树的比较与代表B+树的各种工作负载下的三个商品闪存固态硬盘的变种。我们的研究结果表明，FD-树具有类似的搜索性能的标准B+-树，和类似的更新性能的写优化的B+-树的变体。因此，FD树在闪存盘和磁盘上的整体性能上优于其他B+树索引变体。
Large flash disks, or solid state drives (SSDs), have become an attractive alternative to magnetic hard disks, due to their high random read performance, low energy consumption and other features. However, writes, especially small random writes, on flash disks are inherently much slower than reads because of the erase-before-write mechanism. To address this asymmetry of read-write speeds in tree indexing on the flash disk, we propose FD-tree, a tree index designed with the logarithmic method and fractional cascading techniques. With the logarithmic method, an FD-tree consists of the head tree -- a small B+-tree on the top, and a few levels of sorted runs of increasing sizes at the bottom. This design is write-optimized for the flash disk; in particular, an index search will potentially go through more levels or visit more nodes, but random writes are limited to a small area -- the head tree, and are subsequently transformed into sequential ones through merging into the lower runs. With the fractional cascading technique, we store pointers, called fences, in lower level runs to speed up the search. Given an FD-tree of n entries, we analytically show that it performs an update in O(logB n) sequential I/Os and completes a search in O(logB n) random I/Os, where B is the flash page size. We evaluate FD-tree in comparison with representative B+-tree variants under a variety of workloads on three commodity flash SSDs. Our results show that FD-tree has a similar search performance to the standard B+-tree, and a similar update performance to the write-optimized B+-tree variant. As a result, FD-tree dominates the other B+-tree index variants on the overall performance on flash disks as well as on magnetic disks.