 |
|
Пошук запису із заданим значенням ключа
Відмітимо, що впорядкування записів за значеннями ключа не дає тут прискорення процедури пошуку. Це пов'язано з тим, що після ряду додавань нових записів і видалення якихось існуючих записів фізична і логічна послідовність записів у списку істотно відрізнятиметься. При цьому буде неможливо за номером запису визначити його адресу і звертатися до запису, відповідної середини таблиці, для реалізації дихотомічного методу пошуку. Тому пошук можна вести лише за допомогою перебору. В ОП зчитується перший запис списку, розблоковується, значення ключових полів логічних записів цього фізичного запису порівнюються із заданим значенням. Якщо значення співпали, потрібний запис знайдений, якщо не збіглися, із записів вибирається адреса наступного запису списку, читається цей запис. Далі процедура повторюється. Середня кількість звернень до ВП буде рівною, як і в 9.4.1, (1+[N/k]) /2.
Читання запису
Після завершення попередньої операції запис зчитується в ОП. Оцінка кількості звернень до ВП таж.
Коректування запису
Зчитаний запис коректується і заноситься у ВП на своє місце (за своєю адресою). Кількість звернень до ВП на одиницю є більшою, ніж при читанні.
Видалення запису
Відмітимо, що ми говоримо про операції над логічними записами. Операція видалення логічного запису аналогічна операції коректування. Службове поле відповідного логічного запису позначається як "видалений запис". Сформований фізичний запис заноситься у ВП. Кількість звернень до ВП рівна ТР+1.
Додавання запису
Для визначеності вважатимемо, що заданий ключ логічного запису, після якого має бути доданий новий запис. Здійснюється операція пошуку і читання фізичного запису, в якому розташований запис з ключем РК. Якщо в цьому блоці є логічний запис, помічений як видалений запис, що додається, заноситься на його місце. Блок записується у ВП. Кількість звернень до ВП рівна ТР+1. Якщо у цьому блоці немає логічних записів, помічених як видалені, необхідно додавати новий фізичний запис, що вибраний із списку вільних елементів. З цією метою адреса зв'язку знайденого раніше фізичного запису замінюється на адресу початку списку вільних елементів.
Читається перший фізичний запис списку вільних елементів. Адреса зв'язку цього запису замінює адресу початку порожнього списку. В ОП формується новий фізичний запис, який буде доданий, що містить логічний запис. В ролі адреси зв'язку заноситься адреса зв'язку з фізичного запису, що передує тому запису який додається. Кожен з цих записів заноситься у ВП. Кількість звернень до ВП при додаванні запису буде приблизно рівною ТР+3.
Розглянутий метод організації структури зберігання досить ефективно вирішує проблеми додавання і видалення записів, але не уникає перебору при пошуку потрібного запису.
37. Структура зберігання даних у зовнішній пам’яті комп’ютера. Використання індексів. В-дерева
Як уже наголошувалося, впорядкування записів дозволяє використовувати дихотомічний метод пошуку потрібного запису і тим самим істотно скоротити одну з основних складових часу пошуку – кількість звернень до ВП. Проте при цьому виникають проблеми з додаванням записів, пов'язані з необхідністю перезапису частини фізичних записів (зсуву).
Для того, щоб використовувати дихотомічний пошук і не переміщувати фізичні записи при додаванні нових записів, використовується так зване логічне впорядкування фізичних записів (індексування). Основна структура зберігання містить записи вихідної таблиці і представлена у вигляді неврегульованої послідовності фізичних записів (див. п. 5.4.1). Для можливої реалізації дихотомічного пошуку по певному ключу створюється додаткова структура зберігання (так званий індекс). Кількість записів в індексі дорівнює кількості записів вихідної таблиці (кількості фізичних записів в основній структурі зберігання). Кожен запис індексу має два поля: ключове поле запису основної структури і покажчик – адреса запису основної структури з відповідним значенням ключа.
Записи індексу (індексного файлу) впорядковані за значенням ключа. Адреси зв'язку цих записів визначають логічне впорядкування записів основної структури зберігання. Приклад відповідної структури зберігання наводиться (при припущенні k=1) на мал. 9.6.
Дану структуру зберігання називають ще інвертованим списком. Сенс цього терміну полягає в наступному. Можна було б упорядкувати записи основної структури зберігання, не переставляючи їх, а об'єднавши у відповідний впорядкований список. У нашому випадку адреси зв'язку як би віддаляються із списку і включаються до складу файлу-індексу (інвертуються). Тому отримана структура інтерпретується як інвертований список.
Структура В-дерева (збалансоване дерево) є наслідком подальшого розширення концепції використання індексів (будується індекс над індексом) і є багаторівневими індексами.
В-дерево будується таким чином. Послідовність записів, відповідна записам вихідної таблиці, упорядковується по значеннях первинного ключа. Логічні записи об'єднуються в блоки (по k записів у блоках).
Значенням ключа блоку є мінімальне значення ключа у записах, що входять у блок. Послідовність блоків є останнім рівнем В-дерева. Будується індекс попереднього рівня. Записи цього рівня містять значення ключа блоку наступного рівня і покажчик-адресу зв'язку відповідного блоку; записи цього рівня також об'єднуються у блоки (по k записів). Потім аналогічно будується індекс більш високого рівня і так далі, поки кількість записів індексу на певному рівні буде не більший k.
Розглянемо процедуру роботи з B-деревом на прикладі. Нехай є файл екземплярів логічних записів, ключі яких набувають значень 2, 7, 8, 12, 15, 27, 28, 40, 43, 50. Для визначеності візьмемо k=2 (у блок об'єднуємо по 2 екземпляри записів). Побудоване для цього прикладу В-дерево зображене на мал. 9.7 (для спрощення малюнка на рівні 4 представлені лише ключі логічних записів і не представлені значення інших полів цих записів).
У блоках вказано значення ключа відповідного блоку. Значення k прийнято рівним 2.
За побудовою В-дерева всі вихідні записи знаходяться на одній відстані від верхнього індексу (дерево є збалансованим).
Розглянемо реалізацію основних операцій.