101 - Datenstrukturen in SQLite-Datenbanken - Kapitel 7

SQLite Einführung

• SQLite ist eine Datenbank, die von Richard Hipp entwickelt wurde.
• Es handelt sich um eine Client-Server-lose Datenbank.
• Die Datenbankdaten werden als Datei auf dem Client gespeichert.

Datenbankrelevanz

• Mobiles Betriebssystem (Android und iOS)
• Desktop Betriebssystem (Mac und Windows)
• Browser (Chrome, Firefox, Safari)

SQLite Dateiformat

• Eine Datenbank ist eine Sammlung von Tabellen (Tables).
• Jede Tabelle hat ein definiertes Format (Schema).
• Tabellen können über eindeutige Schlüssel (Keys) miteinander verknüpft sein (Relational).
• Die Datenbank ist idealerweise normalisiert, um Duplikate zu minimieren und Effizienz und Integrität zu maximieren.
• Tabellen und Indizes werden gesammelt.
• Die Nutzung von Binärbäumen (Binary Trees) – B-Trees – ist üblich
• Eine SQLite-Datenbank besteht aus einer Anzahl von (meist) gleich großen Einheiten von Daten – Pages.
• Eine Page hat eine Größe von 512 Bytes.
• Die kleinstmögliche Datenbank hat 512 Bytes.
• Die größte Datenbank ist bis 140 TB.
• Es gibt verschiedene Page Typen: B-Tree, Overflow, Freelist, Pointer Map und Lock-Byte Pages.

B-Tree Pages

• B-Tree Pages sind die häufigste Art von Pages.
• Es gibt zwei Arten von B-Tree-Tabellen: Table-B-Tree und Index-B-Tree
• Jede Art hat zwei Unterarten: Interior Pages und Leaf Pages.
• Die aktiven/vorhandenen Inhalte der Datenbank werden in Leaf Pages abgelegt.
• Nicht-allokierte Bereiche befinden sich ebenfalls auf den Pages.

Erste Page

• Die Datenbank beginnt auf der ersten Page.
• Die ersten 100 Bytes bilden den Database Header.
• Nach dem Header befindet sich die Table B-Tree des sqlite_master-Tables.
• Der sqlite_master Table enthält Informationen zu jeder Tabelle und jedem Index in der Datenbank.

Database Header

• Die ersten 100 Bytes des Headers enthalten 23 Einträge.
• Wichtige strukturelle Daten der Datenbank werden beinhaltet.
• Integer-Werte werden in SQLite im Big-Endian-Format gespeichert.

B-Trees

• Eine Datenbank besteht aus Tabellen und Indizes.
• Jeder benötigt jeweils eine oder mehrere Seiten (Pages).
• Eine Seite gehört nicht zu verschiedenen Tabellen oder Indizes.
• Seiten werden mit einem B-Baum zusammengefügt.

Tabelle: sqlite_master

• Jede Datenbank hat eine sqlite_master-Tabelle.
• Die Tabelle beginnt auf der ersten Seite nach dem Header und enthält Daten zu jeder Tabelle in der Datenbank.
• Die Tabelle enthält Informationen wie Typ, Name, Bezugsname, Root Page (Anfang), SQL-Statement der Erstellung der Tabelle.

B-Tree-Interior und Leaf Pages

• Die Struktur eines B-Baumes wird mit Hilfe von Interior und Leaf Pages realisiert.
• Es gibt immer nur eine Root Page am Anfang der Table.

Interior Pages

• Beinhalten Verweise (Pointers) auf weitere Pages.
• Zeigen auf weitere Interior oder Leaf Pages.

Leaf Pages

• Behalten die eigentlichen Daten, die in der Datenbank abgelegt sind.
• Es gibt Ausnahmen von WITHOUT_ROWID-Tabellen.

Größere Tabellen

• Größere Tabellen haben eine komplexere Struktur aus Interior und Leaf Pages.
• Wenn die Datenbankdaten geändert werden, können Seiten (Pages) hinzugefügt oder gelöscht werden.
• Einträge auf den Seiten können auch intern kopiert werden.

Aufbau von Interior und Leaf Pages

• Page Header
• Cell Pointer Array
• Zellen (Cells Header + Zellinhalt (Payload))
• Freie Blöcke (Free Blocks)

Page Header

