писів може бути знайдена за допомогою послідовної обробки елементів, що залишилися кінцевого вузла. Потім, при необхідності, відбувається перехід вправо по зв'язаному списку листя. Алгоритм продовжується до тих пір, поки не знайдено запис, що має значення більше ніж у останнього елемента з діапазону і поки зв'язний список не закінчилася.
Обчислювальна складність даної операції в гіршому випадку T (xy) Find=O ((logb/2n) + m), де b - порядок дерева або коефіцієнт розгалуження; n - кількість елементів у дереві; m - довжина пов'язаного списку.
Доказ. Пошук першого елемента з діапазону в дереві має трудомісткість O (logb/2n). Щоб знайти всі елементи діапазону, необхідно проходити по кінцевим вузлам доти, поки чергова запис задовольняє умовам діапазону або поки записи в дереві не закінчаться.
Приклад пошуку по діапазону від 9 до 14 (Рис.7):
(Рис.7)
3. B +-дерева в системах баз даних
Більшість систем баз даних використовують індекси, побудовані на тій чи іншій формі B +-дерева через його численних переваг, зокрема його підтримку запитів по діапазону.
Висновок
В результаті виконання роботи досліджено структуру B +-дерева. Вивчено її основні операції, доведена їх обчислювальна складність.
Список використаних джерел
<# «justify"> Додаток
(Рис.8)
На малюнку (Рис.8) відбувається послідовна вставка елементів в дерево (in - вставка елемента з ключем рівним n; t - операція виведення вмісту B + дерева на екран; знак «|» розділяє вузли між собою ).
(Рис.9)
На малюнку (Рис.9) наведено приклад вставки і видалення елементів (dn - видалення з дерева елемента з ключем рівним n).
(Рис.10)
На малюнку (Рис.10) наведено приклад пошуку записів з діапазону від 11 до 20.
