Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: Grid Files and R-Trees

Re: Grid Files and R-Trees

From: Benjamin Johnston <superhero_at_benjaminjohnston.com.au>
Date: Sat, 28 Dec 2002 11:21:38 +1000
Message-ID: <7T6P9.10967$jM5.32038@newsfeeds.bigpond.com>


> Hi all.
> I'am interested in the grid file concept, as discussed in "The Grid File:
An
> Adaptable, Symmetric multkey file structure"by Niwvergelt, H.
HinterBerger,
> Sevcik. I'am also interested in the R-Tree, and belive they are related.
>
> I'am interested in how it can be adapted for Database management systems,
> what benefits over the B-Tree is achieved?

I believe some of the advantages are stated in the paper. Namely that only 2 disk accesses are required, and the preservation of structure.

Of course, Grid files and R-Trees are multidimensional data structures, whereas the B-Tree is a single dimensional data structure.

B-Trees aren't designed for accessing spatial data (well, without first using a transformation such as a Z-ordering).

Why not draw out a sample grid, and a sample R-tree, and consider the type of queries (point? window? sort?) you need to support and see how they compare (disk space, insert/delete/read time, disk accesses) when you "manually query" the structures?

> What the differance between the
> grid file and an R-Tree?

Grid files are like a large, sparse, matrix/array, Whereas R-Trees are trees.

I would tend to say that there are so many differences, that a better question might be what they have in common: they're both multidimensional structures, they both index the actual data as opposed to space (ie. it matters, but not all that much, how the data is distributed).

-Benjamin Johnston Received on Fri Dec 27 2002 - 19:21:38 CST

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US