Re: Implementierung mehrdimensionaler Indexe

* Harald Fuchs <hf0614x(at)protecting(dot)net> schrieb:

<snip>
> Sehe ich auch so. Ich würde sogar soweit gehen zu sagen, daß
> PostgreSQL (ebenso wie die meisten anderen DBMS) gar keine
> mehrdimensionalen Indizes kennt. Mehrspaltige Indizes würde ich eher
> "geschachtelt" als "mehrdimensional" nennen, weil immer erst nach der
> ersten Spalte indiziert wird und darin dann nach der zweiten.

Gibts dazu irgentwo nähere Infos ?

Ich bin bisher immer davon ausgegangen, daß so ein mehrspaltiger
Index nichts weiter ist, als ein Index über einer Verkettung der
einzelnen Spalten. (ähnlich wie wohl ein Funktionalen Index
einfach ein Index über dem Funktionsergebnis sein düffte)

Solch ein Schachtel-Index dürfte sich aber um einiges anders
verhalten, als solch ein Kombi-Index.

Beispiel: WHERE x=123 and y=666

Kombi: btree ueber (x||y)
-> 1x direkter lookup.

Schachtel: btree ueber x, an jedem knoten btree ein
weiterer btree ueber einer teilmenge von y.
-> 2x direkter lookup
(einmal in erster ebene, dann in der zweiten)

Interessant sind ja aber auch Fälle wie:

WHERE x<123 and x<666 and y>12 and y<17

Da kommt man mit einer simplen Verkettung nicht mehr weiter -
der Index kann so einfach nicht greifen. Aber man könnte ich
evtl. damit helfen, daß man erst die passende Teilmenge zu
x sucht und innerhalb dieser Intervalle nochmal einschränkt.
Dürfte aber etwas knifflig werden.

Evtl. ist hier ein zweistufiger Baum doch nicht so verkehrt.
Man könnte erst das Intervall im B*-Baum raussuchen, alle
Knoten durchlaufen und nochmal deren Unterbäume scannen.

hmm...

cu
--
---------------------------------------------------------------------
Enrico Weigelt == metux IT service
phone: +49 36207 519931 www: http://www.metux.de/
fax: +49 36207 519932 email: contact(at)metux(dot)de
---------------------------------------------------------------------
Realtime Forex/Stock Exchange trading powered by postgresSQL :))
http://www.fxignal.net/
---------------------------------------------------------------------