FD-Tree: a Tree Index on Solid State Drives

DOWNLOAD

The latest version of FD-tree is available for download:
FD-tree code base.

Copyright (c) 2010, Hong Kong University of Science and Technology. All rights reserved.

The license is a free non-exclusive, non-transferable license to reproduce, use, modify and display the source code version of the Software, with or without modifications solely for non-commercial research, educational or evaluation purposes. The license does not entitle Licensee to technical support, telephone assistance, enhancements or updates to the Software. All rights, title to and ownership interest in the Software, including all intellectual property rights therein shall remain in HKUST.

OVERVIEW

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.

PUBLICATION

Tree Indexing on Solid State Drives
Proceedings of the VLDB Endowment (VLDB), journal track, Vol 3, 2010

Tree Indexing on Flash Disks
IEEE International Conference on Data Engineering (ICDE), short paper, 2009

PEOPLE

Yinan Li, Bingsheng He, Jun Robin Yang, Qiong Luo, Ke Yi