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