Re: Data structure for indexing on multiple keys.

> 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
Multidimensional Access Methods
ACM Computing Surveys, Vol. 30, No. 2, June 1998

If you do not have access to this paper, try searching the web for the following keywords. For main memory:

k-d Tree (Bentley)
BSP Tree (Fuchs)
BD Tree (Ohsawa and Sakauchi)
Quadtree

For secondary storage:

k-d-B Tree (Robinson)
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
    let net=es in
      me_at_privacy.net Received on Thu Sep 09 2004 - 12:58:09 CDT