Using B+-Trees in a Two-Disk Single Processor Architecture to Efficiently Process . . .

In this paper we address the problem of indexing spatial data, in particular two dimensional rectangles. We propose an approach which uses two B + -trees, each of them indexing the projected sides of the given rectangles. The approach, which we name 2dMAP21, can also be easily parallelized using two disks -- but still a single processor -- each holding the trees indexing the projected sides on either axes. We focus on queries of the type "find all rectangles included within another (reference) rectangle". Nevertheless, 2dMAP21 can processe other types of queries as well. We compare our approach to the R -tree, known as the most efficient R-tree derivative. Our investigation shows that, if the queries have the same spatial distribution of the data, the non-parallel 2dMAP21 may be a competitive alternative to the R -tree in some cases, whereas the parallelized version of 2dMAP21 outperforms that structure virtually always. 2dMAP21 may consume a little more or less storage space t..