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

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

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

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

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

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

• одиниці, якщо запис знаходиться у блоці;

• одиниці плюс кількість записів у відповідному цьому блоку списку області переповнювання (як правило, невелика кількість).

Модифікації запису

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

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

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