I've got an idea for indexing multidimensional data. I haven't been able to find anything equivalent and am wondering if it is indeed a novel approach.

The idea is a 'stacked' B+ tree implementation where the leaf nodes contain both the dimension data and a pointer to the next dimension. Each dimension is in itself a B+ tree. It is similar to how Range Trees link/point to the next dimension. However, it is different from a Range Tree by using a B+ tree instead of a straight binary search tree.

Also, the elements in each B+ tree layer are unique and are stored with the number of records belonging to each leaf value.

I believe the search complexity would be $(\sum_{i=0}^{d-1} \log _{B} \text{card}(n^{i})) + k$.

Where $\log _{B}$ comes from the branching factor of the B+ tree, $\text{card}(n^{i})$ is the number of unique elements stored for each dimension and $d$ is the number of dimensions stored. $k$ is simply the number of elements returned.

Has anyone written / designed a similar search algorithm before?

  • $\begingroup$ can you implement the multidimensional b tree? $\endgroup$
    – user14240
    Mar 18, 2013 at 8:51

1 Answer 1


No, this is not new; range searching with multilevel B-trees is completely standard. See, for example, the following surveys:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.