Tree Indexing on Solid State Drives

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-beforewrite
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.