Структура индексов 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