Навігація
Головна
 
Головна arrow Інформатика arrow Бази даних
< Попередня   ЗМІСТ   Наступна >

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

Індексний файл впорядкований по первинному ключу (головному атрибуту фізичного запису). Індекс містить посилання не на кожен запис, а на групу записів (рис. 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].

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

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

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Природознавство
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук