Tree Indexing on Flash Disks

MPhil Thesis Defence


Title: "Tree Indexing on Flash Disks"

By

Mr. Yinan Li


Abstract

Large flash disks 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 random writes, on the 
flash disk are inherently much slower than reads because of the 
erase-before-write mechanism. To address this asymmetry of read-write 
speeds in indexing on the flash disk, we propose the 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 a FD-tree of n entries, we analytically show that it supports 
updates in O(logBn) sequential I/Os and preserve the search efficiency in 
O(logBn)random I/Os, where B is the page size. We evaluate the FD-tree in 
comparison with representative B+-tree variants under a variety of 
workloads on both mid-class and high-end flash SSDs. Our results show that 
the 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 outperforms all these B+-tree index variants on both 
update- and search-intensive workloads.


Date:			Monday, 22 June 2009

Time:			10:00am-12:00noon

Venue:			Room 3494
 			Lifts 25-26

Committee Members:	Dr. Qiong Luo (Supervisor)
 			Prof. Dimitris Papadias (Chairperson)
 			Dr. Ke Yi


**** ALL are Welcome ****