ЛАНЦЮЖКИ покажчиків В БАЗІ ДАНИХ

Знову припустимо, як і на початку розділу Г4, що важливе значення має запит: Визначити всіх постачальників з міста с. Ще одним збереженим поданням, що дозволяє досить успішно виконувати цей запит (можливо, навіть краще в порівнянні з індексом, хоча і не завжди), є подання, в якому використовуються ланцюжки покажчиків Таке уявлення показано на рис Г 16 Як показано на цьому малюнку, в ньому використовуються два файли – файл постачальників і файл міст, багато в чому аналогічно тому, як і в індексному поданні, показаному на рис Г9 (але на цей раз обидва файли, швидше за все, повинні знаходитися в одному і тому ж наборі сторінок з причин, які будуть описані в розділі Г7) Але в уяві на основі ланцюжка покажчиків, показаному на рис Г 16, файл міст – це не індекс, а структура, яку іноді називають батьківським файлом Відповідно до цього, файл постачальників іменується дочірнім файлом і вся ця структура може розглядатися як приклад батьківсько-дочірньої організації даних

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

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

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

■ Хоча ця структура може виявитися придатною для запиту: Визначити постачальників з зазначеного міста, вона не сприяє (фактично може навіть перешкодити) успішному виконанню протилежної запиту: Визначити назву міста, де знаходиться зазначений ний постачальник (Де постачальник вказано за допомогою номера постачальника) Для виконання останнього запиту, мабуть, буде потрібно хешування або індексування файлу

постачальників слід зазначити, що тепер батьківсько-дочірня структура, заснована на номерах постачальників, не матиме будь-якого сенсу (поясніть, чому)

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

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

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

■&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Примітка До речі, для створення нового хешірованного файлу також зазвичай потрібно ре організація існуючого файлу, якщо тільки вживаний метод хешування не є непрямим [Г24]

Можливі деякі варіанти цієї основної батьківсько-дочірньої структури, наприклад, як описано нижче

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

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

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

Нарешті, безумовно, існує можливість не тільки визначити будь-яку кількість індексів на будь-якому конкретному файлі, але і забезпечити проходження через такий файл будь-якої кількості ланцюжків покажчиків (Можливий також такий варіант, хоча і не дуже широко поширений, коли застосовуються і індекси, і ланцюжки покажчиків) На рис Г 17 показано виставу для файлу постачальників, в якому використовуються дві різні ланцюжки покажчиків, і тому визначено дві різні батьківсько-дочірні структури, в одній з яких як батьківського використовується файл міст (як на рис Г 16), а в іншій – файл статусу Файл постачальників є дочірнім для обох цих структур

                                                                                       0Z                                         4JW    IS

Джерело: Дейт К Дж, Введення в системи баз даних, 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>

*

*