Die einfachste Implementierung einer Datenbank

Von aller Anwendungssoftware sind Datenbanken möglicherweise die komplexeste.

Das MySQL-Handbuch umfasst mehr als 3.000 Seiten, das PostgreSQL-Handbuch umfasst mehr als 2.000 Seiten und das Oracle-Handbuch ist umfangreicher als beide zusammen.

Es ist jedoch nicht schwierig, die einfachste Datenbank selbst zu schreiben. Auf Reddit gibt es einen Beitrag, der das Prinzip in wenigen hundert Worten anschaulich erklärt. Unten ist das, was ich basierend auf diesem Beitrag zusammengestellt habe.

1. Daten in Textform speichern

Der erste Schritt besteht darin, die zu speichernden Daten in eine Textdatei zu schreiben. Diese Textdatei ist Ihre Datenbank.

Um das Lesen zu erleichtern, müssen die Daten in Datensätze unterteilt werden und die Länge jedes Datensatzes muss gleich sein. Unter der Annahme, dass die Länge jedes Datensatzes beispielsweise 800 Byte beträgt, beträgt die Startposition des fünften Datensatzes 3200 Byte.

Meistens kennen wir die Position eines bestimmten Datensatzes nicht, wir kennen nur den Wert des Primärschlüssels. Zu diesem Zeitpunkt können Sie zum Lesen der Daten die Datensätze einzeln vergleichen. Dies ist jedoch zu ineffizient, da Datenbanken häufig das B-Tree-Format zum Speichern von Daten verwenden.

2. Was ist ein B-Baum?

Um den B-Baum zu verstehen, müssen wir vom binären Suchbaum ausgehen.

Der binäre Suchbaum ist eine Datenstruktur mit sehr hoher Sucheffizienz. Er weist drei Merkmale auf.

(1) Jeder Knoten hat höchstens zwei Teilbäume.

(2) Der Wert des linken Teilbaums ist kleiner als der des übergeordneten Knotens und der Wert des rechten Teilbaums ist größer als der des übergeordneten Knotens.

(3) Um den Zielwert unter n Knoten zu finden, sind im Allgemeinen nur log(n)-Vergleiche erforderlich.

Die Struktur des binären Suchbaums ist nicht für Datenbanken geeignet, da seine Sucheffizienz von der Anzahl der Ebenen abhängt. Je niedriger die Daten sind, desto mehr Vergleiche sind erforderlich. Im Extremfall erfordern n Daten n Vergleiche, um den Zielwert zu finden. Für die Datenbank müssen Sie jedes Mal, wenn Sie eine Ebene eingeben, Daten von der Festplatte lesen. Dies ist sehr fatal, da die Lesezeit der Festplatte viel länger ist als die Datenverarbeitungszeit Festplatte, desto besser.

Der B-Baum ist eine Verbesserung gegenüber dem binären Suchbaum. Seine Designidee besteht darin, zusammengehörige Daten so weit wie möglich zu sammeln, sodass mehrere Daten gleichzeitig gelesen werden können und die Anzahl der Festplattenoperationen reduziert werden kann.

B-Baum hat auch drei Eigenschaften.

(1) Ein Knoten kann mehrere Werte enthalten. In der Abbildung oben enthält der größte Knoten beispielsweise 4 Werte.

(2) Neue Ebenen werden nur hinzugefügt, wenn die Daten ausgefüllt sind. Mit anderen Worten: B-Tree verfolgt so wenige „Schichten“ wie möglich.

(3) Der Wert im untergeordneten Knoten weist eine strikte Größenkorrespondenz mit dem Wert im übergeordneten Knoten auf. Im Allgemeinen gilt: Wenn der übergeordnete Knoten einen Wert hat, gibt es +1 untergeordnete Knoten. Im Bild oben hat der übergeordnete Knoten beispielsweise zwei Werte (7 und 16), die drei untergeordneten Knoten entsprechen. Der erste untergeordnete Knoten hat einen Wert kleiner als 7, der letzte untergeordnete Knoten hat einen Wert größer als 16 und der mittlere untergeordnete Knoten hat einen Wert zwischen 7 und 16.

Diese Datenstruktur ist sehr hilfreich, um die Anzahl der Lesevorgänge von der Festplatte zu reduzieren. Unter der Annahme, dass ein Knoten 100 Werte enthalten kann, kann ein 3-schichtiger B-Baum 1 Million Daten enthalten. Wenn er durch einen binären Suchbaum ersetzt wird, sind 20 Schichten erforderlich! Unter der Annahme, dass das Betriebssystem jeweils einen Knoten liest und der Wurzelknoten im Speicher verbleibt, muss der B-Baum die Festplatte nur zweimal lesen, um den Zielwert unter 1 Million Daten zu finden.

3. Index

Die Datenbank wird im B-Tree-Format gespeichert, wodurch nur das Problem gelöst wird, Daten anhand des „Primärschlüssels“ zu finden. Wenn Sie andere Felder finden möchten, müssen Sie einen Index erstellen.

Der sogenannte Index ist eine B-Tree-Datei mit einem bestimmten Feld als Schlüssel. Angenommen, es gibt eine „Mitarbeitertabelle“, die zwei Felder enthält: Mitarbeiternummer (Primärschlüssel) und Name. Für Namen kann eine Indexdatei erstellt werden. Diese Datei speichert Namen im B-Tree-Format, und auf jeden Namen folgt seine Position in der Datenbank (d. h. welcher Datensatz). Suchen Sie bei der Suche nach einem Namen zunächst den entsprechenden Datensatz im Index und lesen Sie ihn dann aus der Tabelle.

Diese Indexsuchmethode wird als „Indexed Sequential Access Method“ bezeichnet, abgekürzt als ISAM. Es gibt bereits mehrere Implementierungen (z. B. C-ISAM-Bibliothek und D-ISAM-Bibliothek). Solange Sie diese Codebibliotheken verwenden, können Sie die einfachste Datenbank selbst schreiben.

4. Erweiterte Funktionen

Nach der Bereitstellung des grundlegendsten Datenzugriffs (einschließlich Indizierung) können auch einige erweiterte Funktionen implementiert werden.

(1) Die SQL-Sprache ist eine universelle Betriebssprache für Datenbanken, daher ist ein SQL-Parser erforderlich, um SQL-Befehle in entsprechende ISAM-Operationen zu analysieren.

(2) Datenbankverbindung (Join) bezieht sich auf den Aufbau einer Verbindungsbeziehung zwischen zwei Tabellen in der Datenbank über „Fremdschlüssel“. Sie müssen diesen Vorgang optimieren.

(3) Datenbanktransaktion bezieht sich auf eine Reihe von Datenbankvorgängen, die stapelweise ausgeführt werden. Solange ein Schritt fehlschlägt, ist der gesamte Vorgang erfolglos. Daher ist ein „Vorgangsprotokoll“ erforderlich, damit der Vorgang rückgängig gemacht werden kann, wenn er fehlschlägt.

(4) Sicherungsmechanismus: Speichern Sie eine Kopie der Datenbank.

(5) Remote-Betrieb: Ermöglicht Benutzern den Betrieb der Datenbank auf verschiedenen Computern über das TCP/IP-Protokoll.