SP-GiST
SP-GiST ist eine Indexstruktur in Datenbanksystemen, die Daten durch wiederholtes Aufteilen des Raums in ungleiche, nicht überlappende Bereiche organisiert. Sie eignet sich besonders für unregelmäßige Daten wie geografische Koordinaten, Telefonnummern oder Texte, bei denen klassische Indexverfahren langsam werden.
Wenn eine Datenbank Millionen von Einträgen enthält, wäre es viel zu langsam, bei jeder Suche jeden Eintrag einzeln zu prüfen. Deshalb legt eine Datenbank einen Index an — eine Art Inhaltsverzeichnis, das direkt auf die relevanten Stellen zeigt. SP-GiST ist eine besondere Art solchen Indexes. Die Abkürzung steht für Space-Partitioned Generalized Search Tree, auf Deutsch ungefähr: „raumaufteilender verallgemeinerter Suchbaum“. Das klingt sperrig, beschreibt aber ein konkretes Prinzip: SP-GiST teilt den Bereich, in dem Daten liegen, immer wieder in kleinere Abschnitte auf — ähnlich wie man eine Landkarte in Regionen, dann in Städte, dann in Stadtteile untergliedert. Entscheidend ist dabei, dass diese Abschnitte sich nicht überlappen und unterschiedlich groß sein dürfen.
Wozu SP-GiST in der Praxis gebraucht wird
Klassische Indexstrukturen wie der B-Baum funktionieren gut, wenn Daten gleichmäßig verteilt sind — etwa Kundennummern oder Preise. Viele reale Daten sind aber unregelmäßig: Adressen häufen sich in Städten, Telefonnummern folgen Ländervorwahlen, geografische Punkte klumpen sich in bewohnten Gebieten. Für solche Daten ist ein gleichmäßig aufteilender Index ineffizient.
SP-GiST passt seine Aufteilung an die tatsächliche Verteilung der Daten an. Wo viele Einträge dicht beieinander liegen, entstehen feinere Unterteilungen. Dünn besiedelte Bereiche bleiben grob zusammengefasst. Das macht Suchanfragen in solchen Daten deutlich schneller, weil der Index große leere Bereiche in einem einzigen Schritt überspringen kann. Damit füllt SP-GiST eine Lücke, die B-Bäume und ähnliche Strukturen offenlassen.
Das Prinzip hinter der Raumaufteilung
SP-GiST baut intern eine Baumstruktur auf — eine Hierarchie aus Knoten, die jeweils auf kleinere Unterknoten zeigen. Jeder innere Knoten steht für einen Bereich. Er teilt diesen Bereich in Teilbereiche auf, die sich gegenseitig nicht überschneiden. Erst am untersten Ende des Baums, in den sogenannten Blattknoten, liegen die eigentlichen Datensätze.
Ein typisches Beispiel ist der Quadtree: Er teilt eine zweidimensionale Fläche immer wieder in vier Quadranten. SP-GiST kann dieses Prinzip als eine von mehreren möglichen Strategien nutzen. Genauso unterstützt es Kd-Bäume, die abwechselnd horizontal und vertikal teilen, oder Trie-Strukturen, die Zeichenketten buchstabenweise aufdröseln. All diese Varianten folgen demselben Grundgedanken: nicht überlappende, hierarchische Aufteilung.
Das „Generalized“ im Namen bedeutet, dass SP-GiST kein festes Verfahren vorschreibt. Stattdessen stellt es einen Rahmen bereit, in den verschiedene Aufteilungsstrategien eingehängt werden können. Datenbankentwickler können eigene Strategien implementieren, solange diese das Nicht-Überlappungs-Prinzip einhalten. Das macht SP-GiST flexibler als viele spezialisierte Konkurrenzstrukturen.
SP-GiST in Datenbanken und Geodiensten
SP-GiST ist vor allem aus PostgreSQL bekannt, einem weit verbreiteten Open-Source-Datenbanksystem. Dort steht der Indextyp seit Version 8.2 zur Verfügung und lässt sich mit einem einzigen Befehl anlegen. PostgreSQL liefert fertige SP-GiST-Strategien für Punktkoordinaten, geometrische Formen, IP-Adressbereiche und Texte mit.
Besonders oft begegnet man SP-GiST im Zusammenhang mit Geodaten. Wer etwa alle Restaurants innerhalb von zwei Kilometern um einen bestimmten Punkt sucht, stellt eine sogenannte Umkreisabfrage. Ohne Index müsste die Datenbank jede Adresse einzeln prüfen. Mit einem SP-GiST-Index auf den Koordinaten kann sie ganze Regionen ausschließen, die zu weit entfernt liegen, und kommt so in einem Bruchteil der Zeit zum Ergebnis.
Ein häufiger Irrtum ist, SP-GiST mit GiST zu verwechseln. GiST — ohne das „SP“ — ist ebenfalls ein verallgemeinerter Suchbaum, erlaubt aber überlappende Bereiche. Das ist bei manchen Daten nützlich, kostet aber bei der Suche mehr Aufwand, weil mehrere überlappende Äste gleichzeitig verfolgt werden müssen. SP-GiST verzichtet bewusst auf Überlappung und ist dafür bei geeigneten Daten schneller. Welcher der beiden Indextypen besser passt, hängt vom konkreten Anwendungsfall ab.