Datenbankindex

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
jeanluc
Beiträge: 33
Registriert: Mo Apr 22, 2013 10:18 pm

Datenbankindex

Beitrag von jeanluc » Di Okt 22, 2013 5:34 pm

Ich habe grad einen Knoten im Kopf. Wenn ich einen Datenbankindex über (mehrere) Spalten einer Tabelle anlege, wie genau werden dann die Indexbäume (B+-Bäume) konstruiert ? Für jede Spalte vom Typ (VAR)CHAR, INTEGER, DECIMAL usw. ein Baum ? Gemischte Bäume ? Die Eigenschaften von B+-Bäumen sind mir bekannt, mir fehlt nur der Bezug zu "richtigen" Daten.

Wie berechnet man die Schlüssel, insbesondere bei Strings ? Erhält dann jedes Unicode-Zeichen eine interne Ordnung (Zahl) ?

sebix
Beiträge: 82
Registriert: Mo Nov 19, 2012 8:27 pm

Re: Datenbankindex

Beitrag von sebix » Di Okt 22, 2013 6:34 pm

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.

jeanluc
Beiträge: 33
Registriert: Mo Apr 22, 2013 10:18 pm

Re: Datenbankindex

Beitrag von jeanluc » Mi Okt 23, 2013 1:33 pm

Dass die Spaltenmenge dann eine geordnete Menge ist, wird aus dem CREATE INDEX Statement leider nicht ersichtlich. Ich hatte immer gedacht, dass die Attribute / Spalten gleichwertig sind.

Ist deine Beschreibung gängige Implementierung ? Denn das würde ja wirklich bedeuten, dass A2 wesentlich langsamer ist, weil ich jeden sekundären Index-Baum durchsuchen muss anstatt nur einen. Alternativ muss ich vorher wissen welche Abfragen abgesetzt werden und dementsprechend die Indizes erzeugen.

sebix
Beiträge: 82
Registriert: Mo Nov 19, 2012 8:27 pm

Re: Datenbankindex

Beitrag von sebix » Mi Okt 23, 2013 8:12 pm

AFAIK ist dieses Konzept gängig. Bei Postgres und MySQL war ich mir sicher, da ich es explizit las, für Oracle habe ich gerade nachgesehen.

Und ja, es ist auf jeden Fall enorm wichtig, zu Wissen welche Abfragen gestellt werden, und wie die Funktionen eines DBMS effektiv genützt werden können. Die Optimierung der Datenbankstrukturen ist eine der wichtigsten Aufgaben eines DB-Admins, alleine darüber gibts Wälzer an Literatur, ein so ein Buch liegt neben mir, in dem ich für das Topic wieder einen kurzen Blick hineinwarf.

Antworten