Firebird-Indexstruktur für Firebird 2.0 (ODS 11 und höher)
Firebird-Indexstruktur ODS11 und höher
Der Grund für eine neue Struktur ist:
- bessere Unterstützung beim Löschen eines Indexschlüssels aus vielen Duplikaten (verursachte langsame Garbage Collection)
- Unterstützung größerer Datensatznummern als 32-Bit (40 Bit)
- Vergrößerung der Indexschlüsselgröße (1/4 Seitengröße)
Bestehende Struktur (ODS10 und niedriger):
| header | node | node | node | node | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
header =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // rechte Schwester-Seite
SLONG btr\_left\_sibling; // linke Schwester-Seite
SLONG btr\_prefix\_total; // Summe aller Präfixe auf der Seite
USHORT btr\_relation; // Relations-ID für Konsistenz
USHORT btr\_length; // Länge der Daten im Bucket
UCHAR btr\_id; // Index-ID für Konsistenz
UCHAR btr\_level; // Index-Ebene (0 = Blatt)
struct btn btr\_nodes\[1.;
};
node =
struct btn {
UCHAR btn\_prefix; // Größe des komprimierten Präfixes
UCHAR btn\_length; // Länge der Daten im Knoten
UCHAR btn\_number\[4.; // Seiten- oder Datensatznummer
UCHAR btn\_data\[1.;
};
end marker = END_BUCKET oder END_LEVEL
Diese stehen anstelle der Datensatznummer für Blattknoten und anstelle der Seitennummer für Nicht-Blatt-Knoten.
Wenn der Knoten ein END_BUCKET-Marker ist, sollte er dieselben Daten enthalten wie der erste Knoten auf der nächsten Schwester-Seite.
Bei einem END_LEVEL-Marker sind Präfix und Länge null, er enthält also keine Daten.
Außerdem enthält jeder erste Knoten auf einer Ebene (außer Blattseiten) einen degenerierten Null-Längen-Knoten.
Neue ODS11-Struktur:
| header | jump info | jump nodes | … | node [*] | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
jump info =
struct IndexJumpInfo {
USHORT firstNodeOffset; // Offset zum ersten Knoten auf der Seite \[\*\]
USHORT jumpAreaSize; // Größe des Bereichs, bevor ein neuer Jumpnode erstellt wird
UCHAR jumpers; // Anzahl der Jump-Nodes auf der Seite, maximal 255
};
jump node =
struct IndexJumpNode {
UCHAR\* nodePointer; // Zeiger darauf, wo dieser Knoten von der Seite gelesen werden kann
USHORT prefix; // Länge des Präfixes gegenüber dem vorherigen Jumpnode
USHORT length; // Länge der Daten im Jumpnode (zusammen mit Präfix ist dies
Präfix für den referenzierten Knoten)
USHORT offset; // Offset zum Knoten auf der Seite
UCHAR\* data; // Daten können von hier gelesen werden
};
Neues Flag für die neue Indexstruktur:
Dem header->pag_flags werden neue Flags hinzugefügt.
Das Flag btr_large_keys (32) dient zum Speichern von komprimierter Länge/Präfix und Datensatznummer. Dies bedeutet auch, dass Länge und Präfix bis zu 1/4 der Seitengröße betragen können (1024 bei 4096 Seitengröße) und in Zukunft leicht erweiterbar sind, ohne die Datenträgerstruktur erneut zu ändern. Auch die Datensatznummer kann leicht auf z. B. 40 Bit erweitert werden. Diese Zahlen werden pro 7 Bit mit 1 Bit (höchstes) als Marker gespeichert (Codierung mit variabler Länge). Jedes neue Byte, das gespeichert werden muss, wird um 7 verschoben. Beispiele: 25 wird als 1 Byte 0x19 gespeichert, 130 = 2 Bytes 0x82 0x01, 65535 = 3 Bytes 0xFF 0xFF 0x03.
Duplikat-Knoten:
Außerdem wird ein neues Flag zum Speichern der Datensatznummer auf jedem Knoten (Nicht-Blatt-Seiten) hinzugefügt. Dies beschleunigt den Indexabruf bei vielen Duplikaten. Das Flag ist btr_all_recordnumber (16). Mit diesen zusätzlichen Informationen wird die Schlüsselsuche bei Einfügungen/Löschungen mit vielen Duplikaten (z. B. NULLs in Fremdschlüsseln) viel schneller (wie auch die Garbage Collection!). Darüber hinaus speichern Duplikat-Knoten (Länge = 0) ihre Längeninformation nicht; 3 Bits vom ersten gespeicherten Byte werden verwendet, um zu bestimmen, ob dieser Knoten ein Duplikat ist. Neben dem ZERO_LENGTH (4) Marker gibt es auch END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) und ONE_LENGTH (5) Marker. Die Nummern 6 und 7 sind für zukünftige Verwendung reserviert.
Jump-Nodes:
Ein Jumpnode ist ein Verweis auf einen Knoten irgendwo auf der Seite.
Er enthält Offset-Informationen über den spezifischen Knoten und die Präfixdaten des referenzierten Knotens, aber auf den Jumpnodes selbst wird ebenfalls Präfixkomprimierung durchgeführt.
Idealerweise wird ein neuer Jumpnode nach dem ersten Knoten generiert, der nach jedem jumpAreaSize gefunden wird, aber das ist nur der Fall beim Deaktivieren/Aktivieren eines Indexes oder beim Einfügen von Knoten in derselben Reihenfolge, in der sie im Index gespeichert werden.
Wenn Knoten zwischen zwei Jumpnode-Referenzen eingefügt werden, werden nur die Offsets aktualisiert, aber nur, wenn die Offsets einen bestimmten Schwellenwert (+/-10 %) nicht überschreiten.
Wenn ein Knoten gelöscht wird, werden nur Offsets aktualisiert oder ein Jumpnode wird entfernt. Dies bedeutet, dass ein kleines Loch zwischen dem letzten Jumpnode und dem ersten Knoten existieren kann, sodass keine Zeit mit der Generierung neuer Jumpnodes verschwendet wird.
Präfix und Länge werden ebenfalls durch Codierung mit variabler Länge gespeichert.
Beispieldaten:
(x) = Größe in x Bytes
| header (34) | ||||
| 52 (2) | 256 (2) | 2 (1) | 30 (2) | 0 (1) |
| 2 (1) | 260 (2) | FI (2) | 1 (1) | 1 (1) |
| 514 (2) | U (1) | 0 (1) | 1 (1) | 0 (1) |
| A (1) | … | |||
| 2 (1) | 6 (1) | 21386 (3) | REBIRD (6) | … |
| 2 (1) | 2 (1) | 1294 (2) | EL (2) | … |
Zeiger nach festem Header = 0x22
Zeiger nach Jump-Info = 0x29
Zeiger zum ersten Jumpnode = 0x29 + 6 (Jumpnode 1) + 5 (Jumpnode 2) = 0x34
Jumpnode 1 verweist auf den Knoten, der FIREBIRD als Daten darstellt, da dieser Knoten ein Präfix von 2 hat, werden die ersten 2 Zeichen FI auch auf dem Jumpnode gespeichert.
Unser nächster Jumpnode zeigt auf einen Knoten, der FUEL mit ebenfalls einem Präfix von 2 darstellt. Somit sollte Jumpnode 2 FU enthalten, aber unser vorheriger Knoten enthielt bereits das F, sodass dieses aufgrund der Präfixkomprimierung ignoriert wird und nur U gespeichert wird.
NULL-Zustand:
Die zu speichernden Daten werden in der Prozedur compress() in btr.cpp bestimmt.
Für ASC (aufsteigende) Indizes werden keine Daten gespeichert (Schlüssel hat null Länge). Dies setzt sie automatisch als ersten Eintrag in den Index und somit in die richtige Reihenfolge (Bei Ein-Feld-Indizes sind Knotenlänge und Präfix null).
DESC (absteigende) Indizes speichern ein einzelnes Byte mit dem Wert 0xFF (255). Um zwischen einem Wert (leerer String kann 255 sein) und einem NULL-Zustand zu unterscheiden, fügen wir ein Byte von 0xFE (254) am Anfang der Daten ein. Dies wird nur für Werte durchgeführt, die mit 0xFF (255) oder 0xFE (254) beginnen, damit wir die richtige Reihenfolge beibehalten.
Beispiele:
| Knoten ASC-Index, 1 Segment | |||
| prefix | length | gespeicherte Daten | realer Wert/Zustand |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| Knoten DESC-Index, 1 Segment | |||
| prefix | length | gespeicherte Daten | realer Wert/Zustand |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| Knoten ASC-Index, 3 Segmente | |||
| prefix | length | gespeicherte Daten | realer Wert/Zustand |
| 0 | 0 | NULL,NULL, NULL | |
| 0 | 10 | x01(1) x70(F) x73(I) x82(R) x69(E) x01(1) x66(B) x73(I) x82(R) x68(D) | NULL, NULL, FIREBIRD |
| 0 | 10 | x02(2) x70(F) x73(I) x82(R) x69(E) x02(2) x66(B) x73(I) x82(R) x68(D) | NULL, FIREBIRD, NULL |
| 0 | 10 | x03(3) x70(F) x73(I) x82(R) x69(E) x03(3) x66(B) x73(I) x82(R) x68(D) | FIREBIRD, NULL, NULL |
| 3 | 9 | x00(0) x00(0) x02(2) x65(A) x00(0) x00(0) x00(0) x01(1) x66(B) | FI, A, B |
| … | … | … | … |
| Knoten DESC-Index, 3 Segmente | |||
| prefix | length | gespeicherte Daten | realer Wert/Zustand |
| 0 | 12 | xFC xB9 xB6 xFF xFF xFD xBE xFF xFF xFF xFE xBD | FI, A, B |
| 3 | 17 | xAD xBA xFC xBD xB6 xAD xBB xFD xFF xFF xFF xFF xFE xFF xFF xFF xFF | FIREBIRD, NULL, NULL |
| 1 | 19 | xFF xFF xFF xFF xFD xB9 xB6 xAD xBA xFD xBD xB6 xAD xBB xFE xFF xFF xFF xFF | NULL, FIREBIRD, NULL |
| 6 | 14 | xFF xFF xFF xFF xFE xB9 xB6 xAD xBA xFE xBD xB6 xAD xBB | NULL, NULL, FIREBIRD |
| 11 | 4 | xFF xFF xFF xFF | NULL,NULL, NULL |
| END_LEVEL |
c ABVisie 2005, Arno Brinkman