Розширюваний метод хешування

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

Метод расширяемого хешування (Extendable hashing) [Г28] представляє собою витончений варіант основного методу хешування, дозволяє усунути описані вище проблеми3 Насправді, розширюване хешування гарантує, що кількість операцій доступу до диску, необхідних для пошуку певного запису, ніколи не перевищує двох і зазвичай зводиться тільки до однієї операції, незалежно від того, якого розміру досягає сам файл (Тому даний метод гарантує також, що ніколи не виникне потреба в реорганізації файлу)

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

Нижче наведено короткий опис розглянутої схеми хешування

1 Припустимо, що основною функцією хешування є h, а значення первинного ключа неко торою конкретної записи г одно к Хешування значення до (тобто обчислення виразу

h (к)) призводить до отримання значення з, званого псевдоключа (Pseudokey) записи к псевдоключа НЕ інтерпретуються безпосередньо як адреси, а замість цього застосовуються для непрямого пошуку адрес зберігання, як описано нижче

2 Файл має повязаний з ним каталог, який також зберігається на диску Каталог складається з за головка, що містить значення d (скорочення від depth – глибина каталогу), поряд з 2d указу телямі Покажчики вказують на сторінки з даними, які містять фактичні записи (на кожній сторінці є багато записів) Таким чином, каталог з глибиною d дозволяє управляти файлом з максимальним розміром, складовим 2d окремих сторінок з даними

3 Якщо провідні d бітів псевдоключа розглядаються як подвійне ціле число без знака Ь, то i-й покажчик в каталозі (1 для якої b дорівнює 0 . 01, і тд (Звичайно всі ці 2d покажчика не є різними це означає, що кількість різних сторінок зданими, як правило, менше ніж 2d, як поки зано на рис Г 15) Тому, щоб знайти запис, яка має значення первинного ключа до, необ ходимо хешірованного до для визначення псевдоключа s і взяти перші d бітів цього псевдоклю ча якщо ці біти мають числове значення il, здійснюється перехід до i-му вказівником в ка талоге (перша операція доступу до диску) і перехід з цього вказівником до сторінки, яка містить необхідну запис (друга операція доступу до диску)

3 В [Г28] застосовується англомовне написання терміна extendable (Розширюваний) з буквою i, тобто

&quotextendible&quot.

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

4 Кожна сторінка з даними має також заголовок, який вказує локальну глибину р цієї сторінки (р

Рис Г 15 Приклад застосування способу расширяемого хешування

5 Тепер припустимо, що сторінка з даними 000 заповнена і потрібно вставити новий запис, що має псевдоключ, який починається з 000 (або з 001) У цей момент зазначена сторінка розділяється на дві це означає, що з пулу вільних сторінок береться нова, порожня сторінка, а всі записи 001 вилучаються зі старої сторінки і переносяться в нову Покажчик 001 в

каталозі коригується таким чином, щоб він вказував на нову сторінку (покажчик 000 все ще вказує на стару сторінку) Локальна глибина р для кожної з цих двох сторінок тепер буде дорівнює 3, а не 2

6 Тепер припустимо, що сторінка з даними, відповідна початковій рядку бітів 000, знову заповнюється і повинна бути знову розділена Існуючий тека не дозволяє забезпечити такий поділ, оскільки локальна глибина розділяється сторінки вже дорівнює глибині каталогу Тому розмір каталогу подвоюється це означає, що значення d збільшується на одиницю і кожен покажчик замінюється парою суміжних, ідентичних покажчиків Тепер зявляється можливість розділити сторінку з даними записи 0000 залишаються на старій сторінці, а записи 0001 переміщаються на нову сторінку перший покажчик в каталозі залишається незмінним (тобто як і раніше вказує на стару сторінку), а другий покажчик коригується таким чином, щоб він вказував на нову сторінку Слід зазначити, що операція удваивания розміру каталогу вимагає відносно невеликих витрат часу, оскільки вона не повязана з доступом до будь-якої з сторінок з даними

На цьому опис методу расширяемого хешування завершується Крім нього, запропоновано безліч інших доповнень до основного методу хешування див, наприклад, [г29] – [г36]

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


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

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*