Wie sieht ein B-Baum-Index auf mehr als 1 Spalte aus?

Question

Also ich habe mich über Indizes und ihre Implementierung informiert und bin auf diese Website gestoßen, die eine kurze Erläuterung zu B-Tree-Indizes hat:

http://20bits.com/articles/interview-questions-database-indexes/

Der B-Tree-Index macht perfekt Sinn für Indizes, die nur auf einer einzelnen Spalte sind. Aber nehmen wir an, ich erstelle einen Index mit mehreren Spalten, wie funktioniert dann der B-Tree? Was ist der Wert jedes Knotens im B-Tree?

Zum Beispiel, wenn ich diese Tabelle habe:

tabelle kunde:
id    number
name   varchar
telefonnummer   varchar
stadt   varchar

und ich einen Index auf: (id, name, stadt) erstelle

und dann die folgende Abfrage ausführe:

SELECT id, name 
  FROM kunde
 WHERE stadt = 'Meine Stadt';

wie nutzt diese Abfrage den Index mit mehreren Spalten, oder nutzt sie diesen nicht, es sei denn der Index wurde als (stadt, id, name) oder (stadt, name, id) erstellt?

Answer 1

Bei den meisten Implementierungen ist der Schlüssel einfach ein längerer Schlüssel, der alle Schlüsselwerte mit einem Trennzeichen enthält. Da steckt kein Zauber dahinter ;-)

In Ihrem Beispiel könnten die Schlüsselwerte so aussehen:

"123499|John Doe|Conway, NH"
"32144|Bill Gates| Seattle, WA"

Eine der Eigenschaften dieser Indizes mit zusammengesetzten Schlüsseln ist, dass die Zwischenknoten des Baums in einigen Fällen verwendet werden können, um die Abfrage zu "decken".

Zum Beispiel, wenn die Abfrage darin besteht, den Namen und die Stadt zu finden, die zu der ID gehören, kann der Index effizient nach dieser suchen, da die ID zuerst im Index steht. Sobald im Zwischenknoten angekommen, kann er den Namen und die Stadt aus dem Schlüssel "parsen" und muss nicht zum Blattknoten gehen, um dasselbe zu lesen.

Wenn die Abfrage jedoch auch die Telefonnummer anzeigen möchte, folgt die Logik dem Blatt, wenn der vollständige Datensatz gefunden wurde.

Answer 2

Stellen Sie sich vor, dass der Schlüssel durch ein Python-Tupel (col1, col2, col3) repräsentiert wird ... die Indizierungsoperation umfasst den Vergleich von tuple_a mit tuple_b ... wenn Sie nicht wissen, welchen Wert von col1 und col2 Sie interessieren, sondern nur col3, dann müssten Sie den gesamten Index lesen ("vollständige Indexsuche"), was nicht so effizient ist.

Wenn Sie einen Index auf (col1, col2, col3) haben, können Sie davon ausgehen, dass jedes RDBMS den Index (auf direkte Weise) verwendet, wenn die WHERE-Klausel einen Verweis auf (1) alle 3 Spalten (2) sowohl col1 als auch col2 (3) nur col1 enthält.

Ansonsten (z. B. nur col3 in der WHERE-Klausel) wird entweder das RDBMS diesen Index überhaupt nicht verwenden (z. B. SQLite) oder eine vollständige Indexsuche durchführen (z. B. Oracle) [wenn kein anderer Index besser ist].

In Ihrem speziellen Beispiel, vorausgesetzt, dass die ID eindeutiger Bezeichner eines Kunden ist, ist es sinnlos, sie in einem Index erscheinen zu lassen (außer dem Index, den Ihr DBMS für einen Primärschlüssel oder eine Spalte, die als UNIQUE gekennzeichnet ist, einrichten sollte).

Answer 3

Einige Implementierungen verknüpfen einfach die Werte in der Reihenfolge der Spalten mit Trennzeichen.

Eine andere Lösung besteht darin, einfach einen B-Baum innerhalb eines B-Baums zu haben. Wenn Sie ein Blatt in der ersten Spalte treffen, erhalten Sie sowohl eine Liste übereinstimmender Datensätze als auch einen Mini-B-Baum der nächsten Spalte usw. Daher spielt die Reihenfolge der in den Index angegebenen Spalten eine große Rolle dafür, ob dieser Index für bestimmte Abfragen nützlich sein wird.

Hier ist eine verwandte Frage, die ich letzte Woche geschrieben habe:

Springt SQL Server über Blätter, wenn ein zusammengesetzter grupierter Index verwendet wird?

Answer 4

In Oracle kann auch dann ein zusammengesetzter Schlüsselindex verwendet werden, wenn die führenden Spalten nicht gefiltert sind. Dies wird durch drei Mechanismen erreicht:

1. Ein schneller vollständiger Indexscan, bei dem Multiblock-Lesevorgänge verwendet werden, um das gesamte Indexsegment zu durchlaufen.
2. Ein vollständiger Indexscan, bei dem der Index in der logischen Reihenfolge der Blöcke gelesen wird (ich glaube, ich habe gelesen, dass Oracle in neueren Versionen Multiblock-Lesevorgänge dafür verwenden kann, aber Sie sollten wirklich mit einzelnen Block-Lesevorgängen rechnen)
3. Ein Indexübersprungsscan, bei dem das Vorhandensein einer sehr geringen Kardinalität für die nicht prädizierten führenden Spalten Oracle ermöglicht, mehrere Indexbereichsscans durchzuführen, einen für jeden eindeutigen Wert der führenden Spalte(n). Diese sind in meiner Erfahrung ziemlich selten.

Suchen Sie nach Artikeln von Richard Foote oder Jonathan Lewis für weitere Informationen zu den internen Oracle-Indexen.

Answer 5

"Der Index wird nach dem ersten Schlüsselelement, dann nach dem zweiten Schlüssel und so weiter geordnet sein" https://www.qwertee.io/blog/postgresql-b-tree-index-explained-part-1/