BKD-Tree: Theory, Construction, Query, Update and Practical Compression Strategies for Large-Scale Numeric Range Search

The article begins by highlighting the importance of efficient range queries on large multidimensional numeric datasets in search engines and introduces BKD-Tree (Block‑K‑Dimension‑Balanced Tree) as a solution that combines the benefits of KD‑Tree and B‑Tree while supporting dynamic updates through a logarithmic method.

It defines the problem of retrieving all points whose x‑coordinate lies in (-3, 8) and y‑coordinate in (-5, 3) from a set of 2‑D points, and explains why traditional structures like BST, B‑Tree, or KD‑Tree are insufficient for massive, mutable data.

The core construction algorithm is illustrated with the recursive BuildBKD(A, k, leavesOffset, numLeaves) pseudocode, which decides split dimensions, computes leaf counts, and uses a specialized Select operation to partition data so that the first leftCount elements have split‑dim values not greater than the rest.

For leaf‑node storage, the article describes two compression schemes: WriteDocIds that selects among CONTINUOUS_IDS, BITSET_IDS, DELTA_16_STYLE, MERGE_24_STYLE, and SIMPLE_32_STYLE based on monotonicity and value range, and point‑value compression that distinguishes low‑cardinality (run‑length) and high‑cardinality (byte‑wise) cases using WriteLowCardSuffixes and WriteHighCardSuffixes respectively.

Query processing is modeled with a Visitor pattern; a BKDVisitor class defines methods to compare node bounds with the query range and to visit matching document IDs, enabling efficient pruning of the tree.

Dynamic updates are handled by the logarithmic method: new points are buffered in a fully binary tree in memory, and when the buffer fills, it is merged with existing on‑disk trees, effectively doubling the tree size while preserving fast updates.

To minimize storage, the index data (leaf block pointers, split dimensions, and split values) are packed using the RecursivePackIndex algorithm, which records split dimensions, common prefixes, and delta bytes in a compact byte stream, replacing explicit 64‑bit offsets with variable‑length encodings.

Finally, the article discusses practical deployment in the 58 search engine, including file organization (.bkd.data, .bkd.index, .bkd.meta), compression of both raw data and index structures, and an optimized merge strategy for one‑dimensional BKD trees using a priority queue to produce a globally sorted leaf block list.