B S -tree: A gapped data-parallel B-tree
Dimitrios Tsitsigkos, Achilleas Michalopoulos, Nikos Mamoulis, Manolis Terrovitis · 2025
Read B S -tree: A gapped data-parallel B-tree by Dimitrios Tsitsigkos, Achilleas Michalopoulos, Nikos Mamoulis, Manolis Terrovitis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01180.txt.
Introduction
Dimitrios Tsitsigkos, Achilleas Michalopoulos, Nikos Mamoulis, and Manolis Terrovitis present a faster in-memory index for data, in a research paper from 2025. The index is based on the B-tree, a classic balanced tree used in databases. Node sizes are set to blocks that modern chips can scan in parallel.
Their design leaves gaps inside each node by copying some key values. Those gaps let searches and updates run without branching or shifting keys around. A compression trick also shrinks the memory used. In tests with mixed queries and updates, the index beat both classic in-memory indexes and newer learned ones, in single and multi-threaded runs.
Catalog record
| CREATOR | Dimitrios Tsitsigkos, Achilleas Michalopoulos, Nikos Mamoulis, Manolis Terrovitis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-01180
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
B S -tree: A gapped data-parallel B-tree Dimitrios Tsitsigkos, Achilleas Michalopoulos, Nikos Mamoulis, Manolis Terrovitis Abstract . We propose B S -tree, an in-memory implementation of the B + -tree that adopts the structure of the disk-based index (i.e., a balanced, multiway tree), setting the node size to a memory block that can be processed fast and in parallel using SIMD instructions. A novel feature of the B S -tree is that it enables gaps (unused positions) within nodes by duplicating key values. This allows (i) branchless SIMD search within each node, and (ii) branchless update operations in nodes without key shifting. We implement a frame of reference (FOR) compression mechanism, which allows nodes to have varying capacities, and can greatly decrease the memory footprint of B S -tree. We compare our approach to existing main-memory indices and learned indices under different workloads of queries and updates and demonstrate its robustness and superiority compared to previous work in single- and multi-threaded processing. 1. Introduction The B + -tree is the dominant indexing method for DBMSs, due to its low and guaranteed cost for (equality and range) query processing and updates. It was originally proposed as a disk-based index, where the objective is to minimize the I/O cost of operations. As memories become larger and cheaper, main-memory and hardware-specific implementations of the B + -tree ( Boyar and Larsen, 1992 ; Lehman and Carey, 1986 ; Rao and Ross, 1999 ; Rao and Ross, 2000 ; Bohannon et al., 2001 ; Kim et al., 2010 ; Fix et al., 2011 ; Levandoski et al., 2013 ; Kaczmarski, 2012 ; Shahvarani and Jacobsen, 2016 ; Yan et al., 2019 ; Kwon et al., 2023 ) , as well as alternative access methods for in-memory data ( Morrison, 1968 ; Askitis and Sinha, 2010 ; Böhm et al., 2011 ; Kissinger et al., 2012 ; Mao et al., 2012 ; Leis et al., 2013 ; Zhang et al., 2016 ; Binna et al., 2018 ; Zhang et al., 2018 ) have been proposed. The optimization objective in all these methods is minimizing the computational cost and cache misses during search. More recently, learned indices ( Kraska et al., 2018 ; Galakatos et al., 2019 ; Ferragina and Vinciguerra, 2020 ; Ding et al., 2020a ; Zhang and Gao, 2022 ; Wu et al., 2022 ; Kipf et al., 2020 ; Wu et al., 2021 ; Li et al., 2023 ; Zhang et al., 2024 ) , which replace the inner nodes of the B + -tree by ML models have been suggested as a way for reducing the memory footprint of indexing and accelerating search at the same time. In this paper, we propose B S -tree, a B + -tree for main memory data, which is optimized for modern commodity hardware and data parallelism. B S -tree adopts the structure of the disk-based B + -tree (i.e., a balanced, multiway tree), setting the node size to a memory block that can be processed in parallel. At the heart of our proposal lies a data-parallel successor operator ( succ ), implemented using SIMD, which is applied at each tree level for branching during search and updates and for locating the search key position at the leaf level. To facilitate fast updates, without affecting SIMD-based search, we propose a novel implementation for gaps (unused positions) by duplicating keys. The main idea is that we write in each unused slot the next used key value in the node or a global MAXKEY value if all subsequent slots are unused. Our B S -tree construction algorithm initializes sparse leaf nodes with intentional gaps in them, in order to (i) delay possible splits and (ii) reduce data shifting at insertions. Splitting also adds gaps proactively. Finally, we apply a frame-of-reference (FOR) based compression method that allows nodes that use fixed-size memory blocks to have varying capacities , which saves space and increases data parallelism. The computational cost of search and update operations in B S -tree is O(\log_{f}n) , where f is the capacity of the nodes, assuming that f is selected such that each node can be processed by a (small) constant number of SIMD instructions. Novelty and contributions. There already exist several SIMD-based implementations of B-trees and k-ary search ( Schlegel et al., 2009 ; Kim et al., 2010 ; Shahvarani and Jacobsen, 2016 ; Yan et al., 2019 ; Kwon et al., 2023 ; Graefe, 2024 ) . In addition, updatable learned indices ( Ding et al., 2020a ) use gaps to facilitate fast updates. Finally, key compression in B-trees has also been studied in previous work ( Bohannon et al., 2001 ) . To our knowledge, our proposed B S -tree is the first B + -tree implementation that gracefully combines all these features, achieving at the same time minimal storage and high throughput. In particular, the use of duplicate key vales in unused gaps/slots allows (i) branchless, data-parallel SIMD search at each node, and (ii) efficient key insertions and deletions with limited shifting of keys within each node. In addition, our compression scheme allows for direct application of data-parallel search on compressed nodes. To our knowledge, using duplicate keys in gaps within each node for efficient data-parallel search and updates at the same time is novel and has not been supported by previous B-tree implementations ( Graefe, 2024 ) . We implement a version of optimistic lock coupling in B S -tree for concurrency control and extensively compare B S -tree with open-source single- and multi-threaded implementations of state-of-the-art non-learned and learned indices on widely used real datasets, to find that B S -tree and its compressed version consistently prevail in different workloads of reads and updates, typically achieving 1.5x-2x higher throughput than the best competitor. Outline Section 2 presents related work. The B S -tree is described in Section 3 and its updates and construction in Section 4 . Section 5 describes B S -tree compression. Implementation details and concurrency control are discussed in Section 6 and 7 , respectively. Section 8 includes our experimental evaluation. We conclude in Section 9 . 2. Related Work 2.1. B-tree The B + -tree is considered the de-facto access method for relational data, having substantial advantages over hash-based indexing with respect to construction cost, support of range queries, sorted data access, and concurrency control ( Graefe, 2011 ; Elmasri and Navathe, 1989 ; Graefe, 2024 ) . As memory sizes grow, the interest has shifted to in-memory access methods ( Zhang et al., 2015 ) . Rao and Ross ( Rao and Ross, 1999 ) were the first to consider the impact of cache misses in memory-based data structures; they proposed Cache-Sensitive Search Trees (CSS-trees), in which every node has the same size as the cache-line of the machine and does not need to keep pointers for the links between nodes, but offsets that can be calculated by arithmentic operations. Rao and Ross ( Rao and Ross, 2000 ) also proposed the Cache Sensitive B + -tree (CSB+tree), which achieves cache performance close to CSS-Trees, while having the advantages of a B + -tree. Chen et al. ( Chen et al., 2001 ; Chen