Struktura indeksów Firebird dla Firebird 2.0 (ODS 11 i wyższe)
Struktura indeksów Firebird ODS11 i nowsze
Powodem nowej struktury jest:
- lepsze wsparcie dla usuwania klucza indeksu spośród wielu duplikatów (powodowało to wolne odśmiecaczanie)
- wsparcie dla większych numerów rekordów niż 32-bity (40 bitów)
- zwiększenie rozmiaru klucza indeksu (1/4 rozmiaru strony)
Istniejąca struktura (ODS10 i niższe):
| nagłówek | węzeł | węzeł | węzeł | węzeł | węzeł | węzeł | |||
| węzeł | węzeł | węzeł | węzeł | węzeł | węzeł | węzeł | … | znacznik końca |
nagłówek =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // prawa strona siostrzana
SLONG btr\_left\_sibling; // lewa strona siostrzana
SLONG btr\_prefix\_total; // suma wszystkich prefiksów na stronie
USHORT btr\_relation; // identyfikator relacji dla spójności
USHORT btr\_length; // długość danych w zasobniku
UCHAR btr\_id; // identyfikator indeksu dla spójności
UCHAR btr\_level; // poziom indeksu (0 = liść)
struct btn btr\_nodes\[1.;
};
węzeł =
struct btn {
UCHAR btn\_prefix; // rozmiar skompresowanego prefiksu
UCHAR btn\_length; // długość danych w węźle
UCHAR btn\_number\[4.; // numer strony lub rekordu
UCHAR btn\_data\[1.;
};
znacznik końca = END_BUCKET lub END_LEVEL
Są one używane zamiast numeru rekordu dla węzłów liściowych i zamiast numeru strony dla węzłów nieliściowych.
Jeśli węzeł jest znacznikiem END_BUCKET, powinien zawierać te same dane co pierwszy węzeł na następnej stronie siostrzanej.
Przy znaczniku END_LEVEL prefiks i długość są zerowe, więc nie zawiera on danych.
Ponadto każdy pierwszy węzeł na poziomie (z wyjątkiem stron liściowych) zawiera zdegenerowany węzeł o zerowej długości.
Nowa struktura ODS11:
| nagłówek | informacje o skokach | węzły skoków | … | węzeł [*] | węzeł | węzeł | |||
| węzeł | węzeł | węzeł | węzeł | węzeł | węzeł | węzeł | … | znacznik końca |
informacje o skokach =
struct IndexJumpInfo {
USHORT firstNodeOffset; // przesunięcie do pierwszego węzła na stronie \[\*\]
USHORT jumpAreaSize; // rozmiar obszaru przed utworzeniem nowego węzła skoku
UCHAR jumpers; // liczba węzłów skoków na stronie, maksymalnie 255
};
węzeł skoku =
struct IndexJumpNode {
UCHAR\* nodePointer; // wskaźnik do miejsca, skąd można odczytać ten węzeł ze strony
USHORT prefix; // długość prefiksu względem poprzedniego węzła skoku
USHORT length; // długość danych w węźle skoku (razem z prefiksem jest to
prefiks dla wskazywanego węzła)
USHORT offset; // przesunięcie do węzła na stronie
UCHAR\* data; // Dane można odczytać stąd
};
Nowa flaga dla nowej struktury indeksu:
Do nagłówka header->pag_flags dodano nowe flagi.
Flaga btr_large_keys (32) służy do przechowywania skompresowanej długości/prefiksu i numeru rekordu. Oznacza to również, że długość i prefiks mogą wynosić do 1/4 rozmiaru strony (1024 dla rozmiaru strony 4096) i można je łatwo rozszerzyć w przyszłości bez ponownej zmiany struktury dysku. Numer rekordu można również łatwo rozszerzyć na przykład do 40 bitów. Liczby te są przechowywane co 7 bitów z 1 bitem (najwyższym) jako znacznikiem (kodowanie o zmiennej długości). Każdy nowy bajt, który należy zapisać, jest przesuwany o 7. Przykłady: 25 jest przechowywane jako 1 bajt 0x19, 130 = 2 bajty 0x82 0x01, 65535 = 3 bajty 0xFF 0xFF 0x03.
Węzły duplikatów:
Dodano również nową flagę do przechowywania numeru rekordu na każdym węźle (strony nieliściowe). Przyspiesza to wyszukiwanie w indeksie przy wielu duplikatach. Flaga to btr_all_recordnumber (16). Dzięki tej dodatkowej informacji wyszukiwanie kluczy przy wstawianiu/usuwaniu z wieloma duplikatami (np. NULL w kluczach obcych) staje się znacznie szybsze (takie jak odśmiecaczanie!). Ponadto węzły duplikatów (długość = 0) nie przechowują informacji o swojej długości - 3 bity z pierwszego przechowywanego bajtu są używane do określenia, czy ten węzeł jest duplikatem. Oprócz ZERO_LENGTH (4) istnieją również znaczniki END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) i ONE_LENGTH (5). Liczby 6 i 7 są zarezerwowane do przyszłego użycia.
Węzły skoków:
Węzeł skoku to odniesienie do węzła gdzieś na stronie.
Zawiera informacje o przesunięciu do konkretnego węzła oraz dane prefiksu z odwoływanego węzła, ale na samych węzłach skoków również wykonywana jest kompresja prefiksu.
Idealnie nowy węzeł skoku jest generowany po pierwszym węźle znalezionym po każdym jumpAreaSize, ale ma to miejsce tylko przy dezaktywacji/aktywacji indeksu lub wstawianiu węzłów w tej samej kolejności, w jakiej będą przechowywane w indeksie.
Jeśli węzły są wstawiane między dwa odniesienia węzłów skoków, aktualizowane są tylko przesunięcia, ale tylko jeśli przesunięcia nie przekraczają określonego progu (+/-10 %).
Gdy węzeł jest usuwany, aktualizowane są tylko przesunięcia lub węzeł skoku jest usuwany. Oznacza to, że między ostatnim węzłem skoku a pierwszym węzłem może istnieć niewielka dziura, więc nie tracimy czasu na generowanie nowych węzłów skoków.
Prefiks i długość są również przechowywane przy użyciu kodowania o zmiennej długości.
Przykładowe dane:
(x) = rozmiar w x bajtach
| nagłówek (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) | … |
Wskaźnik po stałym nagłówku = 0x22
Wskaźnik po informacjach o skokach = 0x29
Wskaźnik do pierwszego węzła skoku = 0x29 + 6 (węzeł skoku 1) + 5 (węzeł skoku 2) = 0x34
Węzeł skoku 1 odwołuje się do węzła reprezentującego FIREBIRD jako dane, ponieważ ten węzeł ma prefiks 2, pierwsze 2 znaki FI są również przechowywane na węźle skoku.
Nasz następny węzeł skoku wskazuje na węzeł reprezentujący FUEL również z prefiksem 2. Zatem węzeł skoku 2 powinien zawierać FU, ale nasz poprzedni węzeł zawierał już F, więc z powodu kompresji prefiksu ten znak jest ignorowany i przechowywane jest tylko U.
Stan NULL:
Dane, które należy przechowywać, są określane w procedurze compress() w pliku btr.cpp.
Dla indeksów ASC (rosnących) nie będą przechowywane żadne dane (klucz ma zerową długość). To automatycznie umieszcza je jako pierwszy wpis w indeksie, a tym samym we właściwej kolejności (dla indeksu jednopolowego długość węzła i prefiks są zerowe).
Indeksy DESC (malejące) będą przechowywać pojedynczy bajt o wartości 0xFF (255). Aby odróżnić wartość (pusty ciąg może być 255) od stanu NULL, wstawiamy bajt 0xFE (254) na początku danych. Jest to wykonywane tylko dla wartości zaczynających się od 0xFF (255) lub 0xFE (254), aby zachować właściwą kolejność.
Przykłady:
| węzły indeksu ASC, 1 segment | |||
| prefiks | długość | przechowywane dane | rzeczywista wartość/stan |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| węzły indeksu DESC, 1 segment | |||
| prefiks | długość | przechowywane dane | rzeczywista wartość/stan |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| węzły indeksu ASC, 3 segmenty | |||
| prefiks | długość | przechowywane dane | rzeczywista wartość/stan |
| 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 |
| … | … | … | … |
| węzły indeksu DESC, 3 segmenty | |||
| prefiks | długość | przechowywane dane | rzeczywista wartość/stan |
| 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