Storage and Index Structures

  • Bisher haben wir uns nur die Architektur von Datenbanken selber angeschaut
  • Wir haben uns auch schon angeschaut wie man "gute" Applikationen mit Datenbanken schreiben kann
    • So sachen wie Two- oder Three-Tier Architekturen sollten inzwischen ein Begriff sein
    • Wir haben direkt damit auch schon gelernt, wie die Sicherheitsstrukturen von verschiedenen DBMSs aussehen können
    • z.B. dass Prepared Statements sicherer gegen SQL-Injections sind und,
    • dass ORMs uns die Arbeit mit Datenbanken vereinfachen
  • Wir haben also inzwischen nen guten Überblick über Datenbanken as a whole
  • So können wir dann also schon Systeme damit schreiben und sinnvoll mit Datenbanken interagieren
  • Heute wollen wir uns mal anschauen wie das DBMS unter der Haube funktioniert

Physical Storage

  • Wenn wir uns mal so einen PC anschauen haben wir diverse Speichermedien
  • In erster Linie kennen wir natürlich unser Systemspeicher (den RAM)
    • der ist, wie wir inzwischen hoffentlich wissen, ziemlich schnell
    • Da er direkt mit dem CPU verbunden ist
    • Das bedeutet aber auch, dass wir nicht besonders viel davon haben
  • Daher haben wir auch das was wir als Sekundären Speicher bezeichnen
    • Das sind "weiter entfernte" Speichermedien wie SSDs oder auch HDDs die via Storage Controller angesteuert werden. (Hier ein flashback an Rechnerarchitektur)
    • Auf diese Sekundären Medien wird auch via den Primären Speicher zugegriffen, da alles erst in RAM geladen werden muss, bevor der Prozessor (oder auch andere Module wie eine GPU) damit arbeiten können, da sonst die Datenübertragungsgeschwindigkeit einfach nicht ausreicht
    • Wenn wir genauer auf unsere Sekundären Speichermedien schauen sehen wir, dass das in den meissten fällen Block-Storage Devices sind

Block Storage Devices

  • Block Storage bedeutet, dass unsere Speichermedien in "Blöcke" separiert sind mit denen wir dann die Sachen speichern und darstellen können
  • Wir nennen diese "Blöcke" auch Sektoren
  • Jeder Sektor kann nur vollständig oder garnicht beschrieben werden
  • Daher sind die Sektoren meisstens eher klein, um so wenig speicher wie möglich zu wasten und gleichzeitig auch nicht zu viele sektoren für große Dateien zu brauchen
  • Jeder dieser Sektoren ist direkt addressierbar via Logical Block Addressing
  • Wie bei so vielen Dingen im Leben ist auch hier sequentielles Lesen deutlich schneller als Random Lesen
    • Das liegt in der HDD grundlegend daran, dass sich der Kopf (dat ding was die Drehende Disk abliest) sich weniger bewegen muss
    • Und bei SSDs bedeutet das, dass der Controller zwischen weniger Blöcken / Storagemedien hin und her springen muss (Eine SSD besteht meisstens aus mehreren NAND-Chips, google wat das ist, wenns dich interessiert)
  • Insgesamt können wir festhalten, dass wir versuchen unsere Daten so effizient und so Kompakt wie möglich zusammenpacken wollen damit wir am ende möglichst wenig Speicher verbrauchen
    • Gleichzeitig versuchen wir aber auch, alles was zusammengehört zusammen (oder zummindest nah beieinander) zu speichern, damit wir möglichst sequentiell lesen können

File System

  • Damit wir irgendwas mit den Blöcken anfangen können liegt auf unseren Sekundären Speichermedien meisstens noch ein virtuelles Layer: Das Filesystem (FS) (Nicht verwechselnn mit fachschaften lol)
  • Das Filesystem funktioniert am ende ähnlich bzw. genau so wie unsere Blockstorage devices, denn auch das Virtuelle FS ist in blöcke bzw. Sektoren aufgespalten
  • Diese Blöcke entstehen dadurch, dass wir Physische Sektoren zu größeren Blöcken gruppieren, die auf unsere Anforderungen zugeschnitten sind.
    • Diese Gruppierten Blöcke sind oft größer als die darunter liegenden Physischen Blöcke, aber genau deswegen machen wir das ja
  • Idealerweise starten diese Virtuellen Sektoren auch da, wo unsere Physischen Sektoren starten, das macht uns später das addressieren einfacher
  • Jeder Virtuelle Block kann bis zu einer datei enthalten (oder auch nur ein teil eineer Großen datei), sie werden aber nie unter mehreren Dateien aufgeteilt
    • Sprich wenn eine Datei nur 1,5 Blöcke aufbraucht, ist der letzte halbe block frei
    • Das ist ein bisschen wasteful, allerdings können wir so effizienter Addressieren

