Багаторівневі індекси

Вторинні індекси

Лекція № 30

Тема «Внутрішня організація реляційних СКБД. Індекси в БД»

Вторинний індекс також є підпорядкованим файлом, аналогичним первинному індексу. Однак пов'язаний з первинним індексом файл даних завжди відсортований за ключом цього індексу, тоді як файл даних, пов'язаний зі вторинним індексом, не обов’язково повинен бути відсортований за ключем індексації. Окрім того, ключ вторинного індексу може містити значення, що повторюються, що не припускається для значень ключа первинного індекса. Для роботи зі значеннями ключа вторинного індексу, які повторюються, звичайно використовуються перелічені нижче методи.

Створення плотного вторинного індексу, який відповідає всім записам файлу даних, але при цьому в ньому припускається наявність дублікатів.

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

Створення вторинного індексу зі значеннями для всіх унікальних значень ключа. Але при цьому вказівники блоків вказують не на файл даних, а на сегмент, який містить вказівники на відповідні записи файлу даних.

Вторинні індекси підвищують продуктивність обробки запитів, в яких для пошуку використовуються атрибути, відмінні від атрибуту первинного ключа. Однак, таке підвищення продуктивності запитів потребує додаткової обробки, яка пов’язана з супроводженням індексів при оновлюванні інформації в БД. Ця задача вирішується на етапі фізичного проектування бази даних.

При збільшенні розміру індексного файлу та розширенні його вмісту на більшу кількість сторінок, час пошуку потрібного індексу також значно збільшується. Звернувшись до багаторівневого індексу, можна спробувати вирішити цю проблему шляхом скорочення діапазону пошуку. Ця операція виконується над індексом аналогічно тому, як це робиться у випадку файлів іншого типу, тобто завдяки розщіплення індексу на декілька субіндексів меньших за розміром та створення індексу для цих субіндексів. На кожній сторінці файлу даних можуть зберігатися два записи. Кожен індексний запис містить значення ключа доступу та адресу сторінки. Значення ключа доступу, яке зберігається, є найбільшим на адресуємій сторінці.

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-04