Space-Efficient B Trees via Load-Balancing

Abstract We study succinct variants of B trees in the word RAM model that require $$s + o(s)$$ bits of space, where s is the number of bits essentially needed for storing keys and possibly other satellite values. Assuming that elements are sorted by keys (not necessarily in the order of their integer representations), our B trees support standard operations such as searching, insertion and deletion of elements. In some applications it is useful to associate a satellite value to each element, and to support aggregate operations such as computing the sum of values, the minimum/maximum value in a given range, or search operations based on those values. We propose a B tree representation storing n elements in $$s + \mathcal {O}(s / \lg n)$$ bits of space and supporting all mentioned operations in $$\mathcal {O}(\lg n)$$ time. Operations on integer-ordered keys and satellite values can be accelerated to $$\mathcal {O}(\lg n / \lg \lg n)$$ time if we use $$s + \mathcal {O}(s \lg \lg n / \lg n)$$ bits of space. The time is retained for special kind of aggregate functions that can be computed bit-parallel in constant time. For integer-ordered keys, we can also compress the space s to match compression measures using difference encoding of the keys while retaining the operational time complexities. For the last enhancement, we allow us to pre-compute tables of $$o(n)$$ bits.