We propose BS-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 BS-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 BS-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.

翻译：本文提出BS-tree，一种基于内存的B+树实现，它沿用了磁盘索引的结构（即平衡多路树），并将节点大小设置为一个内存块，该内存块可通过SIMD指令实现快速并行处理。BS-tree的一个新颖特性是通过复制键值在节点内部引入间隙（未使用位置）。这使得（i）在每个节点内实现无分支的SIMD搜索，以及（ii）在节点中实现无需键值移位操作的无分支更新。我们实现了一种帧参考（FOR）压缩机制，该机制允许节点具有可变容量，并能显著降低BS-tree的内存占用。我们在不同查询与更新负载下，将本方法与现有主内存索引及学习型索引进行比较，证明了其在单线程与多线程处理中相较于先前工作的鲁棒性与优越性。