Beispiel für eine Tabelle:
Code: Alles auswählen
CREATE TABLE personen (vorname TEXT, nachname TEXT, adresse TEXT, gebdatum TEXT, ... );
CREATE personen_name_index ON personen (vorname, nachname)
Und folgende Abfrage A1:
Code: Alles auswählen
SELECT adresse FROM personen WHERE vorname = 'Otto' AND nachname = 'Mustermann'
Und noch Abfrage A2:
Code: Alles auswählen
SELECT adresse FROM personen WHERE nachname = 'Mustermann'
Von welcher art von Index wir hier reden (B+-Baum, GiST Hash-Tabelle) ist unwichtig, siehe zweiter Teil
Zur ersten Frage:
Ein mehrspaltiger Index bedeutet, dass ein verschachtelter Index aufgebaut wird. Der erste, übergeordnete Index, indiziert die Spalte vorname. In unserem Fall aber, da wir als zweite Spalte nachname für den Index wählen, ist in unserem Index für den Knoten 'Otto' nicht einfach eine Liste an Reihen gespeichert, die einen Otto beinhalten, sondern ein weiterer Index, der die Nachnamen indiziert. Es wird also bei A1 im ersten Index nach Otto gesucht und in dem dort verfübaren Index wiederum Mustermann.
Nun kann die zweite Ebene einfach ignoriert werden, wenn nur der vorname in der Abfrage gegeben ist.
In A2 allerdings wird es schwieriger, da wir viele verschiedene Indizes haben für die Nachnamen. Das DBMS kann nun versuchen die ganzen Indizes wiederzuverwenden, was besser als ein Full Table Search ist, aber wesentlich schlechter als ein passender Index.
Zur Indizierung von Strings:
AFAIK werden für strings keine Hash-Tabellen mehr verwendet, sondern auch Suchbäume, in PostGres etwa
GiST (für Geometrie, Geographie und Volltextsuche). Wie die funktionieren, müsste ich aber auch Nachsehen.