Індексного-послідовний метод

Індексний файл впорядкований по первинному ключу (головному атрибуту фізичного запису). Індекс містить посилання не на кожен запис, а на групу записів (рис. 9.3). Послідовна організація індексного файлу допускає у свою чергу його індексацію - багаторівнева індексація (рис. 9.4).

Індексного-послідовний метод

Рис. 9.3. Індексного-послідовний метод

Многоуровневая.індексація

Рис. 9.4. Многоуровневая.індексація

Процедура додавання можлива у двох видах.

  • 1. Новий запис запам'ятовується в окремому файлі (області), званої областю переповнення. Блок цій області зв'язується в ланцюжок з блоком, до якого логічно належить запис. Запис вводиться в основний файл.
  • 2. Якщо місця в блоці основного файлу немає, запис ділиться навпіл і в індексному файлі створюється новий блок.

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

При довільних методах записи фізично розташовуються довільно.

Індексного-довільний метод

Записи зберігаються в довільному порядку. Створюється окремий файл, що зберігає значення дійсного ключа і фізичної адреси (індексу). Кожній запису відповідає індекс. Загальна схема показана на рис. 9.5. Ідея методу відображена на рис. 9.6: між вироблюваним (відносним) адресою і фізичної записом (абсолютним адресою) існує взаимооднозначное відповідність.

Різновидом цього методу є наявність щільного індексу: крім головного файлу створюється допоміжний файл, званий щільним індексом. Він складається з запису (v, р) для будь-якого значення ключа v в головному файлі, де р - покажчик на запис головного файлу зі значенням ключа v.

Індексного-довільний метод

Рис. 9.5. Індексного-довільний метод

Ідея методу кешування: ПР - програма рандомізації

Рис. 9.6. Ідея методу кешування: ПР - програма рандомізації

Прямий метод

Мається взаимооднозначное відповідність між ключем запису і її фізичною адресою (рис. 9.7). Виділяють два види адрес (рис. 9.8): відносний і абсолютний.

У цьому методі необхідно перетворення і треба чітко знати вихідні дані та організацію пам'яті. Ключі повинні бути унікальними.

Ефективність доступу дорівнює 1, а ефективність зберігання залежить від щільності ключів.

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

Прямий метод

Рис. 9.7. Прямий метод

Абсолютний і відносний адреси

Рис. 9.8. Абсолютний і відносний адреси

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

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

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

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

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

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

Найпростішим алгоритмом кешування може бути функція f (k) = A: (mod 10), де до - ключ, ціле число (табл. 9.3). Така функція не дає рівномірного розподілу, і тому використовують більш відповідні функції, наприклад f = сума цифр ключа (mod 10) + 1.

"Платою" за швидкість пошуку і оновлення в режимі 2 є порушення впорядкованості файлу, втрата можливості виконувати пакетну обробку по первинному ключу. Час обробки в режимі 1 велике.

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

Таблиця 9.3

Прямий метод доступу

Вихідні ключі

Перетворені об'єктні ключі

Адреса зберігання (відносний N блоку)

Х101

01

01 XI01

XI02

02

02 XI02

XI03

03

03 Х103

Х199

99

99 Х199

Y500

100

100 Y501

Y50I

101

101 Y501

Доступ до даних і їх оновлення

Слід окремо поговорити про методи пошуку даних [9, 10] та видачі результатів (у проміжну пам'ять, на термінал) для послідовних методів обробки. Тут використовують пошук за допомогою дерева (бінарне В-, В + -дерева). Бінарне дерево є різновидом У-дерева. По-дерево допускає більш двох гілок, що виходять з однієї вершини. Будь-яка вершина складається із сукупності значень первинного ключа, покажчиків індексів і (асоційованих) даних. Покажчик індексу використовується для переходу на наступний, більш низький рівень вершин (рис. 9.9). "Збережені" у вершині дані фактично являють собою сукупність покажчиків даних і служать для фізичної організації даних, визначення положення даних, ключове значення яких зберігається в цій вершині індексу. Фізична організація ветвящейся вершини В-дерева подібна фізичної послідовної структурі. Алгоритм роботи бінарного дерева (у вершинах) представлений на рис. 9.10.

Цей метод дає гарне використання пам'яті, володіє малим числом підоперацій. Включення і видалення даних досить просто і ефективно.

Використання В-дерева

Рис. 9.9. Використання В-дерева

Алгоритм пошуку по В-дереву

Рис. 9.10. Алгоритм пошуку по В-дереву: КЗ - ключ запиту; КД - ключ даних

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

В В + -дерев його копія поміщається в ліву частину правого листа, що дозволяє спростити операції додавання і видалення [8].

Підводячи деякі підсумки, можна зробити наступні попередні висновки.

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

 
< Попер   ЗМІСТ   Наст >