B*-Bäume
Transbase stützt sich auf hoch optimierte Präfix-B*-Bäume zur Speicherung von Tabellen und Indexen.
Sie können sowohl sequentiell als auch indexiert betrieben werden, sind und bleiben jedoch speichertechnisch nach dem Primärschlüssel der Tabelle sortiert (Clustered Table). Damit können insbesondere Primärschlüsselintervalle mit einer Minimalzahl von Seitenzugriffen durchlaufen werden, was wesentlich zu der hohen Performanz von Transbase beiträgt.
B*-Bäume sorgen durch ihr logarithmisches Verhalten für eine perfekte Skalierbarkeit der Zugriffszeiten.
Bei der Optimierung kann der Schwerpunkt auf Geschwindigkeit oder Platzbedarf gelegt werden. Die Platzoptimierung führt auf der Festplatte zu hochkomprimierten Datensätzen, die den Gesamtspeicherbedarf für die Datenbank minimieren. Im Gegensatz dazu werden die Datensätze bei der Geschwindigkeitsoptimierung nicht komprimiert und im Layout der Rechnerarchitektur abgelegt, so dass Datensätze nicht umgebaut werden müssen. Wie genau diese Ansätze funktionieren, wird im Folgenden anhand eines Beispiels erklärt.
Beispiele
Zur Erklärung der verschiedenen Optimierungen wird im Folgenden ein Beispiel-Tupel in der Datenbank abgelegt. Dieses Tupel hat vier Felder und sieht wie folgt aus:
{"Test", 591, null, date(2020-1-1)}
In obiger Abbildung ist der grundsätzliche Aufbau von B*-Bäumen dargestellt. Auf der untersten Ebene liegen die Datensätze physisch in der Datenbank (Record 578). Die im folgenden erläuterten Optimierungen finden dort statt.
Geschwindigkeitsoptimierte Ablage
Für die geschwindigkeitsoptimierte Ablage nützt Transbase ein sogenanntes 4 Byte-Alignment aus. Dies bedeutet, dass auf physischer Datenspeicherungsebene jedes Feld auf einer Adresse beginnt, die ein Vielfaches von 4 ist. Ein 1-Byte-Element muss somit mit drei Null-Bytes "\0" aufgefüllt werden. Dadurch kann Transbase auf jedes Feld direkt zugreifen.
Die genaue Tupelstruktur wird anhand untenstehender Abbildung erläutert.
In den ersten 10 Adressfeldern sind Pointer abgespeichert, die auf den Anfang der vier Felder und hinter das letzte Feld verweisen. Jeder Pointer eine Größe von 2 Byte.
Die zwei Null-Bytes in den Offsets #10 und #11 werden als Auffüllelemente benötigt, da sonst die 4 Byte-Alignment Vorgabe nicht erfüllt ist.
Somit kann in #12 das erste Feld "Test" vom Typ Character abgespeichert werden, gefolgt von dem notwendigen Char-Begrenzer "\0". Die darauf folgenden drei weiteren Null-Elemente werden wieder benötigt für die Alignment Vorgabe. Daraufhin wird in #20 der Integer "591" abgespeichert mit 2 Auffüllelementen. Pointer 2 und 3 zeigen beide auf das Offset #24, was bedeutet, dass das dritte zu speichernde Feld einen Null-Wert aufweist. Pointer 4 zeigt in #24 auf das Datumselement, Pointer 5 wiederum zeigt auf das Ende des gesamten Tupels in #28.
Insgesamt benötigt dieses Tupel somit 28 Bytes zur Speicherung.
Speicheroptimierte Ablage
Dasselbe Tupel wird nun mit dem Fokus auf geringstmöglichen Speicherplatz abgespeichert, was wiederum an untenstehender Abbildung erklärt wird. Diese Methode umgeht bei der Speicherung die Vorgabe des Alignments und kann so die Auffüll-Bytes einsparen. Diese müssen jedoch bei einem späteren Zugriff wieder hinzugefügt werden, was die Performanz reduziert.
Es fällt zunächst auf, dass diese Speicherung mit nur 4 Pointern auskommt. Dass das erste Element in #8 beginnt, ist durch die Anzahl der vier Elemente des Tupel implizit bekannt.
Es lässt sich weiterhin erkennen, dass die drei Elemente "Test", "591", "Date" optimal und ohne Null-Byte hintereinander abgespeichert sind. Dadurch konnte der Speicherbedarf von 28 auf 18 Byte verringert werden, was einer Einsparung von knapp 36 Prozent entspricht.
Eine weitere Einsparung kann zusätzlich erreicht werden, wenn Festlängenattribute verwendet werden. Für jedes Festlängenattribut können weitere 2 Bytes eingespart werden.
Schlüsselwiederholungen
Bei mehrstufigen Primärschlüsseln können wiederholte Präfixe des Schlüssels unterdrückt werden, was den Speicherbedarf weiter reduziert. Beispielsweise kann die Datensatzfolge
{{"Smith", "Adam"}, {"Smith", "Barbara"}, {"Smith", "Patrick"}, {"Smith", "Thomas"}}
als
{{"Smith", "Adam"}, {"Barbara"}, {"Patrick"}, {"Thomas"}}
abgespeichert werden, was - je nach Länge des wiederholten Schlüssels und der Anzahl der Wiederholungen - zu erheblichen Speicherplatzeinsparungen führt.