Index bei Datenbanken

[Brei]

Vorab: Hab Wikipedia und Boardsuche und Mysql-Manual genutzt.

Trotzdem kapier ich nicht wie ein Index ein Select schneller machen kann.

"Er muss nicht alle Datensätze der Reihe nach durchgehen sondern kann gleich wo hinspringen".

=> schön ung gut, aber warum? Genauer? Er muss ja trotzdem Werte vergleichen

Anm.: "Er" = sagen wir mal der "Datenbankserver"

=> wie nutzt man dann einen Index?

=> wie schaut der aus?

=> Binärbäume check ich garnicht

danke

[Muadibb]

Also,

gehen wir mal davon aus, Du hast eine Adresstabelle mit etwa 1 Mio Einträgen. Nun wird im Allgemeinen ein Primärschlüssel in Form einer laufenden Nummer vergeben.

Jetzt wird es aber mit sehr grosser Wahrscheinlichkeit vorkommen, dass Du sehr viele gleiche Vornamen (wie z.B. Christian, Hans oder so) hast und auch sehr viele gleiche Nachnamen (Müller, Meier, Smith,...).

Stelle Dir vor Du möchtest alle Leute finden, die mit Vornamen Christian heissen. Ohne Index wird nun die gesamte Tabelle sequentiell von oben nach unten durchsucht.

Angenommen ein Christian steht auf Position 10 und einer auf 900000 in Deiner Tabelle, dann durchsuchst Du trotzdem alle 1 Mio Einträge, da Du ja nicht weisst, ob der 900001e Eintrag noch einen Christian enthält.

Wenn Du einen Index z.B. auf den Vornamen erstellst werden Vektoren für jeden Vornamen erzeugt, die dann etwa so aussehen:

Christian(Position 10,900000)

Wenn Du nun bei einer indizierten Tabelle nach Christian suchst, dann wird in der Index Tabelle nach Christian gesucht und dann weiss man automatisch an welchen Stellen der Name auftaucht und kann so wesentlich schneller (gilt aber i.d.R. nur bei grossen Datenmengen) alle Datensätze finden.

Zum Binärbaum in diesem Zusammenhang:

Ein Binärbaum ist eine Möglichkeit auf Speicherebene, die Daten zu organisieren, um einen effizienten Zugriff zu gewährleisten. Die binäre Suche verwendet diesen Baum. Man springt an die Mitte eines Vektors (z.B. aller Anfangsbuchstaben des Alphabets) und überprüft, ob der gesuchte Wert links oder rechts von der Mitte liegt. Das macht man solange, bis am Ziel ist. Man kann so bei jeder Überprüfung 50% der vorhandenen Einträge ausschliessen, da man einen Grössenvergliech macht.

[Amstelchen]

ein index (unabhängig von der art der datenbank) ist nichts anderes als ein inhaltsverzeichnis eines buches. d.h. hat man keinen index, sucht man normalerweise relativ mühsam auf allen seiten nach dem betreffenden text - ist aber ein index vorhanden, geht man durch diesen, sucht sich die entsprechende seite, schlägt diese auf und hat in der regel die seite, auf der der begriff oder das kapitel vorkommt.

es gibt mehere arten von indizes:

- b-bäume (also funktions bzw. algorithmusbasiert)

-- wobei b-bäume wiederum entweder

--- normal oder

--- reversekey (umgekehrter aufbau) geschlüsselt sind

- r-bäume (wie b-bäume, nur mehrdimenisional)

- bitmapindex

-- bitmapindiex mit hoher

-- und niedriger kardinalität (suche dazu mathematische begriffe o.ä.)

- domainindex (also ein anwendungsspezifischer index)

- hashindex (z.b. der md5 eines feldes telefonnummer (?))

ein index kann (im regelfall) entweder unique sein (eindeutige werte haben) oder nonunique (es dürfen gleiche werte darin vorkommen).

im regelfall wird jede art von index für eine bestimmte art von abfrage besser oder schlechter sein als ein anderer.

=> wie nutzt man dann einen Index?

man nutzt ihn meist transparent, d.h. suchen in indizierten datenbeständen werden optimiert, abfragen dauern weniger lang.

=> wie schaut der aus?

kommt auf den index an, aber im prinzip ist ein index auch "nur" eine tabelle.

oder geht es dir darum, wie man (syntaxmässig) einen index anlegt - das ist zwar bei den meisten engines ähnlich, aber nicht wirklich gleich.

=> Binärbäume check ich garnicht

siehe oben.

s'Amstel

[Brei]

Christian(Position 10,900000)

Also schonmal danke, jetzt ist es mir schon klarer. Was wird jetzt aber mit diesem Vektor gemacht? Werden die Vektoren wieder in einer Datenbank gespeichert? Wie wird der verwendet? Schaut "er" dann im Vektor nach, sieht "Christian" und merkt: "ah, auf Position 10,90000,15,20450 stehen noch welche"?

[Muadibb]

genauso!

Ein Index ist wieder eine Tabelle. So kann man es sich am besten vorstellen. Wenn ein select geschrieben wird, in dem nach Vornamen gefragt wird, überprüft der Server ob es dazu einen Index gibt. Wenn ja schaut er dort nach den Positionen in der Originaltabelle und holt sich die gesuchten Datensätze

[SNOWMAN]

das bedeutet, das wenn ich in meine Tabelle ein eigene ID schreibe, welche meinen index darstellt, das es mir diesen Vorteil nicht bringt, da der Index ja eher selten gesucht wird!?

[Muadibb]

das bedeutet, das wenn ich in meine Tabelle ein eigene ID schreibe, welche meinen index darstellt, das es mir diesen Vorteil nicht bringt, da der Index ja eher selten gesucht wird!?

Soll das jetzt eine Frage oder eine Bemerkung sein? In dem Zusammenhang verwirren mich Deine Satzzeichen "!?"

[mme]

das bedeutet, das wenn ich in meine Tabelle ein eigene ID schreibe, welche meinen index darstellt, das es mir diesen Vorteil nicht bringt, da der Index ja eher selten gesucht wird!?

Wenn du auf diesen Index nichts abfragst bringt er dir kaum was... Aber wenn du eine eigene ID in einer Tabelle hast, so nutzt man den meistens als Primary Key, daraus folgt, das die Fremdschlüssel anderer Tabellen ggf. darauf verzweigen... Also benutzt man diese IDs häufig in den Joins. Beim Joins wird der Index dann automatisch (je nach Optimizer) genutzt.

Also bringt dir der Index auf einer eigenen ID doch was.

Wenn die ID jedoch kein Primary Key ist und das ganze somit nicht gilt, frag ich mich wofür du dann die ID hast...

Man kann übrigens bei den meisten DBM-Systemen beliebig viele Indizes auf eine Tabelle anlegen. Dabei muss ein Index sich nicht auf eine Spalte begrenzen.

Noch mal allgemein zum verdeutlichen... Man stelle sich eine Tabelle mit 10 Spalten vor. Da nach allen 10 Spalten gesucht wird, kopiert man die Tabelle 10 mal und sotiert jede Kopie nach einer anderen Spalte. Da dies aber unefizient ist, löscht man alle 9 Spalten nach den man nicht sortiert hat in den Kopien raus, und macht dafür einen Verweis des Datensatzes in der Ursprungstabelle. Fertig. Ob das jetzt intern B-Bäume, Bitmap indizes oder irgendwas sind, macht natürlich einen Unterschied, aber die Idee ist die selbe....

grüße mme

[geloescht_JesterDay]

das bedeutet, das wenn ich in meine Tabelle ein eigene ID schreibe, welche meinen index darstellt, das es mir diesen Vorteil nicht bringt, da der Index ja eher selten gesucht wird!?

Natürlich suchst du danach nicht unbedingt, aber es wurde ja schon die Verwendung in Joins angesprochen. Ausserdem bringt es einen ganz entscheidenden Vorteil: Eine unique ID macht jeden Satz absolut eindeutig!

Bei updates und deletes (oder auch joins) ist das mehr als wichtig! Bei mir hat jede Tabelle (auch wenn sie nur 1 oder 2 spalten enthält) noch eine eindeutige ID. Das bringt dir keine Nachteile, aber im Zweifel eben Vorteile.

[Amstelchen]

noch zu vervollständigen: das mit den "keine nachteile" von indizes ist nicht ganz richtig: da ein index bei updates und inserts aktualisiert werden muss, können daraus auch geschwindigkeitsnachteile entstehen, d.h. beim einfügen von bspw. 1 mio. datensätze müssen für diese auch im index änderungen vorgenommen werden - ergo: oftmals kann ein index auch einen flaschenhals bedeuten und sollte zwischenzeitlich entweder gelöscht oder aber z.b. partitioniert werden.

s'Amstel