Adapting Tree Structures for Processing with SIMD Instructions
Steffen Zeuch, Johann-Christoph Freytag, Huber, Frank · 2014
In this paper, we accelerate the processing of tree-based in-dex structures by using SIMD instructions. We adapt the B+-Tree and prefix B-Tree (trie) by changing the search al-gorithm on inner nodes from binary search to k-ary search. The k-ary search enables the use of SIMD instructions, which are commonly available on most modern processors today. The main challenge for using SIMD instructions on CPUs is their inherent requirement for consecutive memory loads. The data for one SIMD load instruction must be located in consecutive memory locations and cannot be scattered over the entire memory. The original layout of tree-based index structures does not satisfy this constraint and must be adapted to enable SIMD usage. Thus, we introduce two tree adaptations that satisfy the specific constraints of SIMD instructions. We present two di↵erent algorithms for trans-forming the original tree layout into a SIMD-friendly layout. Additionally, we introduce two SIMD-friendly search algo-rithms designed for the new layout. Our adapted B+-Tree speeds up search processes by a fac-tor of up to eight for small data types compared to the origi-nal B+-Tree using binary search. Furthermore, our adapted prefix B-Tree enables a high search performance even for larger data types. We report a constant 14 fold speedup and an 8 fold reduction in memory consumption compared to the original B+-Tree. 1.