Accelerating Braided B+ Tree Searches on a GPU with CUDA

Jordan Fix, Andrew Wilkes, Kevin Skadron
University of Virginia Department of Computer Science, Charlottesville, VA 22904
2nd Workshop on Applications for Multi and Many Core Processors: Analysis, Implementation, and Performance (A4MMC), in conjunction with ISCA, 2011


   title={Accelerating Braided B+ Tree Searches on a GPU with CUDA},

   author={Fix, J. and Wilkes, A. and Skadron, K.},



Download Download (PDF)   View View   Source Source   



Previous work has shown that using the GPU as a brute force method for SELECT statements on a SQLite database table yields significant speedups. However, this requires that the entire table be selected and transformed from the B-Tree to row-column format. This paper investigates possible speedups by traversing B+ Trees in parallel on the GPU, avoiding the overhead of selecting the entire table to transform it into row-column format and leveraging the logarithmic nature of tree searches. We experiment with different input sizes, different orders of the B+ Tree, and batch multiple queries together to find optimal speedups for SELECT statements with single search parameters as well as range searches. We additionally make a comparison to a simple GPU brute force algorithm on a row-column version of the B+ Tree.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: