- 160 views
- 287 downloads
FAR-Tree: A Spatial Index For Solid State Drives
-
- Author / Creator
- Jiang, Feng
-
Solid state drives (SSDs) are becoming more common with their main advantage of faster reads compared to hard disk drives (HDDs). However, writes are relatively slower, indeed asymmetric with respect to reads, unlike in HDDs where read and write are comparable. Current indexing structures were designed for HDDs and aim at reducing the number of reads at query time. In SSDs, index writes may impact the overall query performance in the presence of updates. Thus, we focus on minimizing the number of writes during index update, considering the R-tree in particular, given that it is an ubiquitous and update-expensive indexing structure. We propose the FAR-tree (for Flash Aware R-tree) which aims at avoiding node splits by building a chain of nodes on leaf nodes. Our experiments using real and synthetic datasets show that the FAR-tree can yield a more update-efficient index at the cost of some overhead at query time.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2013
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.