Next: R-Baum Semantik via Gist Up: Typen von Indices Previous: Typen von Indices Contents
Der B-Tree Index wird vom System defaultmäßig verwendet und sind somit der am häufigsten verwendete Indextyp. B-Trees sind auf High-Concurrency optimiert und ermöglichen eine Vielzahl von gleichzeitig agierenden Benutzern.
In PostgreSQL eignen sich B-Trees hervorragend für die Indizierung der gängigen ANSI-SQL Datentypen (varchar, etc.). Sofern Sie keine 'außergewöhnlichen' Funktionalitäten benötigen, sind B-Trees die erste Wahl.
Intern entsprechen B-Trees im Prinzip einer Baumstruktur, die entsprechend sortiert ist. Schematisch kann man sagen, dass kleine Werte links im Baum - große Werte rechts im Baum zu finden sind. Die folgenden Absätze beschreiben, wie ein Index grob funktioniert:
Eine Indexabfrage funktioniert mit Hilfe einer sogenannten Binären Suche. Stellen wir uns vor, wir haben die Zahlen von 1 bis 1.000.000 indiziert:
1 2 3 ... 999.998 999.999 1.000.000
Suchen wir die Zahl 363.452 so nehmen wir unseren Index und suchen den 'mittleren' Wert. Die Ermittlung des mittleren Wertes geht sehr schnell von Statten. Jetzt stellen wir fest, dass die Zahl 500.000 größer ist als der gesucht Wert. Das bedeutet im Prinzip, dass die rechte Hälfte des Index den gesucht Wert nicht mehr enthalten kann - wir haben es also geschafft, nach einem Suchschritt bereits 50% der Daten zu entfernen. Jetzt nehmen wir die linke Hälfte der Daten (also die Werte 0 - 500.000) und suchen wieder den mittleren Wert. 250.000 ist kleiner als der gesuchte Werte - das bedeutet, dass wir wieder 50% der noch übrigen Daten eliminiert haben. Nach zwei Suchschritten bleiben also nur mehr 25% der Daten übrig. Wiederholen wir den Vorgang ausreichend oft, werden wir den entsprechenden Datensatz sehr schnell finden. Im Fall von 1.000.000 Datensätzen werden wir spätestens nach 20 Suchschritten die richtige Zeile finden. Erhöhen wir die Datenmenge auf 1.000.000.000 Datensätze, werden wir lediglich 10 Suchschritte mehr benötigen. Der Grund dafür ist, dass der Suchaufwand mit steigender Datenmengen nur logarithmisch wachsen wird (Anzahl der Suchschritte = Logarithmus dualis der Datenmenge).
Zum Vergleich: Wollen wir aus einer Million Datensätze ohne Index einen speziellen Wert filtern, werden im Durschnitt 500.000 Suchschritte benötigen (im Schnitt werden wir die halbe Tabelle lesen müssen bevor wir den Wert gefunden haben).
Klarerweise sind die von PostgreSQL verwendeten Indexes wesentlich komplexer, da Concurrency ein wesentliches Thema darstellt. Um gleichzeitige Benutzer zu verwalten, verwendet PostgreSQL High-Concurrency Indices, die auf den Verfahren von Lehman und Yao basieren. Innerhalb des Index werden Daten in Blöcken fixer Größe verwaltet (üblicherweise 8kb Blöcke). Im Knoten des Baumes befindet sich also nicht nur ein Datensatz sondern in der Regel gleich ein ganzes Set von Werten. Das hat den Vorteil, dass die Zugriffe auf die Platte beim Durchwandern des Index sehr stark reduziert werden. Da die Indexstruktur einer Datenbank sicherstellen muss, dass Benutzer gleichzeitig arbeiten können, sind Vorkehrungen zu treffen.
Im Fall eines INSERTs sind die folgenden Schritte notwendig:
Im schlimmsten Fall gibt es also beim Einfügevorgang drei Locks. Theoretisch ist dieser Vorgang auch mit nur zwei Locks möglich, in dem man den aktuellen Datensatz bereits nach dem put() wieder freigibt.
Der beschriebene Vorgang wirkt auf den ersten Blick etwas umständlich und unnötig komplex - bedenken Sie aber: Sie sind im Index nicht alleine und es muss sichergestellt sein, dass jeder Benutzer einen konsistenten Datenbestand vorfindet, der gleichzeitig editiert wird.
Wenn Sie einen Datensatz aus einem Index löschen wollen, kann dieser nicht sofort gelöscht werden. Das ist von großer Bedeutung, da es sonst unmöglich wäre, ein ROLLBACK durchzuführen. Auch das Modifizieren eines Datensatzes ist eigentlich keine Modifikation im eigentlichen Sinne: Vielmehr wird ein neuer Datensatz angelegt und der alte Datensatz wird für ungültig 'erklärt' (= schlichtweg ignoriert).