Область переполнения

Адрес (номер страницы)	Номер накладной	Название товара	Арти- кул	Коли-чество	Дата поставки	Ссылка на синонимы
500	29	Брюки	750	90	13.12.05
501	96	Сапоги	220	120	13.12.05
502	40	Костюм	300	35	14.12.05	500
503
504
505

Рис. 6. Пример хеширования с областью переполнения

Стратегия разрешения коллизий с помощью свободного замещения

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

Технології пошуку і видалення записів в обох стратегіях також аналогічні.

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

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

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

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

Незважаючи на зазначені недоліки хешування, даний спосіб організації зберігання і швидкого витягання необхідних даних широко застосовується, в першу чергу в об'єктно-орієнтованих базах даних [12].

Кластеризація

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

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

Таблица 3.7 Сведения о поставках товаров в магазин

Номер накладной	Название товара	Артикул	Количество	Дата поставки	Номер страницы
37	Костюм	500	50	10.12.05	1
60	Костюм	500	35	11.12.05	1
28	Костюм	300	20	12.12.05	2
74	Костюм	400	50	12.12.05	2
54	Сапоги	200	75	10.12.05	5
18	Туфли	100	120	11.12.05	9
80	Туфли	100	100	12.12.05	9

В результаті з безлічі сторінок формуються блоки, які називаються кластерами, в кожному з яких зберігаються записи з однаковими назвами товарів.

Новий запис, що вводиться в базу даних, повинен бути розміщений в конкретному кластері. Цей процес може бути виконаний на вже наявній сторінці (у розглянутому прикладі, якщо товар називається Чоботи, на сторінці з номером 5) або за відсутності на ній вільного місця, на сторінці фізично найбільш близькою (товар Костюм - на сторінці з номером 3).

Для кластерізірованих таблиць можна створити нещільні індекси (див. п. 3.4) з покажчиками на перші записи, що входять в кожен кластер (блок).

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

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