• Flag (1 Byte): 0x02 -> Interior Index, 0x05 -> Tabelle des Interior, 0x0A -> Leaf Index, 0x0D -> Tabellende
• Erster freier Block (2 Bytes)
• Anzahl der allokierten Zellen (2 Bytes)
• Offset zum ersten Eintrag (2 Bytes)
• Anzahl der Fragmente in Bytes (1 Byte)
• Verweis ganz rechts (4 Bytes, nur Interior)

Beispiel eines Headers

• a = (0D)16 → Blatttabelle
• b = (0000)16 = (0)10 → keine freien Blöcke
• c = (0001)16 = (1)10 → eine belegte Zelle
• d = (0FAC) 16 = (4012)10 → Eintrag an Offset 4012
• e = (00)16 = (0)10 → 0 Byte Fragment

Varints

• Integer werden mit variabler Länge gespeichert (1 bis 9 Bytes).
• Das Zweierkomplement-Format wird verwendet, um kleine positive Zahlen effizient darzustellen.
• Es wird für Bytelängen, ROWIDs und verschiedene Eintragstypen verwendet.
• Dies gibt es auch für negative Werte, aber das ist ineffizienter.

Steuerungszeichen

• Steuerungszeichen durch das höchstwertigste Bit
• 1 bedeutet, dass das Bit auf weitere Bytes folgt
• 0 bedeutet das letzte Byte

Positiver Varint

• Beispiel für die Darstellung positiver Zahlen in Varint-Format.

Cell Pointer Array

• Nach dem Header folgt der Cell Pointer Array.
• Beinhaltet einen 2 Byte-Pointer für jede genutzte Zelle.
• Zeigt auf Tabellenoffset auf der Seite.
• Die Anzahl der allokierten Zellen steht im Header dieser Seite.

Struktur eines Eintrags

• Die Einträge im Cell Pointer Array zeigen auf Einträge innerhalb der Seite.
• Das Layout der Einträge hängt von der Art der Seite (Interior oder Leaf) ab.
• Interior Table, Leaf Table, Interior Index, Leaf Index.

Aufbau der Interior und Leaf Table Records

• Interior Record: Zeigt auf Kindsknoten (Varint), Integer-Schlüssel/ROWID (Varint).
• Leaf Record: Länge des Payloads (Varint, inkl. Overflow), Integer-Schlüssel/ROWID (Varint), Payload (variable Länge), Pointer auf Overflow-Seite (4 Bytes, nur bei Bedarf).

Leaf Table Record

• Payload Length
• ROWID
• Record Length
• Null
• txt12
• … -Payload
• Overflow Page

Leaf Table Aufbau

• Länge des Payloads (Varint, inkl. Overflow)
• Integer Key / ROWID (Varint)
• Payload (variable Länge)
• Pointer auf Overflow-Seite(4 Bytes, nur wenn nötig)
• Payload besteht aus Kopf (Payload Header) und Inhalt (Payload Body)

Attributtypen

• Übersicht über verschiedene Attributtypen, Größe (Bytes) und Beschreibung.

Leaf- und Interior-Tabelle

• Leaf Tabelle: Data Layout: Payload Length, ROWID, Record Len, Serial type, Daten
• Interior Tabelle enthält Referenzen zu anderen Pages/Kindsknoten, Key, und Position auf der linken Seite

Record Recovery

• Die Wiederherstellung von Daten in SQLite-Datenbanken hängt davon ab, wie viel von einem Eintrag erhalten ist.
• Möglichkeiten:
  • Intakte Struktur
    • Leaf Page (Flag 0x0D)
    • Verwaiste Page (z. B. durch Reorganisation)
    • Cell Pointer Array intakt
  • Verwaiste Einträge
    • Vollständiger Record, aber ohne Eintrag im Cell Pointer Array
  • Partielle Einträge
    • Eintrag beginnt mit Freeblock-Header überschrieben -Es kann sein, dass der wiederhergestellte Eintrag auch „live” in der Datenbank weiter existiert.
• Um einen Eintrag zu finden, können folgende Schritte verfolgt werden:
  • Suche nach dem ersten Eintrag im Cell Pointer Record
  • Analysiere den Record und den dazugehörigen Payload
  • Vergleiche den Eintrag mit den vorhandenen Tabellen

Verwaiste Einträge

• Kein Eintrag findet sich im Cell Pointer Record.
• Finde den Record und die zugehörige Tabelle.
• Alle nicht allokierten Bytes werden analysiert.
• Für jedes potenzielle Startbyte wird geprüft, ob ein korrekter Record zu einer Tabelle passt.

