Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Проектування бази даних для аеропорту

Реферат Проектування бази даних для аеропорту





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


. 5 Дозвіл колізії методом вільного заміщення


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

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

Після переміщення «незаконної» записи знову вноситься запис займає своє законне місце і стає першим записом у новій ланцюжку синонімів.


. 6 Індексні файли


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

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

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


. 6.1 Файли з щільним індексом, або індексного-прямі файли.

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

Таблиця

Значення ключаНомер записи

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

Найбільш ефективним алгоритмом пошуку на упорядкованому масиві є логарифмічний, або бінарний, пошук. У теорії ймовірності його називають методом половинного ділення. Максимальне число кроків пошуку визначається двійковим логарифмом від загального числа елементів (цілей) в шуканому просторі пошуку:



де N - число елементів.

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

Відповідно до формули число звернень до диска при пошуку записи визначиться наступним чином:



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

Враховуючи що після пошуку запису в індексному блоці потрібно ще раз звернутися до основної області, у формулі, додалася одиниця (+1).

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


. 6.2 Файли з нещільним індексом, або індексного-послідовні файли

Структура записів даних в таких файлах має вигляд, представлений на рис. 4.



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

- визначається номер блоку основної області, в який необхідно помістити новий запис;

- знайдений блок зчитується в оперативну пам'ять;

- в оперативній пам'яті здійснюється коректування блоку;

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


Назад | сторінка 3 з 9 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Файли
  • Реферат на тему: Способи запису інформації на вінчестер, головки читання-запису
  • Реферат на тему: Текстові файли і різні методи шифрування
  • Реферат на тему: Програма для пошуку мінімуму функції двох дійсних змінних в заданій області
  • Реферат на тему: Роль і місце рекрутерів в процесі пошуку роботи