R-Baum Semantik via Gist

Geometrische Daten sind nicht mit herkömmlichen B-Trees zu bewältigen. Vielmehr braucht man einen Indextyp, der in der Lage ist, sich an die Gegebenheiten geometrischer Daten anzupassen. Lange Zeit gab es in PostgreSQL einen Index Typ, der allgemein als R-Baum bekannt geworden ist. Dieser Index Typ konnte zur Indizierung von Linien und anderen geometrischen Objekten herangezogen werden. Mittlerweile gibt es keine explizite R-Baum Implementierung mehr - stattdessen wird R-Baum Semantik über sogenannte Gist Indices abgearbeitet. Bevor wir uns im Detail mit Gist beschäftigen, sehen wir uns kurz an, wie geometrische Daten prinzipiell indiziert werden können:

Die Grundidee hinter dem Index ist erstaunlich einfach: Jedem Objekt wird eine Box zugeordnet, die das Objekt vollständig umschließt. Im Fall von Punkten und Rechtecken ist diese Box automatisch definiert. Bei Polygonen und dergleichen wird diese Box erst generiert. Alle Objekte werden im Baum nach Ihrer 'Größe' organisiert, um so eine Baumstruktur zu erzeugen. Ist also beispielsweise das Objekt R2 ein Teil von R1, so wird wird R2 im Baum auch 'unter' R1 eingetragen. Sind R1 und R2 voneinander unabhängig (= nicht hierachisch), so stehen sie im Baum nebeneinander. Es ist auf diese Weise also sehr schnell möglich zu prüfen, ob ein Objekt in einem anderen Objekt enthalten ist.

Die folgende Grafik zeigt ein Beispiel, das 19 Objekte zeigt, die ineinander verschachtelt sind.

sql/rtree.eps

In jedem Rechteck befindet sich ein beliebiges geometrisches Objekt. Wie man sieht, sind die gezeigten Objekte hierachisch angeordnet. Somit kann man diese Struktur in einen Baum überführen:

sql/rtree2.eps