Firebird 2.0（ODS 11及更高版本）的Firebird索引结构
Firebird 索引结构 ODS11 及更高版本
新结构的原因：
- 更好地支持从大量重复项中删除索引键（导致垃圾回收缓慢）
- 支持大于 32 位的记录号（40 位）
- 增加索引键大小（页面大小的 1/4）
现有结构（ODS10 及更低版本）：
| 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; // 右侧兄弟页面
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.;
};
node =
struct btn {
UCHAR btn\_prefix; // 压缩前缀的大小
UCHAR btn\_length; // 节点中数据的长度
UCHAR btn\_number\[4.; // 页面号或记录号
UCHAR btn\_data\[1.;
};
end marker = END_BUCKET 或 END_LEVEL
这些用于叶节点的记录号和用于非叶节点的页面号。
如果节点是 END_BUCKET 标记，则它应包含与下一个兄弟页面上第一个节点相同的数据。
对于 END_LEVEL 标记，前缀和长度均为零，因此不包含数据。
此外，每个级别上的第一个节点（叶页面除外）都包含一个退化的零长度节点。
新的 ODS11 结构：
| header | jump info | jump nodes | … | node [*] | node | node | |||
| node | node | node | node | node | node | node | … | end marker |
jump info =
struct IndexJumpInfo {
USHORT firstNodeOffset; // 页面中第一个节点的偏移量 \[\*\]
USHORT jumpAreaSize; // 创建新跳转节点之前的区域大小
UCHAR jumpers; // 页面中跳转节点的数量，最大为 255
};
jump node =
struct IndexJumpNode {
UCHAR\* nodePointer; // 指向可以从页面读取此节点的位置的指针
USHORT prefix; // 相对于前一个跳转节点的前缀长度
USHORT length; // 跳转节点中数据的长度（连同前缀一起作为指向节点的前缀）
USHORT offset; // 页面中节点的偏移量
UCHAR\* data; // 可以从此处读取数据
};
新索引结构的新标志：
在 header->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 后找到的第一个节点之后生成一个新的跳转节点，但这仅在索引被停用/激活或按与索引中存储顺序相同的顺序插入节点时才会发生。
如果在两个跳转节点引用之间插入节点，则只更新偏移量，但前提是偏移量不超过特定阈值（+/-10%）。
当删除节点时，只更新偏移量或移除跳转节点。这意味着最后一个跳转节点和第一个节点之间可能存在一个小空洞，因此我们不会浪费时间生成新的跳转节点。
前缀和长度也使用可变长度编码存储。
示例数据：
(x) = 以 x 字节为单位的大小
| 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) | … |
固定 header 后的指针 = 0x22
jump info 后的指针 = 0x29
第一个跳转节点的指针 = 0x29 + 6（跳转节点 1）+ 5（跳转节点 2）= 0x34
跳转节点 1 引用表示 FIREBIRD 作为数据的节点，因为该节点的前缀为 2，所以前 2 个字符 FI 也存储在跳转节点上。
我们的下一个跳转节点指向表示 FUEL 的节点，其前缀也为 2。因此跳转节点 2 应包含 FU，但我们的前一个节点已经包含 F，因此由于前缀压缩，这个 F 被忽略，只存储 U。
NULL 状态：
需要存储的数据在 btr.cpp 中的 compress() 过程中确定。
对于 ASC（升序）索引，不存储数据（键为零长度）。这将自动将它们放在索引中的第一个条目，从而保持正确的顺序（对于单字段索引，节点长度和前缀为零）。
DESC（降序）索引将存储一个值为 0xFF (255) 的单个字节。为了区分值（空字符串可以是 255）和 NULL 状态，我们在数据前面插入一个 0xFE (254) 字节。这仅对以 0xFF (255) 或 0xFE (254) 开头的值执行，因此我们保持正确的顺序。
示例：
| 节点 ASC 索引，1 个段 | |||
| prefix | length | stored data | real value/state |
| 0 | 0 | NULL | |
| 0 | 0 | NULL | |
| 0 | 1 | x65 (A) | A |
| 1 | 1 | x65 (A) | AA |
| … | … | … | … |
| 节点 DESC 索引，1 个段 | |||
| prefix | length | stored data | real value/state |
| … | … | … | … |
| 0 | 2 | xFE xFE (ю) x4A (J) | 0xFE 0x4A |
| 1 | 1 | xFF (я) | 0xFF |
| 0 | 1 | xFF | NULL |
| 1 | 0 | xFF | NULL |
| END_LEVEL |
| 节点 ASC 索引，3 个段 | |||
| prefix | length | stored data | real value/state |
| 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 个段 | |||
| prefix | length | stored data | real value/state |
| 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