Firebird-indexstructuur voor Firebird 2.0 (ODS 11 en hoger)
Firebird-indexstructuur ODS11 en hoger
De reden voor een nieuwe structuur is:
- betere ondersteuning voor het verwijderen van een indexsleutel uit veel duplicaten (veroorzaakte trage garbage collection)
- ondersteuning voor grotere recordnummers dan 32-bits (40 bits)
- vergroting van de indexsleutelgrootte (1/4 paginagrootte)
Bestaande structuur (ODS10 en lager):
| header | node | node | node | node | node | node | |||
| node | node | node | node | node | node | node | … | eindmarkering |
header =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // rechter zusterpagina
SLONG btr\_left\_sibling; // linker zusterpagina
SLONG btr\_prefix\_total; // som van alle prefixen op de pagina
USHORT btr\_relation; // relatie-id voor consistentie
USHORT btr\_length; // lengte van gegevens in bucket
UCHAR btr\_id; // index-id voor consistentie
UCHAR btr\_level; // indexniveau (0 = blad)
struct btn btr\_nodes\[1.;
};
node =
struct btn {
UCHAR btn\_prefix; // grootte van gecomprimeerde prefix
UCHAR btn\_length; // lengte van gegevens in node
UCHAR btn\_number\[4.; // pagina- of recordnummer
UCHAR btn\_data\[1.;
};
eindmarkering = END_BUCKET of END_LEVEL
Deze staan in plaats van recordnummer voor bladpagina’s en in plaats van paginanummer voor niet-bladpagina’s.
Als de node een END_BUCKET-markering is, moet deze dezelfde gegevens bevatten als de eerste node op de volgende zusterpagina.
Bij een END_LEVEL-markering zijn prefix en lengte nul en bevat deze dus geen gegevens.
Ook bevat elke eerste node op een niveau (behalve bladpagina’s) een degeneratie-node met lengte nul.
Nieuwe ODS11-structuur:
| header | jump-info | jump-nodes | … | node [*] | node | node | |||
| node | node | node | node | node | node | node | … | eindmarkering |
jump-info =
struct IndexJumpInfo {
USHORT firstNodeOffset; // offset naar eerste node op pagina \[\*\]
USHORT jumpAreaSize; // grootte van gebied voordat een nieuwe jumpnode wordt gemaakt
UCHAR jumpers; // aantal jump-nodes op pagina, met een maximum van 255
};
jump node =
struct IndexJumpNode {
UCHAR\* nodePointer; // aanwijzer naar waar deze node op de pagina kan worden gelezen
USHORT prefix; // lengte van prefix ten opzichte van vorige jump node
USHORT length; // lengte van gegevens in jump node (samen met prefix is dit
prefix voor verwijzende node)
USHORT offset; // offset naar node op pagina
UCHAR\* data; // Gegevens kunnen hier worden gelezen
};
Nieuwe vlag voor de nieuwe indexstructuur:
Er worden nieuwe vlaggen toegevoegd aan de header->pag_flags.
De vlag btr_large_keys (32) is voor het opslaan van gecomprimeerde lengte/prefix en recordnummer. Dit betekende ook dat lengte en prefix tot 1/4 van de paginagrootte kunnen zijn (1024 voor 4096 paginagrootte) en in de toekomst eenvoudig uitbreidbaar zijn zonder de schijfstructuur opnieuw te wijzigen. Ook kan het recordnummer eenvoudig worden uitgebreid naar bijvoorbeeld 40 bits. Die nummers worden opgeslagen per 7 bits met 1 bit (hoogste) als markering (variabele lengtecodering). Elk nieuw byte dat moet worden opgeslagen, wordt met 7 verschoven. Voorbeelden: 25 wordt opgeslagen als 1 byte 0x19, 130 = 2 bytes 0x82 0x01, 65535 = 3 bytes 0xFF 0xFF 0x03.
Duplicaat-nodes:
Ook wordt een nieuwe vlag toegevoegd voor het opslaan van recordnummers op elke node (niet-bladpagina’s). Dit versnelt indexophaling bij veel duplicaten. De vlag is btr_all_recordnumber (16). Met deze toegevoegde informatie wordt sleutelopzoeking bij invoegingen/verwijderingen met veel duplicaten (NULL’s in foreign keys bijvoorbeeld) veel sneller (zoals de garbage collection!). Daarnaast slaan duplicaat-nodes (lengte = 0) hun lengte-informatie niet op; 3 bits van het eerste opgeslagen byte worden gebruikt om te bepalen of deze node een duplicaat is. Naast de ZERO_LENGTH (4) zijn er ook END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) en ONE_LENGTH (5) markeringen. Nummers 6 en 7 zijn gereserveerd voor toekomstig gebruik.
Jump-nodes:
Een jump node is een verwijzing naar een node ergens op de pagina.
Het bevat offset-informatie over de specifieke node en de prefixgegevens van de verwezen node, maar op de jump-nodes zelf wordt ook prefixcompressie toegepast.
Idealiter wordt een nieuwe jump node gegenereerd na de eerste node die wordt gevonden na elke jumpAreaSize, maar dat is alleen het geval bij het deactiveren/activeren van een index of het invoegen van nodes in dezelfde volgorde als waarin ze in de index worden opgeslagen.
Als nodes worden ingevoegd tussen twee jump node-verwijzingen, worden alleen de offsets bijgewerkt, maar alleen als de offsets een specifieke drempel niet overschrijden (+/-10%).
Wanneer een node wordt verwijderd, worden alleen offsets bijgewerkt of wordt een jump node verwijderd. Dit betekent dat er een klein gat kan bestaan tussen de laatste jump node en de eerste node, zodat we geen tijd verspillen aan het genereren van nieuwe jump-nodes.
De prefix en lengte worden ook opgeslagen met variabele lengtecodering.
Voorbeeldgegevens:
(x) = grootte 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) | … |
Aanwijzer na vaste header = 0x22
Aanwijzer na jump-info = 0x29
Aanwijzer naar eerste jump node = 0x29 + 6 (jump node 1) + 5 (jump node 2) = 0x34
Jump node 1 verwijst naar de node die FIREBIRD als gegevens vertegenwoordigt, omdat deze node een prefix van 2 heeft, worden de eerste 2 tekens FI ook op de jump node opgeslagen.
Onze volgende jump node verwijst naar een node die FUEL vertegenwoordigt met ook een prefix van 2. Dus jump node 2 zou FU moeten bevatten, maar onze vorige node bevatte al de F, dus door prefixcompressie wordt deze genegeerd en wordt alleen U opgeslagen.
NULL-status:
De gegevens die moeten worden opgeslagen, worden bepaald in de procedure compress() in btr.cpp.
Voor ASC (oplopende) indexen worden geen gegevens opgeslagen (sleutel heeft lengte nul). Dit plaatst ze automatisch als eerste vermelding in de index en dus in de juiste volgorde (voor indexen met één veld zijn node-lengte en prefix nul).
DESC (aflopende) indexen slaan een enkel byte op met de waarde 0xFF (255). Om onderscheid te maken tussen een waarde (lege string kan 255 zijn) en een NULL-status voegen we een byte van 0xFE (254) toe aan het begin van de gegevens. Dit wordt alleen gedaan voor waarden die beginnen met 0xFF (255) of 0xFE (254), zodat we de juiste volgorde behouden.
Voorbeelden:
| nodes ASC-index, 1 segment | |||
| prefix | lengte | opgeslagen gegevens | werkelijke waarde/status |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| nodes DESC-index, 1 segment | |||
| prefix | lengte | opgeslagen gegevens | werkelijke waarde/status |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| nodes ASC-index, 3 segmenten | |||
| prefix | lengte | opgeslagen gegevens | werkelijke waarde/status |
| 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 |
| … | … | … | … |
| nodes DESC-index, 3 segmenten | |||
| prefix | lengte | opgeslagen gegevens | werkelijke waarde/status |
| 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