Firebird 2.0（ODS 11及以上版本）的Firebird索引结构
Firebird インデックス構造 ODS11 以降
新しい構造の理由は次のとおりです：
- 多数の重複からインデックスキーを削除する際のサポート向上（遅いガベージコレクションの原因となっていた）
- 32ビットを超えるレコード番号のサポート（40ビット）
- インデックスキーサイズの拡大（ページサイズの1/4）
既存の構造（ODS10以前）：
| ヘッダー | ノード | ノード | ノード | ノード | ノード | ノード | |||
| ノード | ノード | ノード | ノード | ノード | ノード | ノード | … | 終端マーカー |
ヘッダー =
typedef struct btr {
struct pag btr\_header;
SLONG btr\_sibling; // 右側の兄弟ページ
SLONG btr\_left\_sibling; // 左側の兄弟ページ
SLONG btr\_prefix\_total; // ページ上のすべてのプレフィックスの合計
USHORT btr\_relation; // 整合性チェック用のリレーションID
USHORT btr\_length; // バケット内のデータ長
UCHAR btr\_id; // 整合性チェック用のインデックスID
UCHAR btr\_level; // インデックスレベル（0 = リーフ）
struct btn btr\_nodes\[1.;
};
ノード =
struct btn {
UCHAR btn\_prefix; // 圧縮プレフィックスのサイズ
UCHAR btn\_length; // ノード内のデータ長
UCHAR btn\_number\[4.; // ページ番号またはレコード番号
UCHAR btn\_data\[1.;
};
終端マーカー = END_BUCKET または END_LEVEL
これらは、リーフノードの場合はレコード番号の代わりに、非リーフノードの場合はページ番号の代わりに配置されます。
ノードが END_BUCKET マーカーの場合、次の兄弟ページの最初のノードと同じデータを含む必要があります。
END_LEVEL マーカーの場合、プレフィックスと長さはゼロであり、データは含まれません。
また、各レベルの最初のノード（リーフページを除く）には、退化したゼロ長ノードが含まれます。
新しい ODS11 構造：
| ヘッダー | ジャンプ情報 | ジャンプノード | … | ノード [*] | ノード | ノード | |||
| ノード | ノード | ノード | ノード | ノード | ノード | ノード | … | 終端マーカー |
ジャンプ情報 =
struct IndexJumpInfo {
USHORT firstNodeOffset; // ページ内の最初のノードへのオフセット \[\*\]
USHORT jumpAreaSize; // 新しいジャンプノードが作成される前の領域サイズ
UCHAR jumpers; // ページ内のジャンプノード数（最大255）
};
ジャンプノード =
struct IndexJumpNode {
UCHAR\* nodePointer; // このノードをページから読み取れる位置へのポインタ
USHORT prefix; // 前のジャンプノードに対するプレフィックスの長さ
USHORT length; // ジャンプノード内のデータ長（プレフィックスと合わせて
参照ノードのプレフィックスとなる）
USHORT offset; // ページ内のノードへのオフセット
UCHAR\* data; // データはここから読み取れる
};
新しいインデックス構造の新しいフラグ：
ヘッダー->pag_flags に新しいフラグが追加されます。
フラグ btr_large_keys (32) は、圧縮された長さ/プレフィックスとレコード番号を格納するためのものです。これは、長さとプレフィックスがページサイズの1/4（4096ページサイズの場合1024）まで可能になり、将来ディスク構造を再度変更することなく簡単に拡張できることを意味します。また、レコード番号も例えば40ビットに簡単に拡張できます。これらの数値は、7ビットごとに格納され、1ビット（最上位）がマーカーとして使用されます（可変長エンコーディング）。格納する必要がある新しいバイトはすべて7ビットシフトされます。例：25は1バイト 0x19 として格納、130 = 2バイト 0x82 0x01、65535 = 3バイト 0xFF 0xFF 0x03。
重複ノード：
また、すべてのノード（非リーフページ）にレコード番号を格納するための新しいフラグも追加されます。これにより、多数の重複がある場合のインデックス取得が高速化されます。フラグは btr_all_recordnumber (16) です。この追加情報により、多数の重複（外部キーのNULLなど）がある場合の挿入/削除時のキールックアップが大幅に高速化されます（ガベージコレクションも同様です！）。さらに、重複ノード（長さ = 0）は長さ情報を格納しないため、最初に格納されるバイトの3ビットを使用して、このノードが重複であるかどうかを判断します。ZERO_LENGTH (4) に加えて、END_LEVEL (1)、END_BUCKET (2)、ZERO_PREFIX_ZERO_LENGTH (3)、ONE_LENGTH (5) マーカーもあります。番号6と7は将来の使用のために予約されています。
ジャンプノード：
ジャンプノードは、ページ内のどこかにあるノードへの参照です。
特定のノードへのオフセット情報と、参照されるノードからのプレフィックスデータが含まれますが、ジャンプノード自体にもプレフィックス圧縮が行われます。
理想的には、jumpAreaSize ごとに見つかった最初のノードの後に新しいジャンプノードが生成されますが、これはインデックスの非アクティブ化/アクティブ化、またはインデックスに格納される順序と同じ順序でノードを挿入する場合にのみ発生します。
2つのジャンプノード参照の間にノードが挿入された場合、オフセットのみが更新されますが、オフセットが特定のしきい値（+/-10％）を超えない場合に限ります。
ノードが削除された場合、オフセットのみが更新されるか、ジャンプノードが削除されます。つまり、最後のジャンプノードと最初のノードの間に小さな隙間が存在する可能性があり、新しいジャンプノードの生成に時間を費やすことはありません。
プレフィックスと長さも可変長エンコーディングで格納されます。
データ例：
(x) = xバイト単位のサイズ
| ヘッダー (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) | … |
固定ヘッダー後のポインタ = 0x22
ジャンプ情報後のポインタ = 0x29
最初のジャンプノードへのポインタ = 0x29 + 6（ジャンプノード1）+ 5（ジャンプノード2）= 0x34
ジャンプノード1は、データとして FIREBIRD を表すノードを参照しています。このノードのプレフィックスは2なので、最初の2文字 FI がジャンプノードにも格納されます。
次のジャンプノードは、プレフィックスも2の FUEL を表すノードを指しています。したがって、ジャンプノード2には FU が含まれるはずですが、前のノードにはすでに F が含まれているため、プレフィックス圧縮によりこれは無視され、U のみが格納されます。
NULL 状態：
格納する必要があるデータは、btr.cpp の compress() プロシージャで決定されます。
ASC（昇順）インデックスの場合、データは格納されません（キーはゼロ長）。これにより、自動的にインデックスの最初のエントリとして配置され、正しい順序になります（単一フィールドインデックスの場合、ノードの長さとプレフィックスはゼロです）。
DESC（降順）インデックスは、値 0xFF (255) の単一バイトを格納します。値（空文字列は255になる可能性があります）と NULL 状態を区別するために、データの先頭に 0xFE (254) のバイトを挿入します。これは、0xFF (255) または 0xFE (254) で始まる値に対してのみ行われ、正しい順序を維持します。
例：
| ASC インデックスのノード、1セグメント | |||
| プレフィックス | 長さ | 格納データ | 実際の値/状態 |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| DESC インデックスのノード、1セグメント | |||
| プレフィックス | 長さ | 格納データ | 実際の値/状態 |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| ASC インデックスのノード、3セグメント | |||
| プレフィックス | 長さ | 格納データ | 実際の値/状態 |
| 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 インデックスのノード、3セグメント | |||
| プレフィックス | 長さ | 格納データ | 実際の値/状態 |
| 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