Удосконаленні збалансовані древовидні індекси (Збалансоване дерево)

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

Рис. 1 Збалансоване дерево

Глибиною дерева називається максимальна кількість рівнів поміж коренем та листом. Глибина дерева може бути різною для різних шляхів доступу до листів. Якщо ж вона є однаковою для всіх листів, то дерево називається збалансованим, або В-деревом (В-Тгее).

Ступенем (degree) (або порядком (order)) дерева називається максимально припустима кількість дочірних вузлів для кожного батьківського вузла. Великі ступені звичайно використовуються для створення більш широких та меньш глибоких дерев. Оскільки час доступу в древовидній структурі залежить від глибини, а не від ширини, звичайно прийнято використовувати больш «розгалужені» та меньш глибокі дерева.

Бінарним деревом (binary tree) називається дерево порядку 2, в якому кожен вузел має не більш ніж два дочірних вузла.

Удосконалені збалансовані древовидні індекси визначаються за наступними правилами.

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

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

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

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

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

• Листи дерев пов’язані в порядку збільшення значень ключа.