RDMS

  • Jetzt haben wir uns (mehr oder weniger) durch die Schichten durchgearbeitet und sind wieder beim DBMS angekommen
  • Unter der Haube speichert unser DMBS alles wie "normale" Programme auch als Dateien.
  • Diese Dateien spaltet as DBMS in sog. Pages
  • Diese sind praktisch dasselbe wie unsere "Blöcke" auf FS ebene
  • Diese Pages sind auch mit dem Sektorstart angeordnet
  • Wenn wir jetzt etwas von einer Bestimmtne Page laden wollen, wird diese zunächst auch in unser Primäres Speichermedium, also den RAM geladen
  • Von da aus können wir dann "schnell" auf diese Zugreifen, da RAM ja ziemlich schnell ist, wie wir wissen (hihihi)
  • Das nennen wir "buffering"

Records

  • Wenn wir in der Leiter der Abstraktion noch weiter nach oben rücken, sehen wir, dass wir inzwischen wieder da Angekommen sind, wo wir vor ein Paar wochen waren: Records
  • Diese sind, wie wir ja schon wissen, eine Kollektion von Werten in einem Reihen-Orientierten Modell
    • Sprich jeder Record ist eine Reihe in einer Tabelle
    • Jeder der werte die einen Tupel bzw. Record zusammensetzen hat daher auch seine eigene Zelle
    • Wir nennen diese Speicherarchitektur auch ein -ary Storage-Model
  • Da wir alle unsere Werte in Records bzw. Tupeln speichern, können wir sicher gehen, das alles auch in Virtuelle und darunter dann in Physische Blöcke aufgeteilt wird, und das auch überall alles irgendwie Sortiert zusammenpasst
  • Wie genau das Funktioniert kann man hier sehen

Wie finden wir jetzt kram?

  • Naja, das ist die Frage die uns warscheinlich (mit) am meissten Interessiert
  • Wenn wir uns anschauen wie der kram gespeichert wird, sollten wir auch wissen, wie dieser gespeicherte Kram durchsucht wird
  • dafür gibt es (natürlich) verschiedene Möglichkeiten

Full-Table Scan

  • Wir laden uns eine Page in den RAM
  • Dann iterieren wir durch alle Records in dieser Page mithilfe des Slot-Array (das oben angegebene Beispiel)
  • Für jeden der Records schauen wir, ob unsere condition zutrifft (die, die wir bei der Query angegeben haben)
  • Und dann laden wir die nächste Page und machen das so lange, bis wir alle pages durchhaben
  • Am Ende spucken wir dann alles aus, wo die Condition gepasst hat

Index Structures

  • Indizes sollten uns allen schon ziemlich bekannt vorkommen
  • Mit denen können wir dinge "sinnvoll" und schnell durchsuchen
  • Wenn wir also in unserer DB alles sinnvoll durchnummerieren und mit indizes Versehen können wir vieles einfach schneller durchsuchen
  • Die Indizes werden dann genutzt, damit wir mit bestimmten Conditions schneller durch unsere DBs iterieren können
    • (Daher sollte man auch immer ne ID haben lol)
  • Um einen Index zu bekommen können wir praktisch jedes (feld) attribut nutzen
    • Ein Index kann zu mehreren Attributen passen
    • Ebenfalls können mehrere Indizes zu einem Attribut gehören
  • Index strukturen brauchen allerdings zusätzlichen Speicher und auch zusätzlichen Aufwand

Hash-Indizes

  • Indizieren via Hashes ist inzwischen etwas was wir alle ziemlich gut kennen und auch irgendwie Hassen gelernt haben (besonders in Info 2 gott verdammt)
  • Wenn wir via Hashing indizieren wollen können wir das wieder mit unseren Eimern machen, und hoffen, dass das danach nicht alles im Eimer ist (haha)
  • Dafür brauchen wir dann eine weitere, interne Datenstruktur die sachen mit dem hash eines indizierten Attribut ausseinanderhält
  • Der Index besteht bzw, addressiert Eimer
  • Jeder der Eimer hat elemente also das Indexierte Attribut und den Record-Identifier
  • Wenn wir jetzt eine Reihe finden wollen, machen wir das indem wir den Hash von generieren
    • Damit können wir dann den richtigen Eimer ausfindig machen
    • und in diesem Eimer können wir dann "manuell" nach suchen
    • yay

-Bäume

  • Wir kennen sie alle
  • Wir mögen sie warscheinlich (nicht)
  • Jede Node kann mehrere Einträge haben
  • Jede Node kann ausserdem mehrere Kinder haben (auch mehr als zwei, daher auch nicht binär)
  • Innerhalb der Node sind die Einträge Sortiert
  • Der Baum ist Balanciert, also haben alle Wege die selbe Länge
  • Der Baum hat den Parameter der die Minimale Anzahl von Einträgen pro Node bestimmt
  • Wie genau das Funktioniert, kannst du sehen wenn das Licht angeht

-Bäume

  • Wenn wir uns unsere bisherigen Strukturen anschauen können wir uns dann auch noch fragen, wie wir die Sache mit den Bäumchen noch verbessern können
  • Das machen wir indem wir alle Keys in die blätter quetschen
  • Und die blätter dann miteinander verbinden
  • Wenn wir das so machen, können wir den oberen Teil des Baums zum suchen verwenden und die Blätter des baumes zeigen direkt auf die zugehörigen Werte

Wasn jetzt der Unterschied?

  • Hauptsächlich differenzieren sich die beiden Herangehensweisen in der Internen Struktur der beiden Bäumchen
  • Der "normale" B-Baum hat schlüssel auch innerhalb des baumes, das hat der B⁺ Baum nicht, dafür hat dieser dann "pointer-schlüssel" die auf die "richtigen" schlüssel zeigen
  • Durch diese Referenzschlüssel können wir dann "einfacher" durch den Baum suchen.
    • Diese Referenzschlüssel können Kopien des "richtigen" schlüssel sein, müssen das aber nicht, das entscheidet sich je nach DBMS und je nach Datentyp
  • Diese Referenzschlüssel müssen allerdings auch immer geupdated werden, wenn die "richtigen" schlüssel verändert werden
    • z.b. wenn etwas hinzugefügt oder auch entfernt wird
  • Wenn wir uns die Komplexität anschauen unterscheiden sich die beiden Bäumchen kaum, allerdings sind B⁺ Bäume in der Praxis schon effizienter, wenn eine größere Datenmenge vorliegt, dafür verbrauchen sie allerdings auch mehr speicher
  • Je nach index level können B⁺ Bäume auch mehr indizes beinhalten

Aber warum Bäume?

  • Wenn wir unsere Daten mit der Hilfe von Bäumen speichern bzw. indexieren können wir sicher gehen, dass der kram Sortiert bleibt und wir so sequentiell durch unsere Daten iterieren können
    • Das ist, wie wir ja oben schon gesehen haben, besonders schnell
  • Wir können ausserdem eine Liste von Hierachischen Keys im RAM behalten, damit wir möglichst wenig auf unseren Sekundären Speicher zurückgreifen müssen
    • Das spart energie, Zeit und auch Festplattenleben, denn letztendlich ist jeder Zugriff "schädlich" für das Leben unsere Festplatte
  • Wir können darüber hinaus auch teilweise vollständige Blöcke nutzen um das Inserten und Löschen von Daten zu beschläunigen
  • Ebenso können wir durch den baum den Index balanziert behalten, damit wir möglichst wenig durch die gegend uschen müssen
  • Clustured Index

Ja aber was hat das jetzt alles mit uns zu tun?

Physische Datenmodellierung in DBMS

  • Wir können in unserem DBMS auch Indizes erstellen
  • das machen wir mit dieser Query:
  • CREATE [UNIQUE] INDEX name ON table (column [ASC | DESC], [...]);
  • Hier ist zu beachten, dass jedes DBMS das anders handled und auch anderen Syntax dafür hat
  • Manche DBMS bieten auch "B-Tree-Indexes" an, allerdings ähneln diese von der Implementation oft eher B⁺ Bäumen
  • Clustered Indizes werden auf dem Table-Level deklariert, indem spezifiziert wird, welcher index wie geclustered werden soll. Mehr dazu hier

Wann wollen wir denn Indizes?

Bei welchen queries bringt das denn was?

  • DQL und DML queries können von Indizes profitieren
    • Das allerdings nur, wenn die Selektions- oder Joinkriterien Indezierte Attribute sind
  • Ebenso können sachen die Unique sein müssen davon profitieren
    • Wenn die Spalten die extra gechecked werden müssen auch indiziert sind
    • Und man "einfach" schauen kann, ob nen index schon exestiert

Welche Attribute sollen wir Indizieren?

  • Am besten die sachen die oft abgerufen werden und oder in Transaktionen verwendet werden
  • Ebenfalls sachen die Zeitkritisch sind bzw. besonders schnell ausgeführt werden müssen

Wann sind Indizes eher ne doofe idee

  • Daten die oft modifiziert bzw. Angepasst / gelöscht / hinzugefügt werden sind eher unpassend fürs indizieren
    • Da wir jedes mal neue Indexe generieren und einfügen müssen
    • Und das updaten bzw. umherschieben von Indizes ist aufwändig
  • Ebenso sollten wir attribute die wir nie zum auswählen nutzen nicht indexieren, da uns das da keinen vorteil bringt und nur speicher und rechenleistung schluckt

Design-Decisions mit Indizes

58