Multidimensional B+ tree

Question

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?

Answer 1

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

• Lars Arge. External memory data structures. Handbook of Massive Data Sets (James Abello, Panos M. Pardalos, and Mauricio G. C. Resende, eds.), 313-357. Kluwer Academic Publishers, 2002. See especially sections 5 and 6.

• Jeffrey Scott Vitter. Algorithms and data structures for external memory. Foundations and Trends in Theoretical Computer Science 2(4): 305–474, 2008. See especially section 12.