 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Ієрархічна організація файлів (даних)
В-дерева, В*-дерева.
Описана у попередньому розділі структура блоків індексів отримала подальший розвиток у так званих індексних файлах древовидної структури. Традиційно різноманітні варіанти дерев використовувалися в інформатиці в тих випадках, коли було потрібно накопичення даних одночасно з їх сортуванням.
Індексний файл древовидної структури складається з декількох логічно зв¢язаних рівнів. Покажчики посилаються на номери блоків, що знаходяться на один рівень нижче. Саме в зв¢язку з відображенням ієрархії на фізичне збереження даних на диску виявляється вся міць індексних файлів древовидної структури.
Взагалі, відношення ієрархії допускає відміни в глибині різних гілок дерева. Це означає, що шляхи доступу до інформації, пов¢язані з різними гілками, можуть бути різної довжини. Але при реалізації ієрархії за допомогою древовидних індексів це дає вельми нежаданий ефект, тому що кількість звертань до дискових блоків в різних піддеревах ієрархії може бути різним.
Дерево, що має однакове число рівнів у кожному піддереві, називають збалансованим деревом, або скорочено – В-деревом (від англійського balanced tree). Характерною ознакою В-дерева є мінімізація середньої кількості звертань до дискових блоків при пошуку запису даних, що потрібні.
В-дерево, у якого кожний ключ показує на блок даних, що містить потрібний запис, називають В*-деревом. Таким чином, воно представляє собою інтеграцію області покажчиків і області даних та є на сьогодні переважним варіантом цієї форми організації файлів. Таке В*-дерево складається із блоку каталогу на вершині, блоків покажчиків різних рівнів, які посилаються на блоки даних, що знаходяться на нижньому рівні. У підсумку утворюється структура, що подібна піраміді, яка показана на мал.12.
 |
Рівень
покажчиків
(В*-дерево
|
|
 |  |
Рівень даних
Мал. 12. Загальна структура В*-дерева
На перший погляд може показатися, що при традиційному для В*-дерев способі формування блоків покажчиків і даних, що заповнюються лише частково (для резервування вільного місця майбутнім записам), росте потреба у дисковій пам¢яті. Але як показує практика, діло обстоїть зовсім інакше: потреба у вільному місці для збереження даних в таких системах значно нижче, ніж в системах, які не засновані на В*-деревах.
Для роз¢яснення причин такого стану, звернемось до двох факторів:
1. Середній рівень наповненості блоків покажчиків та даних та
2. Звичайні для В*-дерев поля перемінної довжини і, як наслідок, записи перемінної довжини.
Практика показує, що у великих по обсягу глобалів розповсюджених М-застосувань[7] в середньому коефіцієнт наповнення становить біля 80%. Блоки покажчиків можуть заповнюватися ще в меншій степені, але із-за порівно незначної кількості вони не мають великого впливу на загальну статистику, Таким чином, перевитрата дискового простору в В*-деревах складає біля 20%.
Але, навіть ці 20% компенсуються за рахунок використання полів перемінної довжини. Вигоди від цієї переваги залежать від відношення між полями перемінної довжини (такими як імена та прізвища, найменування товарів, ціни, пояснення тощо) та фіксованої довжини (дати, коди, табельні номера тощо). Крім того, впливає кількість та довжини необов¢язкових полів (у яких може бути відсутні значення), але які проте потребують резервування дискового простору при використанні файлів з фіксованою довжиною полів.
У найвищої ступені показником для систем оперативної обробки трансакцій є час читання, запису та корегування окремого запису даних. Припустимо, що деякий блок уміщує 50, а блок даних – 20 елементів. В таблиці показано число дискових операцій, що потрібні для пошуку потрібного блоку, в залежності від числа записів, що зберігаються. В таблиці не враховується одноразове читання блока записів.
Таблиця 2
Кількість фізичних звертань до блоків в залежності від розміру В*-дерева
| Кількість записів даних | Кількість читань блоків |
| 1 – 2.000 | |
| 2.001 – 200.000 | |
| 200.001 – 20.000.000 | |
| 20.000.001 – 2.000.000.000 |
Якщо припустити, що середня довжина запису складає 100 байт (що дає цілком реальний розмір блоку у 2 Кбайт), то звідси з неминучістю випливає, що для В*-дерев розміром до 200 Гбайт (!) потрібно в середньому лише 5 (!) операцій доступу до фізичних блоків в процесі пошуку запису, або глобального вузла.
Дана оцінка зроблена без урахування так званого методу стиску ключів, що використовується і при інших методах організації файлів.
Ніяка інша форма організації файлів не виявляється настільки ж сприятлива для читання, запису та корегування окремих записів даних. В*-дерева оптимальні для реалізації випадкового доступу до записів по мірі виявлення запитів, що виникають в системах OLTP.
Яким же чином виконується доступ до наступного запису або послідовна обробка всього файлу – двох інших критеріїв з переліку на початку розділу?
Доступ до наступного запису нічим ні ускладнений, якщо він розташований у тому ж блоці (що вельми вірогідно). При необхідності прочитати наступний блок даних було б потрібно повернутися на рівень покажчиків для визначення його номеру.
Але в ієрархічних базах даних (типу М-систем) подібних повернень удасться уникнути, оскільки у кожному блоці даних зберігається номер наступного – в порядку сортування – блоку даних. Це поле носить найменування покажчик вправо. Це призводить до деякого надлишку, з яким приходиться миритися, бо одразу ж з¢являється можливість обробки наступного (логічно, а не фізично) блоку даних без повернення на рівень блоків покажчиків. А значить, можна обробити все дерево, не читаючи блоку покажчиків, за винятком першого звертання.
Більш того, ці додаткові покажчики дуже корисні при відновленні цілісності даних після аварії, що призвела у негідність окремі блоки покажчиків та даних. Якщо ж окрім покажчиків вправо зберігаються ще й покажчики вліво (на блок, що передує сортуванню), то навіть повна реконструкція структури В*-дерева виконується значно простіше, а таким чином може бути виконана автоматично відповідною утилітою.
Таким чином, В*-дерева відрізняються динамічністю та здатністю до самоорганізації. Як було вказано вище, записи вдається розміщати в блоках у правильних позиціях, відповідних порядку сортування. Область переповнення відсутня, що виключає необхідність у періодичній реорганізації древовидної структури. Застосування доступно постійно, що в деяких секторах ринку систем OLTP є обов¢язковою умовою.
Поиск по сайту: