Theorie: Wie funktioniert ein Index?

[port29]

Hallo Leute,

ich beschäftige mich momentan etwas mehr mit den internen Funktionen von Datenbanken und versuche nebenbei auch selbst eine Datenbank zu entwickeln. Doch leider verstehe ich nicht so ganz, wie der Index einer Datenbank funktioniert.

Wenn ich einen Integer Primärschlüssel habe, dann kann ich die Datenbank auf ein Array abbilden und habe eine mittlere Zugriffszeit von O(1). Das ist soweit klar.

Doch wie ist es bei Strings als Index? Wenn ich ein String habe, muss ich ihn zunächst hashen und anschließend z.B. in einem Baum nach den Werten suchen. Das hat schon eine deutlich höhere Laufzeit zur Folge.

Wie machen sowas denn die großen Datenbanksysteme?

 

[ZodiacXP]

Buch: SQL in a Nutshell Seite 63 bis 68 steht ein bisschen was zum CREATE INDEX aus SQL und hier ist was zu Gridfile:
http://de.wikipedia.org/wiki/Gridfile

Hoffe das hilft dir.

 

[ishino]

In der Regel werden Indizes über einen B-Baum (bzw. B+-Baum) abgebildet (siehe http://de.wikipedia.org/wiki/B-Baum). In den "leaf blocks" (also den Blättern des Baumes) werden die Daten, in diesem Fall "Zeiger" auf die Zeilen in der indizierten Tabelle, gespeichert.

Üblicherweise sind die Bäume relativ flach (um die 3 bis 4 Ebenen). Das Suchen in einer Baumstruktur hat eine Komplexität von O(log n), ist also sehr effizient. Bei einer Suche nach einer Zahl (aus Deinem Integer-Beispiel) würde man sukzessive den Baum von der Wurzel bis zur Blattebene traversieren und dabei jeweils anhand der in den Knoten gespeicherten Werte entscheiden, welcher Teilbaum das gesuchte Ergebnis enthält bzw. enthalten könnte. Ist man dann auf der Blattebene angekommen, findet man dort wo in der indizierten Tabelle die eigentlich benötigten Daten zu finden sind (bei Oracle nennt sich das z.B. ROWID).

Bei Zeichenketten oder Indizes über mehrere Spalten funktioniert das analog. Wörter können, analog zu Zahlen, verglichen werden, so daß die Suche im Grunde genauso funktioniert. Bei zusammengesetzten Indexen werden halt auch die Schlüsselwerte zusammengepackt (einfach gesagt). Damit kann man gleichzeitig nach mehreren Bedingungen suchen (zum Beispiel ein Index über zwei Spalten, eine mit Zahlen eine mit Buchstaben - im Index stehen dann als Schlüssel eben 198A, 29F, 298T usw.).

Meist finden sich in den gängigen RDBMS (Oracle, DB2, etc.) auch noch andere Indexvarianten (Bitmap-Indexe, Funktionsbasierte Indizes, Textindizes, etc.). Die basieren teilweise auf ganz normalen B-Bäumen, die ein bißchen "aufgepustet" werden und dadurch Spezialaufgaben lösbar machen (zum Beispiel sowas wie SELECT ... WHERE sqrt(foo) = 2, also "alle Zeilen, wo die Quadratwurzel des Werts in Spalte "foo" 2 beträgt).

Naja...Details... ;-)

 

[port29]

In der Regel werden Indizes über einen B-Baum (bzw. B+-Baum) abgebildet (siehe http://de.wikipedia.org/wiki/B-Baum). In den "leaf blocks" (also den Blättern des Baumes) werden die Daten, in diesem Fall "Zeiger" auf die Zeilen in der indizierten Tabelle, gespeichert.

Okay, danke für die Info. Ich werde morgen in aller ruhe mal den Artikel durchlesen und evtl. dazu mal die Vorlesung irgendeiner Uni anhören. Bei uns waren die Bäume in Info2, doch es ist jetzt schon sehr lange her. Hatten auch damals eine eeeeetwas höhere Durchfallquote von 75% in der schriftlichen und 85% in der Mündlichen. Das Niveau der Vorlesung war deshalb unter aller Sau.

Aber danke für die Antwort. Beim Integer Schlüssel wollte ich allerdings ein etwas anderes Verfahren durchführen. Ich kenne ja die Speicheradresse, wo mein Index beginnt und dann weiß ich eben, wie lang jeder Eintrag ist. Meine Idee in so einem Fall wäre, dass man von Anfang des Index einfach n * a Speicherstellen weiterspringt (wobei a die Länger einer Speicherstelle angibt). Damit wäre man wirklich in O(1) an der richtigen Adresse. Klar kostet das Verfahren mehr Speicher (wenn Löcher auftreten), aber Speicher haben wir heute doch eh schon genug.

 

[vop]

Hatten auch damals eine eeeeetwas höhere Durchfallquote von 75% in der schriftlichen und 85% in der Mündlichen. Das Niveau der Vorlesung war deshalb unter aller Sau.

War die Durchfallquote wegen des Niveaus so hoch oder war das Niveau wegen der hohen Durchfallquote so niedrig

 

[port29]

War die Durchfallquote wegen des Niveaus so hoch oder war das Niveau wegen der hohen Durchfallquote so niedrig

Ist jetzt zwar OT, aber dennoch will ich darauf antworten. Das Problem an der Vorlesung war, dass die einfachen Sachen (die sogar ein Ghetto-Hauptschüler auf Anhieb verstehen würde) bis ins kleinste Detail erklärt und mit Beispielen druchgekaut wurden. Aber sobald der Stoff komplizierter wurde, ging man schneller durch.

Fragen aus dem Plenum wurden dann einfach nicht beantwortet, dafür wurde der Student runtergeputzt "Wie sie wissen es nicht? Was haben Sie dann überhaupt an der Uni verloren?"

Während der Klausur wurden dann auch die schweren Sachen mitabgefragt. Die Klausur hatte auch eine Aufgabe, die man in der Regel nicht lösen konne.