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

Abgesehen vom bereits beschriebenen Mechanismus des "zusammengesetzten Schlüssels" besteht eine Möglichkeit darin, einen kdtree zu verwenden, der ähnlich wie ein Binärbaum funktioniert, aber während Sie jede Ebene durchlaufen, durchlaufen Sie k Dimensionen. Das heißt, die erste Ebene des Baums teilt die erste Dimension in zwei Teile, die zweite Ebene teilt die zweite Dimension, die k+1 Ebene teilt die erste Dimension erneut, usw. Dies ermöglicht eine effiziente Partitionierung von Daten in beliebig vielen Dimensionen. Dieser Ansatz ist in "räumlichen" Datenbanken (z.B. Oracle Spatial, PostGIS usw.) verbreitet, aber wahrscheinlich nicht so nützlich in "regulären" mehrfach indizierten Tabellen.

http://en.wikipedia.org/wiki/Kd-tree

Answer 2

Es kann den (id, name, city) Index verwenden, um ein "City = ?" Prädikat zu erfüllen, jedoch sehr ineffizient.

Um den Index zur Erfüllung dieser Abfrage zu verwenden, müsste er den Großteil der Baumstruktur durchsuchen, um Einträge mit der gewünschten Stadt zu finden. Das ist immer noch wahrscheinlich eine Größenordnung schneller als das Durchsuchen der Tabelle!

Ein Index von (city, name, id) wäre der beste Index für Ihre Abfrage. Er würde alle gewünschten Stadt-Einträge leicht finden und müsste nicht auf die darunter liegende Tabelle zugreifen, um die id- und name-Werte zu erhalten.