R Bäume (rtree)

Seit einigen Jahren verfügt PostgreSQL über einen eigenen Indextyp, der die Indizierung von geometrischen Objekten ermöglicht. Da PostgreSQL spezielle Datentypen zur Verwaltung von Linien und dergleichen bereitstellt, sind R-Trees in diesem Fall das Mittel der Wahl. Im Gegensatz zu B-Trees sind R-Trees für die Suche im Raum optimiert und können so schnell räumliche Aufgabenstellungen bewerkstelligen.

In PostgreSQL hat man R-Bäume auf Basis des 'Gutman Quadratic Split Algorithm' implementiert. 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.

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: