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

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

Щоб забезпечити доступ від кореня дерева до наново заведеної сторінки, необхідно відповідним образом модифікувати внутрішню сторінку, що є предком листової сторінки, що раніше існувала, тобто вставити в неї відповідне значення ключа і посилання на нову сторінку. При виконанні цієї дії може знов статися переповнення тепер вже внутрішньої сторінки, і вона буде розщепленням на дві. У результаті зажадається вставити значення ключа і посилання на нову сторінку у внутрішню сторінки-предка вище по ієрархії і т.д.

Граничним випадком є переповнення кореневої сторінки В-дерева. У цьому випадку вона також розщеплюється на дві, і заводиться нова коренева сторінка дерева, тобто його глибина збільшується на одиницю.

При видаленні запису виконуються наступні дії:

Пошук запису по ключу. Якщо запис не знайдений, то значить видаляти нічого не треба.

Реальне видалення запису в буфері, в який прочитана відповідна листова сторінка.

Якщо після виконання цієї підоперації розмір зайнятої в буфері області виявляється таким, що його сума з розміром зайнятої області в листових сторінках, що є лівим або правим братом даної сторінки, більше, чим розмір сторінки, операція завершується.

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

Щоб усунути можливість доступу від кореня до звільненої сторінки, треба видалити відповідне значення ключа і посилання на звільнену сторінку з внутрішньої сторінки - її предка. При цьому може виникнути потреба в злитті цієї сторінки з її лівим або правими братами і т.д.

Граничним випадком є повне спустошення кореневої сторінки дерева, яке можливе після злиття останніх двох нащадків кореня. У цьому випадку коренева сторінка звільняється, а глибина дерева меншає на одиницю.

Як видно, при виконанні операцій вставки і видалення властивість збалансованості В-дерева зберігається, а зовнішня пам'ять витрачається досить економно.

Проблемою є те, що при виконанні операцій модифікації дуже часто можуть виникати розщеплення і злиття. Щоб добитися ефективного використання зовнішньої пам'яті з мінімізацією числа розщеплень і злиття, застосовуються більш складні прийоми, в тому числі:

попереджуючі розщеплення, тобто розщеплення сторінки не при її переповненні, а трохи раніше, коли міра заповненості сторінки досягає деякого рівня;

переливання, тобто підтримка рівномірного заповнення сусідніх сторінок;

злиття 3-в-2, тобто породження двох листових сторінок на основі вмісту трьох сусідніх.

Потрібно помітити, що при організації мультидоступу до В-дерев, характерного при їх використанні в СУБД, доводиться вирішувати ряд нетривіальних проблем. Звичайно, грубі рішення очевидні, наприклад монопольне захоплення В-дерева на все виконання операції модифікації. Але існують і більш тонкі рішення, розгляд яких виходить за межі нашого курсу.

І останнє зауваження відносно В-дерев. У літературі вигляд розглянутих нами дерев прийнято називати В* або В+-деревами.

9.2.2. Хешування

Альтернативним і все більш популярним підходом до організації індексів є використання техніки хешування. Це дуже обширна тема, яка заслуговує окремого розгляду. Ми обмежимося лише декількома зауваженнями. Загальною ідеєю методів хешування є застосування до значення ключа деякої функції згортки (хеш-функції), що виробляє значення меншого розміру. Згортка значення ключа потім використовується для доступу до запису.

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

У разі баз даних такі дії є абсолютно неприйнятними. Тому звичайно вводять проміжні таблиці-довідники, що містять значення ключів і адреси записів, а самі записи зберігаються окремо. Тоді при переповненні довідника потрібна тільки його переробка, що викликає менше накладних витрат.

Щоб уникнути потреби в повної переробки довідників, при їх організації часто використовують техніку В-дерев з розщепленнями і злиттям. Хеш-функція при цьому міняється динамічно, в залежності від глибини В-дерева. Шляхом додаткового технічного хитрування вдається добитися збереження порядку записів у відповідності зі значеннями ключа. Загалом методи В-дерев і хешування все більш зближуються.

9.3. Журнальна інформація

Структура журналу звичайно є суто приватною справою конкретної реалізації. Ми відмітимо тільки самі загальні властивості.

Журнал звичайно являє собою чисто послідовний файл із записами змінного розміру, які можна переглядати в прямому або зворотному порядку. Обміни виробляються стандартними порціями (сторінками)