Вдосконалені деревовидні індекси

У багатьох СКБД для зберігання даних або індексів використовується структура даних, яка називається деревом. Дерево складається з ієрархії вузлів (node), в якій кожен вузол, за винятком кореня (root), має батьківський (parent) вузол, а також один, декілька або жодного дочірнього (child) вузла. Корінь не має батьківського вузла. Вузол, який не має дочірніх вузлів, називається лтстом (leaf).

Глибиною дерева називається максимальна кількість рівнів між коренем і листом. Глибина дерева може бути різною для різних шляхів доступу до листів. Якщо ж вона однакова для всіх листів, то дерево називається збалансованим, або В-деревом. Мірою (degree) (або порядком) дерева називається максимально допустима кількість дочірніх вузлів для кожного батьківського вузла. Великі міри зазвичай використовуються для створення ширших і менш глибших дерев. Оскільки час доступу в деревовидній структурі залежить від глибини, а не від ширини, зазвичай прийнято використовувати більш " розгалужені" і менш глибокі дерева. Бінарним деревом (binary tree) називається дерево порядку 2, в якому кожен вузол має не більше двох дочірніх вузлів.

Вдосконалені збалансовані деревовидні індекси B+-Tree визначаються за наступними правилами.

‒ Якщо корінь не є листом, то він повинен мати, принаймні, два дочірні вузли.

‒ У дереві порядку n кожен вузол (за винятком кореня і листів) повинен мати від n/2 до n покажчиків і дочірніх вузлів. Якщо число n/2 не є цілим, то воно округляється до найближчого більшого цілого.

‒ У дереві порядку n кількість значень ключа в листі повинна знаходитися в межах від (n-1)/2 до (n-1). Якщо число (n-1)/2 не є цілим, то воно округляється до найближчого більшого цілого.

‒ Кількість значень ключа в нелистовому вузлі на одиницю менше кількості покажчиків.

‒ Дерево завжди має бути збалансованим, тобто всі шляхи від кореня до кожного листа повинні мати однакову глибину.

‒ Листи дерева зв'язані в порядку зростання значень ключа.

На практиці кожен вузол в дереві є сторінкою, тому в ньому може зберігатися більше трьох покажчиків і двох значень ключа. Якщо передбачити, що сторінка має розмір 4096 байтів, кожен покажчик – довжину 4 байти, розмір поля staffNo також дорівнює 4 байтам і кожна сторінка містить 4-байтовий покажчик на наступний вузол того ж рівня, то на одній сторінці може зберігатися (4096-4) / (4 + 4) =511 індексних записів. Таким чином, порядок даного В+-дерева дорівнює 512. Корінь дерева може містити до 511 записів і мати до 512 дочірніх вузлів. Кожен дочірній вузол також може містити до 511 записів, що в цілому дає структуру з 261632 записів. У свою чергу, кожен дочірній вузол також може мати до 512 дочірніх вузлів, що в сумі дає 262144 дочірніх вузли на рівні 2 цього дерева. Кожен із цих вузлів також може містити до 511 записів, що дає дворівневу структуру з 133955584 записів. Теоретичний максимум для кількості індексних записів в дворівневому дереві визначається таким чином.

Таким чином, описана вище структура дозволяє здійснювати довільний доступ до окремого запису файлу staff, що містить до 134217727 записів, з виконанням лише чотирьох операцій доступу до диска (насправді корінь зазвичай знаходиться в оперативній пам'яті, тому кількість операцій доступу на одиницю менша). Але на практиці кількість записів на одній сторінці зазвичай менше, оскільки не всі сторінки бувають повністю заповненими.

У B+-дереві для доступу до будь-якого запису даних потрібний приблизно однаковий час, оскільки при пошуку є видимою однакова кількість вузлів, завдяки тому, що всі листи дерева мають однакову глибину. Оскільки цей індекс є щільним, кожен запис адресується індексом, тому сортувати файл даних не потрібно, тобто він може зберігатися у вигляді невпорядкованого файлу. Проте подібну збалансованість дерева досить складно підтримувати в ході постійного оновлення вмісту дерева.