Serial Type Array nicht korrekt

• Beispiel, wo ein String mit 49 Bytes ein ROWID von 26 Bytes, und einige Integer mit 8 Byte.
• Die Serial Type Arraygröße passt nicht zu den vorhandenen Byte.

Verwaiste Einträge – Länge des Serial Type Arrays zu groß

• Der Anfang von dem nicht allokierten Byte
• Länge des Payloads möglich (pos. VARINT).
• ROWID möglich (pos. VARINT).
• Die Anzahl der Bytes des Serial Type Arrays sollte größer als 0 sein.
• Der Eintrag könnte richtig sein (z.B. wenn text, int, int, int in einer Tabelle definiert sind).
• Die angegebene Größe des Payloads ist möglicherweise größer als nötig

Verwaiste Einträge – (Fast) Korrekter Eintrag

• Ein Eintrag kann erfolgreich wiederhergestellt werden.
• Der Wert muss nicht NULL sein.

Partielle Einträge

• Überschriebene Teile eines Records können Probleme bei der Wiederherstellung verursachen.
• Nach dem Löschen werden nur die ersten vier Bytes mit einem Freeblock-Header überschrieben.
  • Pointer zum nächsten Freeblock
  • Länge des aktuellen Freeblocks

Partielle Einträge – Aufbau eines Eintrags

Write-Ahead Logs (WALs)

• Die Datenbank selbst wird in einer einzigen Datei abgelegt.
• Weitere Dateien (z. B. Journals und Write Ahead Logs) können zur aktiven Datenbank gehören.
• SQLite ist eine Transaktionsdatenbank.
• Änderungen werden in Gruppen zusammengefasst.
• Die kleinste Änderung betrifft immer mindestens eine Seite.
• Ein Commit kann auch hunderte Pages betreffen.
• Herausforderungen für ein System: Absturz der Software, Absturz des Betriebssystems, Stromausfall.

Ansatz

• Kopieren der betroffenen Seiten in das Rollback-Journal vor Ausführung einer Transaktion.
• Modi für Journal_Mode, welche die Art der Journal-Ungültigerklärung bestimmen. (DELETE, TRUNCATE, PERSIST)

Sequenz einer Transaktion

• Neue oder veränderte Seiten werden geschrieben.
• Der Journal Header wird geschrieben.
• Seiten ohne Änderungen werden kopiert.
• Neue Seiten werden in die Datenbank geschrieben.
• Wenn diese Schritte erfolgreich durchgeführt wurden, markiert der Journal das als ungültig.
• Bei Fehlern wird die gesicherte Seite in die Datenbank kopiert.

Write-Ahead Logs (WALs)

• Write-Ahead Logs (WAL) sind eine Methode, um Änderungen in Form eines Caches zu speichern.
• WALs sind im Vergleich zu Rollback-Journals im Allgemeinen schneller.
• Mehrere Transaktionen können in das WAL eingetragen werden.
• Transaktionen werden im WAL ausgeführt.
• Die Datenbank wird nur in sog. Checkpoints beschrieben.
• Checkpoints können durch Nutzer ausgelöst oder nach mindestens 1000 Seiten oder nach dem Beenden der Software erfolgen.
• WAL-Dateien – Dateiendung: -wal (z.B. test.db → testdb-wal)
• Es gibt einen Commit-Frame zum Schluss der Transaction.

###Praktischer Einsatz von WALs

• Start der Transaktion.
• Modifizierte Pages werden in das WAL (without DB impact) geschrieben.
• Weitere Pages werden in das WAL geschrieben.
• Commit der Transaktion → Commit-Frame.
• Checkpoint (> 1000 Pages or by command) Die aktuellsten Pages werden in die Datenbank geschrieben.
• Neue Transaktionen werden am Anfang des WAL (Header aktualisiert, aber der Rest wird nicht gelöscht) geschrieben.
• Schließen der Software → Checkpoint und Löschen der WAL-Datei.

Teste dein Wissen über die grundlegenden Datenstrukturen und Funktionen in SQLite-Datenbanken. Der Quiz umfasst Fragen zu Page-Typen, Freelist Pages und der Architektur von SQLite. Ideal für Studierende und Fachleute, die ihre Kenntnisse über SQLite vertiefen möchten.