Главная | Обратная связь

Пошук і читання запису із заданим значенням ключа

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

Вважаємо, що всі блоки розташовані у ВП. Тоді кількість звернень до ВП при пошуці інформації дорівнюватиме кількості рівнів дерева. Кількість рівнів дерева дорівнює мінімальному значенню l, при якому виконується умова k^l ³ N (N – кількість логічних записів).

Модифікація (коректування) запису

Після пошуку і читання запису змінюються відкоректовані поля. Якщо коректується не ключ запису, то змінений запис заноситься на своє місце. Якщо змінено значення ключа, то старий запис видаляється (у відповідному блоці з'являється "порожній" запис), а змінений запис заноситься так само, як і новий запис що додається.

Видалення запису

Після пошуку знайдений запис видаляється (у відповідний блок на місце цього запису заноситься "порожній" запис).

Додавання запису

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

Якщо у відповідному блоці нижчого рівня немає порожнього місця, блок ділиться на два блоки. У перший з них заноситься [k/2] записів, у другий заносяться останні. Значенням ключа кожного з указаних блоків буде, як і описано раніше, мінімальне значення ключів у записах, що входять у блок. Запис, що додається, заноситься в той блок, значення ключа якого менше значення ключа запису, що додається. Поява нового блоку з новим значенням ключа обумовлює необхідність формування відповідного нового запису в індексі на попередньому рівні. Цей запис містить нове значення ключа нового блоку і вказівник на його місце розташування. Процедура додавання такого запису аналогічна описаній вище. Знаходиться блок попереднього рівня, куди має бути поміщений цей запис. Якщо у блоці є порожнє місце, запис додається в блок, якщо блок повний, він ділиться на два блоки, запис заноситься в один з блоків, формується запис індексу попереднього рівня і т. д.

Можливий варіант, коли доведеться ділити блок самого верхнього рівня і формувати ще один рівень дерева.

Розглянемо для прикладу, додавання запису з ключем 10, зображеного на мал. 9.7

1. Порівняння на першому рівні.

2<10<43

Рух по лівій гілці.

2. Порівняння на другому рівні.

2<10<15

Рух по лівій гілці.

3. Порівняння на третьому рівні.

2<8<10

Рух по правій гілці.

Шуканий блок

4. Блок заповнений.

Він ділиться на 2 блоки

Порівняння 8<10<12.

Запис з ключем 10 заноситься у блок 1

На нижчому рівні з'явився новий запис із значенням ключа 12. Необхідне додавання новому запису з ключем 12 і покажчиком на запис нижчого рівня до індексу попереднього рівня.

5. Запис із ключем 12 рівня 3 повинен додаватися у блок . Блок заповнений, він ділиться на два блоки

Порівняння 8<12.

Запис додається в другий блок

6. На рівні 3 з'явився блок з новим ключем 8. Необхідне додавання новому запису з ключем 8 і покажчиком на відповідний блок рівня 3 на рівні 2.

7. Запис з ключем 8 рівня 2 повинен додатися у блок . Блок заповнений, він ділиться на два блоки.

2<8<15

Запис додається у блок1 .

8. На рівні 2 з'явився блок з новим ключем 15, необхідне додавання нового запису з ключем 15 і покажчиком на відповідний блок рівня 2 на рівні 1.

9. Запис з ключем 15 рівня 1 повинен додаватися у блок . Блок заповнений, він ділиться на два блоки.

2<15<43

Запис з ключем 15 додається в перший блок

10. Необхідно сформувати ще один рівень дерева .

Отримана структура матиме вигляд, зображена на мал. 9.8.

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

Структура зберігання у вигляді B-дерева дозволяє ефективно проводити операції пошуку, читання, видалення, модифікації з оцінкою кількості звернень до зовнішньої пам'яті кількістю рівнів дерева l (l » log_kN), що істотно менше кількості звернень при переборі [N/k].

Процедура додавання запису теж досить ефективна. Відповідна структура зберігання, зокрема, використовується у вітчизняній СУБД НІКА (раніше використовувалася в системі ІНЕС) і на реальних задачах показала високу ефективність.

38. Структура зберігання даних у зовнішній пам’яті комп’ютера. Розміщення записів з використанням хешування

Як у будь-якому іншому способі організації структур зберігання, логічні записи групуються у фізичні записи (блоки) по k штук. Проте на відміну від всіх інших способів організації структур зберігання тут вибраний особливий спосіб групування. Певним чином вибирається так звана хеш-функція f. Аргументом цієї функції є значення x первинного ключа логічного запису. Тоді f(x) вказує адресу розташування блоку, в якому повинен знаходитися логічний запис із значенням ключа x.

Функція f повинна, по можливості, рівномірно розподіляти значення x по фізичних блоках. Обговоренню можливих хеш‑функцій присвячено досить багато літератури, тому в лекціях ми не будемо торкатися цього питання. Можна лише додати, що інколи, виходячи із специфіки множини значень x первинного ключа, можна побудувати функцію f, що задовольняє всім необхідним умовам. Таким чином, логічний запис таблиці із значенням x первинного ключа розміщується в блоці зовнішньої пам'яті за адресою f(x). У цьому блоці може знаходитися не більш k записів. Може виявитися, що вибрана функція відображує в одну адресу пам'яті (один блок) більший за k записів. Виникає так звана колізія. Можливим способом розв’язання колізій є використання додаткової області переповнювання таким чином. Якщо наступний запис розподіляється за допомогою функції хешування в блок, а він повністю заповнений, то в області переповнювання формується список записів, відповідних цьому блоку, з включенням в нього вказаного запису, а в сам блок заноситься покажчик – адреса зв'язку на перший запис цього списку. Можливі і інші способи розв’язання колізій.

Розглянемо реалізацію основних операцій і дамо оцінку кількості звернень до ВП при їх виконанні.