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

<ul>
<li><p>Lars Arge.
<a href="http://www.daimi.au.dk/~large/Paperpages/dshandbook02.htm">External memory data structures</a>.  <em>Handbook of Massive Data Sets</em> (James Abello, Panos M. Pardalos, and Mauricio G. C. Resende, eds.), 313-357.  Kluwer Academic Publishers, 2002.  <strong><em>See especially sections 5 and 6.</em></strong></p></li>
<li><p>Jeffrey Scott Vitter.  <a href="http://www.nowpublishers.com/product.aspx?product=TCS&amp;doi=0400000014">Algorithms and data structures for external memory</a>.
<em>Foundations and Trends in Theoretical Computer Science</em> 2(4): 305–474, 2008. 
<strong><em>See especially section 12.</em></strong></p></li>
</ul>

CC BY-SA 3.0
2013-02-11T17:01:22.737Z
2013-02-11T17:01:22.737Z
Jeffε
<p>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.</p>

<p>The idea is a 'stacked' <a href="http://en.wikipedia.org/wiki/B+_tree" rel="nofollow">B+ tree</a> 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 <a href="http://en.wikipedia.org/wiki/Range_tree" rel="nofollow">Range Trees</a> 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.</p>

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

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

<p>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.</p>

<p>Has anyone written / designed a similar search algorithm before?</p>

<ds.data-structures><tree>
Multidimensional B+ tree
max
# Multidimensional B+ tree

(Asked by: username_0 on 2013-02-11)

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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Range_tree) 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?

**Tags:** ds.data-structures, tree


---

## 1 answers

### Answer by username_1 on 2013-02-11. Score: 13 | Accepted answer

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](http://www.daimi.au.dk/~large/Paperpages/dshandbook02.htm). *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](http://www.nowpublishers.com/product.aspx?product=TCS&doi=0400000014).
  *Foundations and Trends in Theoretical Computer Science* 2(4): 305–474, 2008.
  ***See especially section 12.***


---

