Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Організація баз даних і знань
Група:
КН-4
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра
С А П Р
З в і т
про виконання
лабораторної роботи №2
на тему:
«ПРЯМИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ»
З курсу:
«Організація баз даних і знань»
Виконав:
ст. гр. КН-4
Львів 2007р.
Мета роботи
Розглянути органiзацiю i ведення файлiв прямого доступу; набути практичнi навички у програмуваннi алгоритмiв доступу хешуванням.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. МЕТОД ПРЯМОГО ДОСТУПУ
Головною особливiстю прямого методу доступу є взаємна однозначна вiдповiднiсть мiж ключем запису i його фiзичною адресою. Фiзичне розмiщення запису визначається безпосередньо iз значення ключа. Створивши файл прямого доступу i видiливши для нього необхiдну дiлянку пам’ятi, можна вставляти записи у будь-якi мiсця файла. Перевага такого пiдходу над послiдовною органiзацiєю файла полягає у тому, що вдається отримати запис за заданим значенням ключа без попереднього перегляду всiх попереднiх записiв файла.
ЕФЕКТИВНІСТЬ ДОСТУПУ дорiвнює одиницi.
ЕФЕКТИВНІСТЬ ЗБЕРІГАННЯ залежить вiд густини ключiв. Якщо густина низька, пам’ять використовується неефективно, оскiльки резервуються адреси, що вiдповiдають вiдсутнiм ключам. У цьому випадку доцiльно використовувати для органiзацiї файла метод хешування. Пряму адресацiю можна важати частковим випадком методу хешування.
2.2. МЕТОДИ ХЕШУВАННЯ.
На практицi кiлькiсть можливих значень ключiв набагато перевищує кiлькiсть реально присутнiх у будь-який момент значень цього ключа. У цьому випадку пряма адресацiя є невигiдною, оскiльки надто багато пам’ятi резервується для записiв, яких немає i нiколи не буде у файлi. Метод хешування дає змогу уникнути цього i водночас зберегти ефективнiсть, властиву прямiй адресацiї. На основi iнформацiї про множину фактичних значень ключiв створюється файл прямого доступу з такою кiлькiстю записiв, яка дещо перевищує фактичне значення ключiв. Вибирається функцiя хешування, яка перетворює значення ключа кожного запису в адресу блока у файлi. Зрозумiло, що хеш-функцiя h - це функцiя, яка вiдображає принцип "багато в один".
2.2.1. ПОШУК
Для того щоб за даним значенням ключа k знайти вiдповiдний запис, необхiдно визначити h(k) i потiм органiзувати лiнiйний пошук у блоцi, номер якого дорiвнює h(k). Цей пошук буде продовжуватися доти, поки не буде знайдений запис, значення первинного ключа якого збiгається iз заданим.
2.2.2. ВСТАВЛЯННЯ
Щоб вставити у файл новий запис, потрiбно за допомогою методу лiнiйного пошуку у блоцi, номер якого визначається значенням h(k), знайти вiльне мiсце. Пiсля цього на мiсце знайденого вiльного запису необхiдно розмiстити новий. Якщо при спробi помiстити новий запис у файл виявляється, що у знайденому блоцi немає вiльного мiсця, вважають, що блок переповнений.
2.2.3. ВИДАЛЕННЯ
Для видалення запису iз файла потрiбно, використовуючи метод лiнiйного пошуку, знайти запис у блоцi, номер якого дорiвнює h(k). Якщо запис буде знайдено то вiн видаляється, якщо нi, то очевидно, що блок був переповнений i необхiдно продовжити пошук.
2.2.4. МОДИФІКАЦІЯ
Якщо необхiдно модифiкувати запис, то потрiбно знайти цей запис i замiнити старi поля на новi. Нiяких iнших змiн не потрiбно.
ХЕШ-функція
0
1
2
3
4
5
6
7
8
9
10
К1
К12
Рис.1. Ілюстрацiя методу хешування
2.3. ПЕРЕПОВНЕННЯ
Для боротьби з переповненням можуть бути використанi три методи: зв’язаних блокiв, зв’язаних записiв та прогресуючого переповнення. 3.1. Метод блокiв, зв’язаних у ланцюг, полягає у такому. Коли блок переповнюється, у ньому розмiщується вказiвник на новостворений блок, призначений тiльки для записiв, що не помiстилися до першого блока. Якщо ж новостворений блок, своєю чергою, переповнений, у нього розмiщується вказiвник, що посилається на ще один знову створений блок i т.д. У результатi буде створений зв’язаний список блокiв, для всiх записiв якого значення функцiї хешування однакове. Головний недолiк методу зв’заних блокiв полягає у тому, що блоки переповнення часто виявляються заповненими лише кiлькома записами, а решта пам’тi витрачається даремно.
3.2. Якщо необхiдно вставити новий запис, а у блоцi, призначеному для цього, немає мiсця, цей запис розмiщується у перший блок переповнення, в якому є вiльне мiсце. Пiсля цього необхiдно вставити цей запис у зв’язаний список записiв iз тим самим значенням функцiї хешування.Хоча у цьому методi часто використовується менше блокiв переповнення, нiж у попередньому, пошук запису, що потрапив у дiлянку переповнення, може потребувати бiльше часу. При органiзацiї першого методу необхiдно органiзувати доступ до двох блокiв: до головного блока, номер якого визначається функцiєю хешування i до блока переповнення, що мiстить даний запис. Якщо ж використовувати другий метод, то необхiдно спочатку органiзувати доступ до головного блока, а потiм переглянути зв’язаний список записiв, що потрапили у дiлянку переповнення, тодi необхiдно, йдучи по зв’язаному списку, органiзувати доступ до блокiв доти, поки не буде знайдений блок, який мiстить шуканий запис.
3.3. Метод прогресуючого переповнення багато у чому схожий на другий метод. Вiдмiннiсть полягає у тому, що записи у блоках переповнення не об’єднуються у зв’язанi списки. У тому випадку, якщо у блоцi, номер якого визначається значенням функцiї хешування, бiльше немає мiсця, запис розмiщується у перший вiльний простiр блока переповнення. У цей блок розмiщуються записи iз рiзним значенням функцiї хешування. Для пошуку запису потрiбно спочатку органiзувати доступ до головного блока. Якщо шуканого запису немає, необхiдно, використовуючи метод лiнiйного пошуку, переглядати блоки переповнення доти, поки запис не буде знайдений. У цьому випадку будуть переглядатися навiть тi записи, що мають iншi значення функцiї хешування. Зауважимо, що другий метод має бiльшу швидкодiю, нiж третiй, оскiльки обмежує пошук лише тими записами, якi мають те саме значення функцiї хешування, що i шукана. Але третiй метод вимагає менше пам’ятi, нiж другий, оскiльки немає необхiдностi зберiгати вказiвники. Крiм того, третiй метод простiший у реалiзацiї.
2.4. ФУНКЦІЇ ХЕШУВАННЯ
Використовуючи хешування обчислюють номер блока для заданого значення первинного ключа. Вимоги до хеш-функцiї:
Забезпечення рiвномiрного розкиду значень ключiв по адресах блокiв.
Повинна якнайменше призводити до ситуацiї переповнення.
Повинна бути простою, тобто мiстити невелику кiлькiсть основних арифметичних операцiй.
Функцiю хешування вибирають у дечому довiльно. Щоб вибрати функцiю хешування, необхiдно знати, по-перше, приблизну кiлькiсть записiв у файлi i, по-друге, скiльки записiв можна помiщати у блок. Ця iнформацiя буде використовуватися для пiдрахунку кiлькостi блокiв у файлi, на основi якого можна визначити дiапазон змiни значень функцiї хешування.
2.4.1. Метод квадратiв
Ключ**2. Визначають число, що складається iз центральних цифр. Для отримання номера дiлянки помножити отримане число на константу.
Адреса блока = 1 7 2 1 4 8**2 =6 2 9 6 3 4 9 3 3 9 0 4
*0.7=24445
2.4.2. Метод дiлення з використанням частки
Частка вiд дiлення є вiдносною адресою. 172148/6997 = 4220, де 6997 є простим числом.
2.4.3. Дiлення на просте число
Кiлькiсть блокiв вибирається так, щоб воно було простим числом. Використовується наступна функцiя хешування:
h(значення ключа)=(значення люча)mod(кiлькiсть блокiв). Вибiр простого числа як дiльника дає змогу органiзувати перемiшування.
2.4.4. Використання кiлькох цифр ключа
Можна як значення функцiї хешування використовувати кiлька цифр iз значення ключа. Наприклад, якщо для цiєї мети вибрати другу i п’яту цифри наступного ключа, то h(935718)=31 i h(955617)=51.
Крiм наведенних iснує багато функцiй хешування.
3. КОНТРОЛЬНI ЗАПИТАННЯ
1. Яка ефективнiсть доступу, зберiганя у файлах прямого доступу?
2. Що таке метод хешування?
3. Як здiйснюється пошук при доступi до файла методом хешування?
4. Як видаляють запис iз файла прямого доступу?
5. Що таке переповнення?
6. Якi методи боротьби з переповненням?
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
1. Написати програму методу прогресуючого переповнення, яка реалiзує такi функцiї:
1. Друк бази даних.
2. Зчитування запису.
3. Введення запису.
4. Видалення запису.
5. Модифiкацiя запису.
6. Вихiд.
2. Написати програму методу зв'язаних блокiв, яка реалiзує такi функцiї:
1. Друк бази даних.
2. Зчитування запису.
3. Введення запису.
4. Видалення запису.
5. Модифiкацiя запису.
6. Вихiд.
3. Написати програму методу зв'язаних записiв, яка реалiзує такi функцiї:
1. Друк бази даних.
2. Зчитування запису.
3. Введення запису.
4. Видалення запису.
5. Модифiкацiя запису.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора