ЗМІСТ
ВСТУП
. Збалансовані багатоходові дерева пошуку
.1 В +-дерево, структура
.2 Характеристика
.3 Твердження про висоті
. Основні операції B + дерева
.1 Пошук запису
.2 Вставка записи
.3 Видалення запису
.4 Пошук по діапазону
. B +-дерева в системах баз даних
ВИСНОВОК
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
ДОДАТОК
ВСТУП
Усі записи з таблиці в СУБД зберігаються на дисках, щоб гарантувати їх незмінність у випадку збоїв. Записи в таблиці організовані в файлах, які управляються СУБД, а не ОС. Всякий раз, коли запит відправляється в СУБД, він обробляється і записи з таблиці, що задовольняють запиту, повертаються СУБД. Те, яким чином обробляється запит, залежить від конкретної структури зберігання записів у файлі. Якщо записи організовані в довільному порядку то таку структуру зберігання називають купи.
Для вилучення записів з файлу організованого купою, все, що СУБД може зробити, це послідовно просканувати дискові сторінки, де зберігаються записи. Зазвичай сторінки, які складають файл, є суміжними на диску.
Якщо, з іншого боку, ці записи зберігаються у файлі в певному порядку, то бінарний пошук може бути використаний для вилучення записів доти, поки критерії запиту збігаються з атрибутами, які використовуються для підтримки порядку сортування в файлі. Наприклад, якщо файл, який зберігає записи для таблиці Students, впорядкований по прізвища та імені (в такому порядку), то бінарний пошук може бути використаний для обробки запитів, щоб шукати студентів тільки за прізвищем або за їх повного імені. Запит, який шукає студентів за їх датою народження, повинен бути оброблений з використанням послідовного сканування відсортованого файлу, аналогічно, якщо запит шукає студентів за їх імені.
Індекс-таблиці являє собою структуру даних і пов'язані з нею алгоритми, що забезпечують механізм, за допомогою якого записи таблиці можна шукати більш ефективно, ніж при будь-якому послідовному сканування або бінарному пошуку. Найбільш поширені структури індексу, використовувані в СУБД, є B +-дерева і хеш-таблиці.
. Збалансовані багатоходові дерева пошуку
Час, потрібний для добування інформації з зовнішньої пам'яті (наприклад з диска), в тисячі разів більше, ніж для вилучення тієї ж інформації, але з оперативної пам'яті. Метою зовнішнього пошуку є зведення до мінімуму кількості звернень до диску, так як доступ до нього займає більше часу, ніж обчислення. Це відрізняється від мети мінімізації кількості обчислень (тобто порівнянь) в пошуку даних, які знаходяться в більш швидкою, оперативної пам'яті. З цієї причини, при типовому доступі до запису із зовнішньої пам'яті, відбувається читання цілої сторінки або блоку даних відразу. +-Дерево є одним з сім'ї багатоходових дерев пошуку (інші: B-дерево, 2-3-4 Дерево, В *-дерева ). Ці дерева були вперше запропоновані Рудольфом Байєром (Rudolf Bayer) і Едом Маккрейтом (Ed McCreight) в 1972 році і всього за кілька років змінили майже вс...
