Modularizing B+-trees: Three-Level B+-trees Work Fine.
Shigero Sasaki, Takuya Araki · 2013
The objective of this research is to improve the single-thread performance of a B+-tree in memory. Existing works have been utilized changes in hardware for the performance improvement. While utilizing these works, we modularize B+trees in memory especially for write-intensive workloads. The modularization is mainly aimed at utilizing the difference in read/write ratio between levels, which is large for write-intensive workloads. In this paper, we show how to modularize B+-trees and effective selections of algorithms and the node size at each level. The cost to switch algorithms is minimized because algorithms at a level are statically defined at compile time. The best selection in this paper formed three-level B+-trees and achieved two- or threefold performance improvement over a typical implementation of a B+-tree. In the three-level B+-trees, we perform linear search on small unsorted leaf nodes, and interpolation search on the large sorted root node, and linear search on small sorted internal nodes. 1.