Database indexing

[Gaestel]

Moin,

ich weiß nicht recht wohin mit meiner Frage, deswegen stelle ich sie jetzt einmal hier.
Irgendwie kapier ich das Prinzip von Indexing in Datenbanken nicht.

Also, ein Index ist doch eine hilfreiche Datenstruktur um schneller Records aus einer Datenbank zu finden.
Dafür wird irgendwie ein "search key" verwendet.

Kann mir mal jemand ein konkretes Beipiel dafür angeben, wie das aussehen könnte?
Wie funktioniert das, wie sieht so ein Index aus? Was genau ist der search key und wie wird er verwendet?

Ich hoffe wirklich ihr könnt mir helfen!

 

[SlaterB]

wie es implementiert und verwendet wird, kann man doch der DB überlassen,

zwei Grund-Datenstrukturen seien genannt:
1. Baum, Suchbaum,
eine Wurzel hat sortiert mehrere Nachfolger, wenn man in den linken Teilbaum wechselt, hat man schon 50% ausgeschlossen (den rechten Teilbaum),
nicht schlecht für einen simplen Arbeitsschritt,
Binärbäume, Suchbäume, Baumsortieren

2. Hashing
Hashfunktion ? Wikipedia

funktioniert ganz grob in etwa so wie eine Quersumme, alle Zahlen von 0-100 haben die Quersumme 0-9

wenn man eine bestimmte Zahl wie 33 hat, berechnet man die Quersumme 6 und schaut sich alle dazu gespeicherten Einträge ein,
das wären in diesem Beispiel wahrscheinlich nur 10% aller Einträge, also 10x schneller, als ALLES anzuschauen

mit komplizierteren Hashfunktionen gehts entsprechend genauer

------

ein Index spart Zeit beim Suchen, erfordert aber zusätzlichen Festplattenplatz und auch etwas Arbeit zur Berechnung,
muss bei jedem Einfügen/ Entfernen aktualisiert werden

 

[Atze]

Datenbankindex ? Wikipedia

 

[Gaestel]

Hallo!

Danke für die Antworten.

Kann ich mir das ganze Prozedere im Prinzip so vorstellen:
Ich habe irgendeine Tabelle A in meiner Datenbank. Meinetwegen mit den Spalten a,b,c,d.
Diese Tabelle ist ja jetzt irgendwie in Pages unterteilt in der Datenbank abgespeichert.
Nehmen wir an, ich möchte die Tabelle jetzt indizieren.

Ich könnte mir jetzt also Spalte a raussuchen, und als search key wählen.
Dann könnte ich einen Baum bauen, dessen Knoten folgendes speichern: <wert von a, pointer zum Datensatz aus Tabelle>

Und in Zukunft könnte das DBMS den Baum durchsuchen, wenn eine Anfrage über Attribut a kommt und somit schneller den entsprechenden Datensatz lokalisieren.


So richtig?

 

[SlaterB]

gewiss

 

[Gaestel]

okay, dann scheine ich schon mal den Gedanken hinter der ganzen Geschichte verstanden zu haben.
Nun steht aber in meinen Notizen "Indexdaten sind viel kleiner als die richtigen Daten".
Weiter hinten steht "Jeder Index Eintrag speichert entweder a) den wirklichen Datensatz b) .. c) .."

Wenn jetzt jeder Indexeintrag den wirklichen Datensatz speichert, wie soll das ganze dann bitte viel kleiner als die richtigen Daten werden?

 

[Gaestel]

hey,

sorry, dass ich hier so meine ganzen Fragen eine nach der anderen stelle, aber weiß nicht recht wo ich das sonst machen soll...

also, noch zusätzlich:
ich weiß, dass der primary index den primary key der tabelle enthält, der secondary index nicht.
Nun steht hier aber auch etwas davon, dass der search key beim primary index das "ordering key field" sein soll.
Wieso? Die Daten in der Tabelle müssen doch nicht mit dem Primary Key geordnet sein? Oder wie ist das gemeint?

 

[SlaterB]

> Jeder Index Eintrag speichert entweder a) den wirklichen Datensatz b) .. c) ..

hier dürfte nur b) und c) zu einem kleineren Index führen

Index file size
- index file for a primary index need substantially fewer blocks than the data file
- why?
- fewer index entries: an entry exists for each block of data file rather than for each record
- index entry is smaller in size than a data record: only two fields (key value and block pointer)

http://www.cs.virginia.edu/~son/662.pdffiles/662.physical.pdf

---------

zum zweiten:
ich denke schon, dass es ausdrücken soll, dass für einen Primary Index gilt, dass die Daten physikalisch tatsächlich genau in der Reihenfolge des Indexes abgelegt sind (dann würde es auch Sinn man den ganzen Eintrag im Index zu halten, die Tabelle IST quasi ein Teil des Primary Index),
der Primary Key ist dabei das 'ordering key field' dieses Primary Indexes

wenn der Index unabhängig von den Daten ist, kann das ja immer noch ein Seconday Index sein