Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2002
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Організація баз даних і знань
Частина тексту файла (без зображень, графіків і формул):
НАВЧАЛЬНЕ ВИДАННЯ
ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ
Методичні вказівки до лабораторної роботи N3 курсу "Організація баз даних і знань" для студентiв базового напрямку "Комп’ютернi науки
Укладачi Керницький Андрій Богданович
Мотика Ігор Іванович
Стех Юрій Васильович
Редактор Черничевич О.
МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи N 3
з курсу "Організація баз даних і знань "
для студентiв базового напрямку 6.0804
"Комп'ютернi науки"
Затверджено на засiданнi кафедри Системи автоматизованого проектування"
Протокол N14 вiд 03.04.1997р.
Львiв 2002
ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ: Методичні вказівки до лабораторної роботи N3 з курсу " Організація баз даниз і знань " для студентiв базового напрямку "Комп'ютернi науки" / Укл. А.Б.Керницький, І.І.Мотика, Ю.В.Стех. - Львiв: НУЛП, 2002.-10с.
Укладачi: А.Б.Керницький, маг.техн.наук.
І.І.Мотика, канд.техн.наук,доц.,
Ю.В.Стех, канд.техн.наук, доц.
Вiдповiдальний за випуск С.П.Ткаченко, канд.техн.наук, доц.
Рецензенти: М.Б.Близнюк, канд.техн.наук, доц.
I.I.Чура, канд.техн.наук, доц.
Додаток
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
1. Написати програму, яка реалiзує алгоритми роботи iндексно-послiдов ного методу доступу до iнформацiї на зовнiшнiх носiях:
1.1. Пошук елемента даних за введеним ключем.
1.2. Вставка елемента даних.
1.3. Видалення елемента даних.
1.4. Модифiкацiя елемента даних.
2. Варіанти файлів даних:
- студентська група,
- кафедра САП,
- НУЛП,
- футбольна лiга,
- прокат авто,
- мережа кiнотеатрiв.
11
3. КОНТРОЛЬНІ ЗАПИТАННЯ
Як органiзовується iндексний файл?
Чому швидкодiя пошуку у iндексному файлі вища?
Як здiйснюється пошук в iндексi?
Як здiйснюється вставка нового елемента даних при iндексно-послiдовному методi?
Що таке ділянка переповнення?
Як органiзовується багатоiєрархiчна адресацiя?
Як організовується видалення при iндексно-послiдовному методi?
10
1. МЕТА РОБОТИ
озглянути органiзацiю i ведення файлiв iндексно-послiдовного доступу; набути практичнi навички у програмуваннi алгоритмiв iндексно-послiдовного доступу до файлiв на зовнiшнiх запам'ятовуючих пристроях.
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ндексний файл завжди впорядкований за так званим первинним ключем (головний атрибут фiзичного запису).
Оскiльки у цьому методi i записи файла даних впорядкованi за ключем, iндекс звичайно мiстить не посилання на окремий запис, а посилання на блоки записiв, всерединi яких можна здiйснювати пошук i сканування. Збереження посилань на блоки записiв, а не на окремi записи значно зменшує розмiр iндексу. Наприклад, якщо в блоцi зберiгається 10 записiв, то для нього в iндексному файлi буде одна стаття, а не 10, i розмiр iндексного файла зменшується в 10 разiв.
3
745
756
781
867
875
879
899
904
910
Блок2
Блок3
Блок1
Індексний файл
Файл даних
Рис.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я дає змогу покращити характеристики доступу.
Індексний файл складається з пар (значення ключа, адреса блока). Пара (v,b) з'являється у файлi iндексу, якщо перший запис у блоцi з адресою b має значення ключа v. Перше поле є ключем файла iндексу, який пiдтримується вiдсортованим за значенням свого ключа.
4
kблока<>k
j:=j+довжина запису
кц
<надрукувати знайдений запис>
iнакше <адресний простiр файла менший за шуканий>
<Закрити файли А i В>
2.4. АЛГОРИТМ ВСТАВЛЯННЯ
<Зчитати ключ запису, який потрiбно вставити><m>
<Вiдкрити 2 файли: файл А - iндексний, файл В - записiв>
<Зчитати з А першу статтю для одержання iндексу><k>
доки не кiнець файла А та m>k
<зчитати iндекс з А><k>
якщо m<k
тодi j:= <номер першого елемента блока>, u:=false
доки j<>k та u:=false
якщо <ї вiльне мiсце> тодi u:= true; s:=j
iнакше j:=j+1
якщо u:=true
тодi якщо s<m
тодi <змiстити всi елементи на одиницю вгору>
iнакше < змiстити всi елементи на одиницю вниз>
<записати в позицiю m запис>
iнакше {блок переповнений}
<останнiй елемент занести у вiльне мiсце зони
переповнення>
<змiстити елементи з m до кiнця блока>
<записати в позицiю m вхiдний запис>
iнакше <адресний простiр файла менший за шуканий>
<Закрити файли А i В>
9
2.2.4. ВИДАЛЕННЯ
Як i пiд час вставлення запису, у даному випадку iснує кiлька стратегiй. (Наприклад, iснує стратегiя, яка не допускає присутностi блокiв, заповнених менше нiж наполовину.) Розглянемо стратегiю, що використовується для невеликої кiлькостi видалень.
Для видалення запису iз значенням ключа v1 використовуємо спочатку процедуру пошуку, щоб знайти цей запис. Перемiщаємо всi записи праворуч вiд нього на один субблок лiворуч для лiквiдацiї промiжку i приводимо у порядок показник "заповнений/незаповнений" у заголовку. Якщо блок став вiльним, видаляємо запис для даного блока в iндексi за допомогою стратегiї видалення.
Якщо блок пiсля видалення запису iз значенням ключа v1 залишається непорожнiм, то операцiю можна вважати закiнченою за умови, що видалений запис не був першим у блоцi. інакше потрiбно модифiкувати запис iндексу для цього блока.
2.3. АЛГОРИТМ ПОШУКУ
<Зчитати ключ запису, який потрiбно знайти><k>
<Вiдкрити 2 файли: файл А - iндексний, файл В - записiв>
<Зчитати з А першу статтю для одержання iндекса><V>
доки не кiнець файла А та k>V
пц
якщо k>V
тодi <зчитати iндекс з А><V>
кц
якщо k<V
тодi j:=<адреса першого елемента блока><V-1>
доки
пц
Блок 8
Блок 7
Блок 9
Значення дійсного ключа
Адресний номер блока
001 386 710
7 8 9
Значення дійсного ключа
Адресний номер блока
001 .. 151
1 2
386 .. 537
3 4
710 .. 786
5 6
001 .. 150
151 .. 385
386 .. 536
538 .. 678
710 .. 785
786 .. 805
Індексний файл 2-го рівня
Індексний файл 1-го рівня
Файл даних
Блок 1
Блок 2
Блок 3
Блок 4
Блок 5
Блок 6
8
Рис.2 Багатоiєрархiчна iндексацiя при iндексно-послiдовному методi доступу.
В iндексно-послiдовному файлi необхiдно отримати вiдповiдi на запитання:
якщо задане значення ключа v1 для iндексного файла, знайти в iндексi такий запис (v2,b), що v2<=v1 i або (v2,b) ї останнiм записом у iндексi, або наступний запис (v3,b) задовольняє умову v1<v3. У цiй ситуацiї говорять, що v2 покриває v1. Отже, ми знаходимо блок b головного файла, що мiстить запис iз значенням ключа v1, оскiльки файл iндексу з гарантiїю є вiдсортованим.
2.1. ПОШУК В ІНДЕКСІ
Нехай є файл iндексу i необхiдно знайти запис (v2,b), такий, що v2 покриває задане значення ключа v1. Одна iз
5
стратегiй полягає у використаннi лiнiйного пошуку, при якому переглядаються всi записи iндексу вiд самого початку доти, поки не буде знайдено запис, що покриває v1. Цей метод доц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стю уникнути виконання процедури реорганiзацiї.
Розглянемо операцiї пошуку, вставляння, видалення i модифiкацiї над вiдсортованим файлом iз записами, не закрiпленими вказiвниками за фіксованими адресами. Цi 4-и операцiї потребують вставляння, видалення, модифiкацiї у файлi iндексу.
Вхiдний вiдсортований файл мiститься у послiдовностi блокiв b1, b2,...,bk. Записи у кожному блоцi мiстяться у сортованоiй послiдовностi, причому записи блока bi передують записам блока bi+1. У заголовку кожного блока знаходиться iнформацiя, що вказує, який iз субблокiв мiстить записи, а який є вiльним.
2.2.1. ПОШУК
Потрiбно знайти у файлi даних запис iз значенням ключа v1. Спочатку знаходимо у файлi iндексу блок, перший запис
6
якого мiстить значення ключа v2, такого, що v2 покриває v1. Здiйснюємо у цьому блоцi пошук запису з ключем v1.
Ми можемо випадково полiпшити вiльний блок i вирiшити, що вiн мiстить запис з ключем v1. Щоб цього не сталося, необхiдно перевiрити ознаку заголовка блоку.
2.2.2. ВСТАВЛЯННЯ
З метою вставляння запису iз значенням ключа v1 використаємо процедуру пошуку, щоб знайти блок bi, у якому мав би знаходитися такий запис. Розмiстимо новий запис у вiдповiдне мiсце у блоцi bi, зберiгши сортовану послiдовнiсть порядок i перемiстивши праворуч записи iз значенням ключа, бiльшим нiж v1, щоб звiльнити мiсце для нового запису. Якщо у блоцi b1 присутнiй хоча б один вiльний субблок у нього помiстяться всi записи. Якщо v1 передує значенню ключа v2 першого запису bi, необхiдно модифiкувати статтю файла iндекса для блока bi, використовуючи модифiкацiю, i змiнити iнформацiю “заповнений/незаповнений" у заголовку блока.
Припустимо, що блок bi вже заповнений настiльки, що для нового запису немає мiсця. Можливi стратегiї вирiшення: органiзацiя блока переповнення, розщеплення блока на два напiвпорожнi блоки.
2.2.3. МОДИФІКАЦІЯ
Для модифiкацiї запису iз значенням ключа v1 спочатку використовується процедура пошуку для цього запису. Якщо модифiкацiя змiнюї ключ, це iнтерпретується як його видалення з наступним вставленням. інакше здiйснюється модифiкацiя i перезаписується даний запис.
7
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора