Оскільки відносини можуть містити невизначені значення, необхідна відповідна підтримка на рівні зберігання. Звичайно це досягається шляхом зберігання відповідної шкали при кожному кортежі, який в принципі може містити невизначені значення.

Проблема розподілу пам'яті в сторінках даних пов'язана з проблемами синхронізації і журналізації і не завжди тривіальна. Наприклад, якщо в ході виконання транзакції деяка сторінка даних спустошується, то її не можна перевести в статус вільних сторінок до кінця транзакції, оскільки при відкаті транзакції видалені при прямому виконанні транзакції і відновлені при її відкаті кортежі повинні отримати ті ж самі ідентифікатори.

Поширеним способом підвищення ефективності СУБД є кластеризація відношення по значеннях одного або декількох стовпців. Корисним для оптимізації з'єднань є спільна кластеризація декількох відносин.

З метою використання можливостей розпаралелювання обмінів із зовнішньою пам'яттю іноді застосовують схему декластеризованого зберігання відносин: кортежі із загальним значенням стовпця декластеризації розміщують на різних дискових пристроях, обміни з якими можна виконувати в паралель.

Що ж до зберігання відношення по стовпцях, то основна ідея складається в спільному зберіганні всіх значень одного (або декількох) стовпців. Для кожного кортежу відношення зберігається кортеж тієї ж міри, що складається з посилань на місця розташування відповідних значень стовпців. У останній лекції ми будемо розглядати особливості організації розподіленій реляційній СУБД. Одним з прийомів є так зване вертикальне розділення відносин, коли в різних вузлах мережі зберігаються різні проекції даного відношення. Зберігання відношення по стовпцях в деякому розумінні є граничним випадком вертикального розділення відносин.

9.2. Індекси

Як би не були організовані індекси в конкретній СУБД, їх основне призначення складається в забезпеченні ефективного прямого доступу до кортежу відношення по ключу. Звичайно індекс визначається для одного відношення, і ключем є значення атрибута (можливо, складового). Якщо ключем індексу є можливий ключ відношення, то індекс повинен володіти властивістю унікальності, тобто не містити дублікатів ключа. На практиці ситуація виглядає звичайно протилежно: при оголошенні первинного ключа відношення автоматично заводиться унікальний індекс, а єдиним способом оголошення можливого ключа, відмінного від первинного, є явне створення унікального індексу. Це пов'язано з тим, що для перевірки збереження властивості унікальності можливого ключа так чи інакше потрібна індексна підтримка.

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

Нарешті, одним з способів оптимізації виконання еквіз'єднання відносин (найбільш поширена з числа операцій, що дорого коштують) є організація так званих мультиіндексів для декількох відносин, що володіють загальними атрибутами. Будь-хто з цих атрибутів (або їх набір) може виступати як ключ мультиіндекса. Значенню ключа зіставляється набір кортежів всіх пов'язаних мультиіндексом відносин, значення виділених атрибутів яких співпадають зі значенням ключа.

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

9.2.1. B-дерева

Видимо, найбільш популярним підходом до організації індексів в базах даних є використання техніки В-дерев. З точки зору зовнішнього логічного уявлення В-дерево - це збалансоване сильно гіллясте дерево у зовнішній пам'яті. Збалансованість означає, що довжина шляху від кореня дерева до будь-якого його листа одна і та ж. Гіллястість дерева - це властивість кожного вузла дерева посилатися але велике число вузлів-нащадків. З точки зору фізичної організації В-дерево представляється як мультиспискова структура сторінок зовнішньої пам'яті, тобто кожному вузлу дерева відповідає блок зовнішньої пам'яті (сторінка). Внутрішні і листові сторінки звичайно мають різну структуру.

У типовому випадку структура внутрішньої сторінки виглядає таким чином:

При цьому витримуються наступні властивості:

ключ(1) <= ключ(2) <=. .. <= ключ(n);

в сторінці дерева Nm знаходяться ключі k зі значеннями ключ(m) <= k <= ключ(m+1).

Листова сторінка звичайно має наступну структуру:

Листова сторінка володіє наступними властивостями:

ключ(1) < ключ(2) <. .. < ключ(t);

сп(r) - впорядкований список ідентифікаторів кортежів (tid), що включають значення ключ(r);

листові сторінки пов'язані одно - або двонаправленим списком.

Пошук в В-дереві - це проходження від кореня до листа відповідно до заданого значення ключа. Помітимо, що оскільки дерева сильно гіллясті і збалансовані, то для виконання пошуку по будь-якому значенню ключа буде потрібне одне і те ж (і звичайне невелике) число обмінів із зовнішньою пам'яттю. Більш точно, в збалансованому дереві, де довжини всіх шляхів від кореня до листа одні і ті ж, якщо у внутрішній сторінці вміщується n ключів, то при зберіганні m записів потрібне дерево глибиною logn(m), де logn обчислює логарифм по основі n. Якщо n досить велике (звичайний випадок), то глибина дерева невелика, і проводиться швидкий пошук.

Основною "родзинкою" В-дерев є автоматична підтримка властивості збалансованості. Розглянемо, як це робиться при виконанні операцій занесення і видалення записів.

При занесення нового запису виконується:

Пошук листової сторінки. Фактично, проводиться звичайний пошук по ключу. Якщо в В-дереві не міститься ключ із заданим значенням, то буде отриманий номер сторінки, в якій йому належить міститися, і відповідні координати всередині сторінки.

Приміщення запису на місце. Природно, що вся робота виготовляється в буферах оперативної пам'яті. Листова сторінка, в яку потрібно занести запис, прочитується в буфер,