Firebird İndeks Yapısı Firebird 2.0 (ODS 11 ve üzeri) için
Firebird İndeks Yapısı ODS11 ve üzeri
Yeni yapının nedeni şudur:
- çok sayıda kopya arasından bir indeks anahtarının silinmesine daha iyi destek (yavaş çöp toplamaya neden oluyordu)
- 32 bitten daha büyük kayıt numaralarını destekleme (40 bit)
- indeks anahtar boyutunu artırma (sayfa boyutunun 1/4’ü)
Mevcut yapı (ODS10 ve altı):
| başlık | düğüm | düğüm | düğüm | düğüm | düğüm | düğüm | |||
| düğüm | düğüm | düğüm | düğüm | düğüm | düğüm | düğüm | … | bitiş işareti |
başlık =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // sağ kardeş sayfa
SLONG btr\_left\_sibling; // sol kardeş sayfa
SLONG btr\_prefix\_total; // sayfadaki tüm öneklerin toplamı
USHORT btr\_relation; // tutarlılık için ilişki kimliği
USHORT btr\_length; // kovadaki veri uzunluğu
UCHAR btr\_id; // tutarlılık için indeks kimliği
UCHAR btr\_level; // indeks seviyesi (0 = yaprak)
struct btn btr\_nodes\[1.;
};
düğüm =
struct btn {
UCHAR btn\_prefix; // sıkıştırılmış önek boyutu
UCHAR btn\_length; // düğümdeki veri uzunluğu
UCHAR btn\_number\[4.; // sayfa veya kayıt numarası
UCHAR btn\_data\[1.;
};
bitiş işareti = END_BUCKET veya END_LEVEL
Bunlar yaprak düğümler için kayıt numarası yerine ve yaprak olmayan düğümler için sayfa numarası yerine kullanılır.
Düğüm bir END_BUCKET işareti ise, sonraki kardeş sayfadaki ilk düğümle aynı veriyi içermelidir.
END_LEVEL işaretiyle önek ve uzunluk sıfırdır, bu nedenle veri içermez.
Ayrıca bir seviyedeki her ilk düğüm (yaprak sayfalar hariç) dejenere sıfır uzunluklu bir düğüm içerir.
Yeni ODS11 yapısı:
| başlık | atlama bilgisi | atlama düğümleri | … | düğüm [*] | düğüm | düğüm | |||
| düğüm | düğüm | düğüm | düğüm | düğüm | düğüm | düğüm | … | bitiş işareti |
atlama bilgisi =
struct IndexJumpInfo {
USHORT firstNodeOffset; // sayfadaki ilk düğüme uzaklık \[\*\]
USHORT jumpAreaSize; // yeni bir atlama düğümü yapılmadan önceki alan boyutu
UCHAR jumpers; // sayfadaki atlama düğümü sayısı, maksimum 255
};
atlama düğümü =
struct IndexJumpNode {
UCHAR\* nodePointer; // bu düğümün sayfadan okunabileceği işaretçi
USHORT prefix; // önceki atlama düğümüne karşı önek uzunluğu
USHORT length; // atlama düğümündeki veri uzunluğu (önekle birlikte bu
işaret eden düğüm için önektir)
USHORT offset; // sayfadaki düğüme uzaklık
UCHAR\* data; // Veri buradan okunabilir
};
Yeni indeks yapısı için yeni bayrak:
header->pag_flags alanına yeni bayraklar eklenir.
btr_large_keys (32) bayrağı, sıkıştırılmış uzunluk/önek ve kayıt numarasını saklamak içindir. Bu aynı zamanda uzunluk ve önekin sayfa boyutunun 1/4’üne kadar (4096 sayfa boyutu için 1024) çıkabilmesi anlamına gelir ve disk yapısını tekrar değiştirmeden gelecekte kolayca genişletilebilir. Ayrıca kayıt numarası örneğin 40 bit’e kolayca genişletilebilir. Bu sayılar, işaretçi olarak 1 bit (en yüksek) ile 7 bitlik gruplar halinde saklanır (değişken uzunluklu kodlama). Saklanması gereken her yeni bayt 7 ile kaydırılır. Örnekler: 25, 1 bayt 0x19 olarak saklanır; 130 = 2 bayt 0x82 0x01; 65535 = 3 bayt 0xFF 0xFF 0x03.
Kopya düğümler:
Ayrıca her düğümde (yaprak olmayan sayfalar) kayıt numarası saklamak için yeni bir bayrak eklenir. Bu, çok sayıda kopya içeren indeks erişimini hızlandırır. Bayrak btr_all_recordnumber (16)‘dır. Bu eklenen bilgiyle, çok sayıda kopya içeren ekleme/silme işlemlerinde (örneğin yabancı anahtarlardaki NULL’lar) anahtar araması çok daha hızlı hale gelir (çöp toplama gibi!). Ayrıca kopya düğümler (uzunluk = 0) uzunluk bilgilerini saklamaz; ilk saklanan bayttan 3 bit, bu düğümün bir kopya olup olmadığını belirlemek için kullanılır. ZERO_LENGTH (4) dışında ayrıca END_LEVEL (1), END_BUCKET (2), ZERO_PREFIX_ZERO_LENGTH (3) ve ONE_LENGTH (5) işaretleri de vardır. 6 ve 7 numaraları gelecekteki kullanım için ayrılmıştır.
Atlama düğümleri:
Atlama düğümü, sayfadaki bir düğüme referanstır.
Belirli düğüm hakkında uzaklık bilgisi ve başvurulan düğümün önek verilerini içerir, ancak atlama düğümlerinin kendisinde de önek sıkıştırması yapılır.
İdeal olarak, her jumpAreaSize’dan sonra bulunan ilk düğümden sonra yeni bir atlama düğümü üretilir, ancak bu yalnızca bir indeksin devre dışı bırakılması/etkinleştirilmesi veya düğümlerin indekste saklanacakları sırayla eklenmesi durumunda geçerlidir.
İki atlama düğümü referansı arasına düğümler eklenirse yalnızca uzaklıklar güncellenir, ancak yalnızca uzaklıklar belirli bir eşiği aşmazsa (+/-%10).
Bir düğüm silindiğinde yalnızca uzaklıklar güncellenir veya bir atlama düğümü kaldırılır. Bu, son atlama düğümü ile ilk düğüm arasında küçük bir boşluk olabileceği anlamına gelir, bu nedenle yeni atlama düğümleri üretmek için zaman harcamayız.
Önek ve uzunluk da değişken uzunluklu kodlamayla saklanır.
Örnek veri:
(x) = x bayt cinsinden boyut
| başlık (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) | … |
Sabit başlıktan sonraki işaretçi = 0x22
Atlama bilgisinden sonraki işaretçi = 0x29
İlk atlama düğümüne işaretçi = 0x29 + 6 (atlama düğümü 1) + 5 (atlama düğümü 2) = 0x34
Atlama düğümü 1, veri olarak FIREBIRD’i temsil eden düğüme referans verir, çünkü bu düğümün öneki 2’dir, ilk 2 karakter FI de atlama düğümünde saklanır.
Sonraki atlama düğümümüz, öneki de 2 olan FUEL’i temsil eden bir düğüme işaret eder. Bu nedenle atlama düğümü 2 FU içermelidir, ancak önceki düğümümüz zaten F’yi içeriyordu, bu nedenle önek sıkıştırması nedeniyle bu yok sayılır ve yalnızca U saklanır.
NULL durumu:
Saklanması gereken veri, btr.cpp içindeki compress() prosedüründe belirlenir.
ASC (artan) indeksler için veri saklanmaz (anahtar sıfır uzunluktadır). Bu, onları otomatik olarak indekste ilk giriş olarak yerleştirir ve böylece doğru sırayı sağlar (tek alanlı indeks için düğüm uzunluğu ve önek sıfırdır).
DESC (azalan) indeksler, 0xFF (255) değerinde tek bir bayt saklar. Bir değer (boş dize 255 olabilir) ile NULL durumu arasında ayrım yapmak için verinin önüne 0xFE (254) baytı ekleriz. Bu yalnızca 0xFF (255) veya 0xFE (254) ile başlayan değerler için yapılır, böylece doğru sırayı koruruz.
Örnekler:
| ASC indeks düğümleri, 1 segment | |||
| önek | uzunluk | saklanan veri | gerçek değer/durum |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| DESC indeks düğümleri, 1 segment | |||
| önek | uzunluk | saklanan veri | gerçek değer/durum |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| ASC indeks düğümleri, 3 segment | |||
| önek | uzunluk | saklanan veri | gerçek değer/durum |
| 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 |
| … | … | … | … |
| DESC indeks düğümleri, 3 segment | |||
| önek | uzunluk | saklanan veri | gerçek değer/durum |
| 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