Re: Data structure for indexing on multiple keys.
Date: Thu, 9 Sep 2004 18:58:09 +0100
Message-ID: <hj5qhc.ga.ln_at_ID-112571.user.uni-berlin.de>
> Please note that this is not about composite keys but supporting
>multiple keys for searching. Thanks in advance for inputs!
>
>Regards,
>Shankar
Hello,
it is ironic that you are posting from news.oracle.com and asking this.
There is an awful lot of these structures, each one intended for
different applications (for example, in-memory or filesystem-based?).
There is a somewhat old survey paper published in ACM Computing Surveys,
Volker Gaede, Oliver Günther
If you do not have access to this paper, try searching the web for the
following keywords. For main memory:
k-d Tree (Bentley)
For secondary storage:
k-d-B Tree (Robinson)
Multidimensional Access Methods
ACM Computing Surveys, Vol. 30, No. 2, June 1998
BSP Tree (Fuchs)
BD Tree (Ohsawa and Sakauchi)
Quadtree
LSD Tree (Henrich)
Buddy Tree (Seeger and Kriegel)
BANG File (Freeston)
hB Tree (Lomet and Salzberg)
BV Tree (Freeston)
R-Tree (Guttman)
R* Tree (Beckmann)
P-Tree (Jagadish)
P-Tree (Schiwietz)
SKD Tree (Ooi)
GBD Tree (Ohsawa and Sakauchi)
PLOP Hashing (Kriegel and Seeger)
Extended k-d Tree (Matsuyama)
R+ Tree (Stonebraker)
Cell Tree (Günther)
Multilayer Grid File (Six and Widmayer)
R-File (Hutflesz)
I think that k-d trees and k-d-B trees are the easiest to understand, the latter being a blend of the former and B-trees.
Regards.
José Juan Mendoza Rodríguez
let me=josejuanmr in
let privacy=lycos in
me_at_privacy.net
Received on Thu Sep 09 2004 - 19:58:09 CEST