# Multidimensional B+ tree

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?

-
can you implement the multidimensional b tree? –  user14240 Mar 18 '13 at 8:51