Firebird структура индекса за Firebird 2.0 (ODS 11 и новије)
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; // идентификатор отношения для согласованности
USHORT btr\_length; // длина данных в блоке
UCHAR btr\_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; // данные можно читать отсюда
};
Новый флаг для новой структуры индекса:
Новые флаги добавлены в header->pag_flags.
Флаг btr_large_keys (32) предназначен для хранения сжатой длины/префикса и номера записи. Это также означает, что длина и префикс могут быть до 1/4 размера страницы (1024 для размера страницы 4096) и легко расширяемы в будущем без повторного изменения структуры на диске. Также номер записи можно легко расширить, например, до 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 байтах
| заголовок (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 также хранятся на узле перехода.
Наш следующий узел перехода указывает на узел, представляющий FUEL, также с префиксом 2. Таким образом, узел перехода 2 должен содержать FU, но наш предыдущий узел уже содержал F, поэтому из-за сжатия префиксов этот символ игнорируется и сохраняется только U.
Состояние NULL:
Данные, которые необходимо сохранить, определяются в процедуре compress() в btr.cpp.
Для индексов 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