Struktura indexů Firebird pro Firebird 2.0 (ODS 11 a vyšší)
Struktura indexů Firebird ODS11 a vyšší
Důvodem pro novou strukturu je:
- lepší podpora mazání indexového klíče z mnoha duplicit (způsobovalo pomalý garbage collection)
- podpora větších čísel záznamů než 32 bitů (40 bitů)
- zvětšení velikosti indexového klíče (1/4 velikosti stránky)
Stávající struktura (ODS10 a nižší):
| 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; // stránka pravého sourozence
SLONG btr\_left\_sibling; // stránka levého sourozence
SLONG btr\_prefix\_total; // součet všech prefixů na stránce
USHORT btr\_relation; // ID relace pro konzistenci
USHORT btr\_length; // délka dat v bucketu
UCHAR btr\_id; // ID indexu pro konzistenci
UCHAR btr\_level; // úroveň indexu (0 = list)
struct btn btr\_nodes\[1.;
};
node =
struct btn {
UCHAR btn\_prefix; // velikost komprimovaného prefixu
UCHAR btn\_length; // délka dat v uzlu
UCHAR btn\_number\[4.; // číslo stránky nebo záznamu
UCHAR btn\_data\[1.;
};
end marker = END_BUCKET nebo END_LEVEL
Tyto jsou místo čísla záznamu pro listové uzly a místo čísla stránky pro nelistové uzly.
Pokud je uzel marker END_BUCKET, měl by obsahovat stejná data jako první uzel na další sourozenecké stránce.
U markeru END_LEVEL jsou prefix a délka nulové, tedy neobsahuje žádná data.
Také každý první uzel na úrovni (kromě listových stránek) obsahuje degenerovaný uzel s nulovou délkou.
Nová struktura ODS11:
| header | jump info | jump nodes | … | node [*] | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
jump info =
struct IndexJumpInfo {
USHORT firstNodeOffset; // offset k prvnímu uzlu na stránce \[\*\]
USHORT jumpAreaSize; // velikost oblasti před vytvořením nového jump uzlu
UCHAR jumpers; // počet jump uzlů na stránce, maximum 255
};
jump node =
struct IndexJumpNode {
UCHAR\* nodePointer; // ukazatel na místo, odkud lze uzel číst ze stránky
USHORT prefix; // délka prefixu proti předchozímu jump uzlu
USHORT length; // délka dat v jump uzlu (spolu s prefixem toto
je prefix pro ukazující uzel)
USHORT offset; // offset k uzlu na stránce
UCHAR\* data; // Data lze číst odtud
};
Nový příznak pro novou strukturu indexu:
Do header->pag_flags jsou přidány nové příznaky.
Příznak btr_large_keys (32) slouží pro ukládání komprimované délky/prefixu a čísla záznamu. To také znamená, že délka a prefix mohou být až 1/4 velikosti stránky (1024 pro velikost stránky 4096) a lze je snadno v budoucnu rozšířit bez další změny diskové struktury. Také číslo záznamu lze snadno rozšířit například na 40 bitů. Tato čísla jsou ukládána po 7 bitech s 1 bitem (nejvyšší) jako markerem (proměnná délka kódování). Každý nový bajt, který je třeba uložit, je posunut o 7. Příklady: 25 je uloženo jako 1 bajt 0x19, 130 = 2 bajty 0x82 0x01, 65535 = 3 bajty 0xFF 0xFF 0x03.
Duplicitní uzly:
Také je přidán nový příznak pro ukládání čísla záznamu na každém uzlu (nelistové stránky). To urychluje vyhledávání v indexu při mnoha duplicitách. Příznak je btr_all_recordnumber (16). S touto přidanou informací se vyhledávání klíčů při vkládání/mazání s mnoha duplicitami (např. NULL v cizích klíčích) stává mnohem rychlejším (jako garbage collection!). Kromě toho duplicitní uzly (délka = 0) neukládají informaci o své délce, 3 bity z prvního uloženého bajtu se používají k určení, zda je tento uzel duplicitní. Kromě ZERO_LENGTH (4) existují také markery END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) a ONE_LENGTH (5). Čísla 6 a 7 jsou vyhrazena pro budoucí použití.
Jump uzly:
Jump uzel je odkaz na uzel někde na stránce.
Obsahuje informaci o offsetu konkrétního uzlu a prefixová data z odkazovaného uzlu, ale na samotných jump uzlech je také provedena prefixová komprese.
Ideálně je nový jump uzel generován po prvním uzlu, který je nalezen po každém jumpAreaSize, ale to platí pouze při deaktivaci/aktivaci indexu nebo vkládání uzlů ve stejném pořadí, v jakém budou uloženy v indexu.
Pokud jsou uzly vkládány mezi dva odkazy jump uzlů, aktualizují se pouze offsety, ale pouze pokud offsety nepřekročí specifický práh (+/-10 %).
Když je uzel smazán, aktualizují se pouze offsety nebo je jump uzel odstraněn. To znamená, že mezi posledním jump uzlem a prvním uzlem může vzniknout malá mezera, takže neztrácíme čas generováním nových jump uzlů.
Prefix a délka jsou také ukládány pomocí proměnné délky kódování.
Příklad dat:
(x) = velikost v x bajtech
| 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) | … |
Ukazatel za pevným headerem = 0x22
Ukazatel za jump info = 0x29
Ukazatel na první jump uzel = 0x29 + 6 (jump uzel 1) + 5 (jump uzel 2) = 0x34
Jump uzel 1 odkazuje na uzel, který představuje FIREBIRD jako data, protože tento uzel má prefix 2, první 2 znaky FI jsou uloženy také na jump uzlu.
Náš další jump uzel ukazuje na uzel, který představuje FUEL s také prefixem 2. Takže jump uzel 2 by měl obsahovat FU, ale náš předchozí uzel již obsahoval F, takže kvůli prefixové kompresi je toto ignorováno a je uloženo pouze U.
Stav NULL:
Data, která je třeba uložit, jsou určena v proceduře compress() v btr.cpp.
Pro ASC (vzestupné) indexy nebudou uložena žádná data (klíč má nulovou délku). To je automaticky umístí jako první položku v indexu, a tedy ve správném pořadí (pro index s jedním polem jsou délka uzlu a prefix nulové).
DESC (sestupné) indexy uloží jeden bajt s hodnotou 0xFF (255). Pro rozlišení mezi hodnotou (prázdný řetězec může být 255) a stavem NULL vložíme na začátek dat bajt 0xFE (254). To se provádí pouze pro hodnoty, které začínají 0xFF (255) nebo 0xFE (254), takže zachováme správné pořadí.
Příklady:
| uzly ASC index, 1 segment | |||
| prefix | délka | uložená data | skutečná hodnota/stav |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| uzly DESC index, 1 segment | |||
| prefix | délka | uložená data | skutečná hodnota/stav |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| uzly ASC index, 3 segmenty | |||
| prefix | délka | uložená data | skutečná hodnota/stav |
| 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 |
| … | … | … | … |
| uzly DESC index, 3 segmenty | |||
| prefix | délka | uložená data | skutečná hodnota/stav |
| 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