ному вузлу дерева відповідає сторінка зовнішньої пам'яті. У B-деревах ключі і відповідні їм значення індексу можуть перебувати як у вузлах, так і в листових блоках. p align="justify"> Опишемо алгоритм пошуку значення в B-дереві по заданому ключу. Припустимо, що відбувається пошук ключа K. В основну пам'ять зчитується коренева сторінка B-дерева. Припустимо, що в цій сторінці міститися ключі k1, k2, ..., km та посилання на сторінки p0, p1, ..., pm. У ній послідовно (або за допомогою якогось іншого методу пошуку в основній пам'яті) шукається ключ K. Якщо він виявляється, пошук завершений. Інакше можливі три ситуації:
. Якщо в ліченої сторінці виявляється пара ключів ki і k (i +1) така, що ki
. Якщо виявляється, що K> km, то пошук продовжується на сторінці pm;
. Якщо виявляється, що K
Для внутрішніх сторінок пошук триває аналогічним чином, поки або не буде знайдений ключ K, або не буде досягнута листова сторінка. Якщо ключ чи не знаходиться і в листовий сторінці, значить ключ K в B-дереві відсутня. p align="justify"> Додавання нового елемента відбувається за наступним алгоритмом. Спочатку, проводиться перевірка на наявність додається ключа в дереві, методом обходу цього дерева. У тому випадку, якщо даний ключ не знайдено, то відбувається перевірка кількості елементів листового блоку, на якому закінчився обхід дерева. Якщо блок містить менше 2 * n елементів, то в нього буде виконана вставка нового елемента, в позицію, не порушує впорядкованість даних у цьому блоці. Інакше, створюється новий листовий блок і в ньому розміщується цей елемент і 2 * n-1 записів з повністю заповненого листового блоку. Ця процедура називається розщепленням. При розщепленні, покажчик на новий листовий блок і його середній ключ поміщаються в батьківський, по відношенню до розщепленим листам, вузол дерева. Якщо батьківський блок також повністю заповнений, він теж буде розщеплений. Цей алгоритм може виконуватися рекурсивно, аж до кореня дерева. p align="justify"> Індекси можуть створюватися не відкрито СУБД, при створенні первинного ключа (PRIMARY KEY), або ж засобами мови SQL. Оператор створення індексу має наступний синтаксис:
[UNIQUE] [CLUSTERED | NONCLUSTERED]
INDEX ім'я_індексу ON ім'я_таблиці (ім'я_стовпця [ASC | DESC] [, ... n])
[WITH [PAD_INDEX]
[[,] FILLFACTOR = фактор_заполненія]
[[,] IGNORE_DUP_KEY]
[[,] DROP_EXISTING]
[[,] STATISTICS_NORECOMPUTE]]
[ON імя_группи_файлов]
Необов'язковий UNIQUE дозволяє зробити створюваний ...
