На сайті 11893 реферати!

Усе доступно безкоштовно, тому ми не платимо винагороди за додавання.
Авторські права на реферати належать їх авторам.

Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних

Реферати > Комп'ютерні науки > Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних

Міністерство освіти і науки України

Львівський національний університет ім. І. Франка

Факультет прикладної математики та інформатики

Кафедра теорії оптимальних процесів

Дипломна робота

Розробка та аналіз оптимальних моделей багаторівневих індексно-послідовних файлів

Виконав:

студент групи ПМа-53м

Прізвище Ім’я

Науковий керівник:

доц. Прізвище І.П.

Робота заслухана на засіданні

кафедри теорії оптимальних процесів

і рекомендовано до захисту.

Протокол № від 2010р.

Завідувач кафедри проф. Бартіш М. Я.

Львів 2010

Зміст

Вступ. 3

Розділ I. Основні поняття та особливості поставленої задачі 3

1.1. Постановка задачі 3

1.2. Теоретична частина. 3

1.3. Типові розподіли ймовірностей звертання до записів файлів бази даних. 3

Розділ II. Оптимальні моделі багаторівневих індексно-послідовних файлів. 3

2.1. Оптимальні моделі дворівневих індексно-послідовних файлів. 3

2.2. Оптимальні моделі багаторівневих індексно-послідовних файлів. 3

Розділ III. Практична частина. 3

3.1. Розігрування випадкових величин. 3

3.2. Порівняльний аналіз. 3

Висновок. 3

Список використаної літератури. 3

Вступ

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

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

На малюнку зображено індексно-послідовний файл з одним рівнем індексної частини.

Рис. 1 - Загальна структура однорівневого індексно-послідовного файлу

Де – елементи індексу, – елементи файлу даних, – вказівники на початок індексної частини та частини з даними, – часи переходу між елементами індексу та записами в базі даних, – час переходу від елементів індексу до блоку, на котрий вони вказують.

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

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

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

Рис. 2 - Загальна структура дворівневого індексно-послідовного файлу

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

Розділ I. Основні поняття та особливості поставленої задачі

1.1. Постановка задачі

В реальних задачах ми нечасто маємо справу з надходженням вимог рівномірно. Частіше має місце надходження вимог за певними законами розподілу ймовірностей.

Поставимо задачу дослідити середній час пошуку інформації для кожного з варіантів розподілу ймовірностей. Дослідити оптимальні розбиття інформації на блоки за цих умов. За критерій оптимальності візьмемо величину середнього часу пошуку (математичне сподівання), а точніше поставимо собі задачу мінімізувати його.

Розглядається побудова та аналіз оптимальних стратегій різних варіантів пошуку інформації в послідовних файлах, що містяться в зовнішній пам'яті ЕОМ, для різних законів розподілу ймовірностей звертання до записів.

Серед законів розподілу ймовірностей звертання до записів розглядаються:

· рівномірний, розподіл

· «бінарний» розподіл,

· закон Зіпфа

· узагальнений розподіл (частковим випадком якого є правило "80-20").

1.2. Теоретична частина

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

Для мінімізації математичного сподівання розробимо теоретичний механізм диференціювання з застосуванням ЕОМ, механізм отримання випадкової змінної з довільного закону розподілу (т.з. операція «розігрування змінної»).

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

Перейти на сторінку номер: 1  2  3  4  5  6 Версія для друкуВерсія для друку   Завантажити рефератЗавантажити реферат