Indexing < Datenbanken < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:54 Mo 29.03.2010 | | Autor: | Wimme |
Hallo!
Leider ist mir das Prinzip von Indexing bei Datenbanken nicht so richtig einleuchtend.
Also irgendwie wird mit Indexing ja erreicht, dass man Datensätze in der Datenbank schneller findet - basierend auf einem Schlüsselwert.
Wie muss ich mir das denn vorstellen?
Ich habe eine Datenbank A (also vielleicht mit einer Tabelle T(a,b,c) wobei a,b und c Attribute sind). Die Tabelle ist ja jetzt irgendwie im Speicher, in pages aufgeteilt.
Was genau macht jetzt ein Index? Könnte das beispielsweise ein Binärbaum sein, der in seinen Knoten einen Wert von a speichert, sowie die Adresse zur kompletten Zeile aus T im Speicher?
Dann könnte man den Binärbaum verwenden um Datensätze zu finden, die diesen speziellen a-value haben.
Ein Beispiel wäre sicherlich sehr hilfreich!
Dankeschön,
Wimme
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:58 Do 01.04.2010 | | Autor: | rainerS |
Hallo Wimme!
> Leider ist mir das Prinzip von Indexing bei Datenbanken
> nicht so richtig einleuchtend.
> Also irgendwie wird mit Indexing ja erreicht, dass man
> Datensätze in der Datenbank schneller findet - basierend
> auf einem Schlüsselwert.
>
> Wie muss ich mir das denn vorstellen?
> Ich habe eine Datenbank A (also vielleicht mit einer
> Tabelle T(a,b,c) wobei a,b und c Attribute sind). Die
> Tabelle ist ja jetzt irgendwie im Speicher, in pages
> aufgeteilt.
> Was genau macht jetzt ein Index? Könnte das
> beispielsweise ein Binärbaum sein, der in seinen Knoten
> einen Wert von a speichert, sowie die Adresse zur
> kompletten Zeile aus T im Speicher?
> Dann könnte man den Binärbaum verwenden um Datensätze
> zu finden, die diesen speziellen a-value haben.
Das ist ein guter Ansatz. Wenn man eine Zeile mit einem bestimmten Wert des Attributes a sucht, kommt man bei n vorhandenen Zeilen mit etwa log(n) Vergleichen aus, um die passende Zeile zu finden. Bei n=1000000 sind das nur 20 Vergleiche gegenüber durchschnittlich einer halben Million bei linearer Suche durch die Tabelle. Diese Ersparnis ist der Zweck eines Index.
Es muss aber kein binärer Baum sein. Ein Index kann zum Beispiel auch als eine Hash-Tabelle implementiert werden.
Viele Grüße
Rainer
|
|
|
|
