Re: Grid Files and R-Trees
Date: Thu, 2 Jan 2003 12:38:21 +0100
Message-ID: <av17mk$jsp$07$1_at_news.t-online.com>
Hi Ian,
a significant difference is, that the grid-file guarantees the "2 disc access" to solve a a single point-query. while the R-tree does not.
On the other hand in some sense the grid-file can be looked at, as some kind of tree with depth 2. Therefore only a limited number of data can be stored in a grid-file, while an unlimited amount of data can be stored in an R-tree.
If you are generally interested in multidimensional datastructures, you should also examine the kdB-tree.
> what benefits over the B-Tree is achieved?
You can find this out, if you compare binary search trees for
one-dimensional data with the kd-tree (a binary search-structure for
multidimensional data)
In one-dimensional case, you can "split" the one-dimension so that exactly
half of the data lies to the left of the split-point and the other half lies
at the right of split-point. Subsequent "splits" of the one-dimensional
room result in binary tree (or a partition of the one-dimensional room). The
order in which "splits" are executed does not matter in this case.
Therefore, you can "rotate" nodes of the binary tree to obtain a balanced
tree. If you are using a B-tree instead of a binary tree, you can also use
this fact, to change the time-order of "splitpoints" an so obtain a
"balanced" multiway-tree - the B-tree.
This is not true if you split multidimensional room:
If you first split along the x-axis and then along the y-axis, you get a
(binary) tree (a socalled kd-tree). It is not possible to get the same
partitioning of the two-dimwensional room, if you first split along the
y-axis and then along the x-axis.
That's the reason, why kd-trees cannot be extented to Multiway-Searchtrees in the same way, as one-dimensional binary searchtrees can be extendet to B-trees.
Gert
Gert Gurrath Software-Entwicklung
Bukarester Str. 10
D-97084 Würzburg
Tel.: -49 -931 / 666 81 23
Fax: -49 -931 / 666 81 26
email: gg_at_gurrathsoftware.de
"Ian" <kellizer(NOSPAM)_at_hotmail.com> schrieb im Newsbeitrag
news:auhlrn$ll2$1_at_news5.svr.pol.co.uk...
> 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? What the differance between the
> grid file and an R-Tree?
>
> would anyone have implemented the structure? Or know of any source code on
> the net?
>
> I would like to implement the grid file in Java?
>
> Kind Regards
>
> Ian
>
>
Received on Thu Jan 02 2003 - 12:38:21 CET