Інформаційні системи та структури даних - Контрольна

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Розділ3

Назвіть різновиди бінарних дерев пошуку

3) Назвіть різновиди бінарних дерев пошуку 1)збалансоване, 2) AVL

Бінарне дерево T_NR = (T_t, R, T_r) має кореневу вершину R, a ліве T_t та праве T_r піддерева кореня R мають відповідно t та r вершин,

причому t >= 0, r >= 0, t + r =NR – 1. У бінарному дереві пошуку кожна вершина пойменована первинним ключем асоційованих даних і 

розташована у лексикографічному порядку, тобто для вершини j ключі вершин T_t лексикографічно передують ключу вершини j і ключам вершин T_r. У разі пошуку в такому дереві спочатку переглядають корінь R і порівнюють ключ пошуку k з ключем кореня k_R. У разі k = k_R

пошук завершено успішно. Якщо k < k_R , пошук продовжується у лівому піддереві T_t ; а якщо k > k_R , – у правому T_r .
Якщо досягнуто лист i та k != k_i, то пошук закінчено без успіху. Лист – вершина бінарного дерева пошуку, яка немає підде¬рев 

(кінцева вершина). Кожна вершина бінарного дерева пошуку зберігає ключ, лівий і правий покажчик. Ключ вершини складається з величини первинного ключа і, можливо, значень кількох неключових елементів даних; кожна вершина асоціюється з певним записом чи конкретними даними. Для додавання нової вершини спочатку по ключу шукають вершину, асоційовану з даними. Якщо пошук безуспішний на листі j, нова вершина додається до дерева як ліве чи праве піддерево листа j залежно від того, відповідно менше чи більше ключ за kj. Причому довжина шляху до ве-ршини залежить від порядку, у якому зберено ключі; тому форма отриманого дерева змінюється від лінійного списку (рис. 30а) до повністю збалансованого дерева (рис. 30б). Зазвичай форма дерева є чимось середнім між цими екстремальними випадками (рис. 30в). Для NR ключів середня довжина шляху до вершини змінюється від (1+NR)/2 для лінійного списку до log2(NR+l) –2 для збалансованого дерева. За відсутності порядку середня довжина шляху – 1,4log2NR для безуспішного пошуку і 1,4log2(NR-1) для успішного. --Різновиди-- 1)збалансоване, 2) AVL У бінарному дереві пошуку баланс спрощує операції вибірки і поновлення. Рівень L_i листа i визначає довжину шляху від кореня T_NR до листа i. Якщо корінь має рівень 0, висоту дерева ви-значають як максимальний рівень усіх його вершин. Дерево називають збалансованим, якщо різ-ниця рівнів будь-яких двох листів не перевищує одиниці.

Якщо рівноймовірно звертання до кожної з вершин, то у збалансованому дереві мінімізовано середню довжина доступу .

Дерево збалансоване за висотою і називається AVL-деревом, якщо для будь-якої його вершини різниця висоти її лівого і правого піддерев не перевищує одиниці. Намалювати. Визначення балансу AVL-дерева менш строге, ніж для збалансованого бінарного дерева пошуку. Це ілюструє рис.32 для пятирівневих дерев. Для додавання нових вершин у мінімальному збалансованому бінарному дереві на вільні тільки 15 місць, тобто 2h-1–1, де h – число рівнів дерева, а в AVL-дерева на рис. 32б – 19 місць.

Очевидно, AVL-дерево доцільніше для орга-нізації збереження даних у БД.

В чому полягає різниця між збалансованим бінарним деревом і AVL-деревом?

4) В чому полягає різниця між збалансованим бінарним деревом і AVL-деревом? У бінарному дереві пошуку баланс спрощує операції вибірки і поновлення. Рівень L_i листа i визначає довжину шляху від кореня T_NR до листа i. Якщо корінь має рівень 0, висоту дерева ви-значають як максимальний рівень усіх його вершин. Дерево називають збалансованим, якщо різ-ниця рівнів будь-яких двох листів не перевищує одиниці.

Якщо рівноймовірно звертання до кожної з вершин, то у збалансованому дереві мінімізовано середню довжина доступу .

Дерево збалансоване за висотою і називається AVL-деревом, якщо для будь-якої його вершини різниця висоти її лівого і правого піддерев не перевищує одиниці. Намалювати. Визначення балансу AVL-дерева менш строге, ніж для збалансованого бінарного дерева пошуку. Це ілюструє рис.32 для пятирівневих дерев. Для додавання нових вершин у мінімальному збалансованому бінарному дереві на вільні тільки 15 місць, тобто 2h-1–1, де h – число рівнів дерева, а в AVL-дерева на рис. 32б – 19 місць.

Очевидно, AVL-дерево доцільніше для орга-нізації збереження даних у БД.

Чому для ведення індексів баз (система інформаційних ресурсів СКБД) доцільніші AVL-дерева, а не збалансовані бінарні

5) Чому для ведення індексів баз (система інформаційних ресурсів СКБД) доцільніші AVL-дерева, а не збалансовані бінарні У бінарному дереві пошуку баланс спрощує операції вибірки і поновлення. Рівень L_i листа i визначає довжину шляху від кореня T_NR до листа i. Якщо корінь має рівень 0, висоту дерева ви-значають як максимальний рівень усіх його вершин. Дерево називають збалансованим, якщо різ-ниця рівнів будь-яких двох листів не перевищує одиниці.

Якщо рівноймовірно звертання до кожної з вершин, то у збалансованому дереві мінімізовано середню довжина доступу .

Дерево збалансоване за висотою і називається AVL-деревом, якщо для будь-якої його вершини різниця висоти її лівого і правого піддерев не перевищує одиниці. Намалювати. --Причина-- Визначення балансу AVL-дерева менш строге, ніж для збалансованого бінарного дерева пошуку. Це ілюструє рис.32 для пятирівневих дерев. Для додавання нових вершин у мінімальному збалансованому бінарному дереві на вільні тільки 15 місць, тобто 2h-1–1, де h – число рівнів дерева, а в AVL-дерева на рис. 32б – 19 місць.

Очевидно, AVL-дерево доцільніше для орга-нізації збереження даних у БД.

Як видалити вершину з незбалансованого впорядкованого бінарного дерева пошуку?

6) Як видалити вершину з незбалансованого впорядкованого бінарного дерева пошуку? Tree - повне бінарне дерево. невикористані вершини позначаються 0. мал а) Level Nodes 1) 22; 2)12 30; 3)8 15 26 32; 4)4 9 14 18 0 27 0 0 мал б) 1)22; 2)14 30; 3)8 15 26 32; 4)4 9 0 18 0 27 0 0; У незбалансованому дереві вершину видаляють зміною значень відповідних покажчиків, а для збереження бінарності дерева треба перемістити певні вершини. На рис.33 проілюстровано видалення вершини 12. Якби в неї не було піддерев, то досить було б установити в нуль лівий по-кажчик вершини 22. Якби у вершини 12 було відсутнє тільки одне з піддерев, то треба було б перемістити друге піддерево на місце вершини 12, яку видаляють; для цього досить установити лівий покажчик вершини 22 на корінь цього піддерева. На рис. 33а у найважчому випадку у вершини 12, яку видаляють, є ліве і праве піддерева. Шукають у правому піддереві вершини 12, рекурсивно проходячи по лівих покажчиках до виявлення листа 14 з найменшим ключем у піддереві; при цьому він більше кожного ключа лівого піддерева вершини 12, що видаляється. Оскільки в неї немає піддерев, перерозподіл вершин дерева зводиться до мінімуму. Вершина 14 додається замість вершини, 12 що видаляється. Якби у вершини 17 не було лівого піддерева, то вона сама стала б на місце 12. Оцінка операції видалення змінюється від найпростішого випадку, коли досить змінити значення лівого покажчика вершини 22, до найскладнішого, – коли треба видалити корінь і переглянути вершини по усій висоті правого піддерева.

Як додати вершину до AVL-дерева?

7) Як додати вершину до AVL-дерева?

Додавання нової вершини до AVL-дерева викликає одинарний чи подвійний поворот. У гіршому випадку подвійний поворот стосується трьох вершин і включає обмін двома піддеревами між вихідними вершинами

Як видалити вершину з AVL-дерева?

8) Як видалити вершину з AVL-дерева? Видалення вершини з AVL-дерева складніше за операцію додавання. Так, для видалення вершини L на рис.37 треба виконати два одинарних повороти (позначено жирними лініями) окремо для пар вершин Е, Н та J, К. Нижня оцінка проста: при видаленні вершини-листа і збереженні балансу досить виконати одну операцію. У розрахунку верхньої оцінки варто врахувати log2NR поворотів, що стосуються щоразу трьох вершин для кожного повороту (дві вершини, що беруть участь у повороті, і початкова вершина піддерева).

Що таке В-дерево?

14) Що таке В-дерево? В-дерево використовується для керування індексами великого розміру, забезпечує проду-ктивність операцій вибірки і відновлення й у порівнянні з бінарними деревами вигідно відрізняєть-ся меншою потребою у додатковій реорганізації. В-дерево відноситься до багатоходових де-рев, які допускають більш двох гілок, що виходять з однієї вершини. В-дерево цілком збалансова-но по висоті, тобто всі його гілки мають одну висоту h. Кожна вершина В-дерева складається із сукупності значень первинного ключа і покажчиків індексу, використовуваних для переходу на ни-жчий рівень В-дерева. Окрема сукупність покажчиків служить для визначення місця розташування асоційованих даних, ключі яких зберігає ця вершина В-дерева. Асоційовані дані можна розмістити безпосередньо у вершинах індексу, але для БД великої розмірності доцільніше використовувати В-дерева тільки для організації індексу, а дані розташовувати в окремій області. На початку 70-х років В-дерева було досліджено для організації ефективного збереження індексів великого розміру і швидкої довільної вибірки даних. Фірма IBM за принципом В-дерева реалізувала відомий метод доступу VSAM. Основний недолік В-дерев – відсутність засобів вибірки даних за вторинним ключем. Пе-ревага В-дерева – корисне застосування простору пам'яті для збереження асоційованих даних перевищує 50%, а Довільний доступ до даних реалізується малою кількістю операцій і за ефекти-вністю аналогічний методам хешування і багаторівневого довідника. Показники вершин В-дерева ступеня k див. у табл. 26. В-дерево ступеня 1, у якому з ко-жної вершини виходять точно дві гілки, – це збалансоване бінарне дерево пошуку. Унаслідок змінної кількості ключів у вершинах В-дерева зручніші за бінарні, оскільки суттєво більше число операцій додавання і видалення не потребують перетворення В-дерева. Таблиця 26 – Дані вершин В-дерева степеня k --Вид вершини; Кількість ключів; Кількість гілок;-- --Корінь; 1 <= q ? k;2 <= w <= k+1;-- --Лист; k <= q <= 2k; - ; -- --Розгалужена; k <= q <= 2k; k+1 <= w <= 2k+1; -- У порівнянні з бінарним деревом пошуку зазначимо зменшення висоти В-дерев, особливо зі зростанням ступеня В-дерева. Отже, В-дерево потенційно при-скорює вибірку порівняно з бінарним деревом пошуку. Крім допуску для кожної вершини кількох гілок, механізм пошуку В-дерева аналогічний бінарному дереву. Упорядковані ключі у вершині про-глядають для пошуку збереженого ключа, рівного чи більшого шуканого. Якщо знайдений ключ, рівний шуканому, пошук вважається успішним і місце розташування даних установлюється за від-повідним покажчиком. Якщо в позиції i знайдено ключ, більший шуканого, то переходимо на вер-шину наступного рівня індексу Pi-1 і повторюємо перегляд обраної вершини лівого піддерева. Як-що всі збережені у вершині ключі менше шуканого, то переходимо на наступний рівень згідно зі значенням самого правого покажчика Pq+1 правого піддерева.

Чим відрізняються збалансовані впорядковані бінарні дерева від багатоходових?

15) Чим відрізняються збалансовані впорядковані бінарні дерева від багатоходових? Дерево називають збалансованим, якщо різниця рівнів будь-яких двох листів не перевищує одиниці. Якщо рівноймовірно звертання до кожної з вершин, то у збалансованому дереві мінімізовано середню довжина доступу. Багатоходовs дерева допускають більш двох гілок, що виходять з однієї вершини.

Коли багатоходове дерево є збалансованим впорядкованим бінарним деревом?

16) Коли багатоходове дерево є збалансованим впорядкованим бінарним деревом? Коли В-дерево ступеня 1, у якому з кожної вершини виходять точно дві гілки, – це збалансоване бінарне дерево пошуку.

Назвіть проблеми модернізації (поновлення) В-дерева?

17) Назвіть проблеми модернізації (поновлення) В-дерева? Продуктивність поновлення. Через баланс характеристики поновлення В-дерева і бінарного дерева пошуку збігаються. У гіршому випадку відновлення балансу після операцій додавання і видалення стосується вершин по усій висоті В-дерева; треба видалити стару вершину, потім знайти відповідне місце і додати нову. А найпростіший випадок поновлення – це зміна неключових елементів асоційованих даних після того, як за ключем знайдено відповідну вершину. Операція додавання нового ключа до В-дерева починають з пошуку його місця в конкретній вершині. Оскільки новий ключ можна додати тільки до листка, треба пройти не менше h вершин і після завершення пошуку вершини для нового ключа можливі чотири випадки. Випадок 1, найпростіший, коли в листі є місце для нового ключа. Варто тільки розташувати новий ключ у лексикографічному порядку цього листка. Випадок 2. Лист містить 2k ключів, а після додавання нового ключа їх стане 2k+1. Цей лист варто розділити на два листи, кожний з який містить k ключів, а один з цих ключів (можливо, но-вий) додати до батьківської вершини, припустивши, що ця вершина неповна. Випадок 3. Вершина-батько теж повна і її треба розділити на дві; у гіршому випадку розпо-діл вершин може поширитися на усі вершини аж до кореня, причому висота В-дерева збільшиться на 1. Випадок 4. Замість поділу заповненої вершини для додавання нового ключа можна про-аналізувати праву подібну їй вершину на наявність в ній вільного місця для можливого перегрупу-вання ключів за участю заповненої вершини. Якщо в ній вільні не менше двох ключових позицій, то відповідну кількість ключів із заповненої вершини можна зрушити у початкову вершину, вити-снувши з неї таку ж кількість ключів у праву подібну вершину; причому зберігаються лексико-графічний порядок вершин та однаковий ступінь їхнього корисного застосування. Фактично оцінка методу перерозподілу «переповненої» вершини більше, ніж методу по-ділу вершини, за умови, що поділ не поширюється нагору по дереву. Сполучення цих методів під-вищує ефективність додавання, дозволяючи уникати зайвого поділу вершин. Як і для операції додавання, у разі видалення ключа з В-дерева можливі три випадки. Ви-даленню ключа передує успішний пошук вершини, що містить цей ключ. Випадок 1, найпростіший, коли ключ видаляється з листа, у ньому як і раніше залишається не менше k ключів і відсутнє так зване антипереповнення Випадок 2 пов'язано з видаленням ключа з розгалуженої вершини. Навіть за відсутності антипереповнення його варто замінити іншим ключем, щоб зберегти праве піддерево ключа, що видаляють. Його заміщують на ключ з лівого листа правого піддерева ключа, що видаляють. Аналогічну процедуру застосовують для видалення ключа з незбалансованого бінарного дерева пошуку. Для видалення ключа з кореня треба переглянути максимум h вершин. Як тільки знайдено лист, лівий ключ з нього віддаляють і додають у нову вершину. Якщо видалення ключа з листа не викликає антипереповнення, операцію закінчують. Процедура включає:

-пошук лівого листа у правому піддереві;

-видалення ключа з листа за відсутності антипереповнення (для випадку антиперепов-нення див. випадок 3);

-видалення ключа з розгалуженої вершини з заміною його ключем, обраним з листа.

Випадок 3. Якщо видалення ключа з листа викликає антипереповнення (у вершині зали-шається менше k ключів), то ключ, що бракує, можна зайняти з лівої чи правої сусідньої вершини. Інколи для балансу між двома сусідніми вершинами можна зайняти кілька ключів. Останнє вима-гає наявності в двох вершинах не менш 2k ключів. Якщо ключів менше 2k, то відбувається зчеп-лення вершин і всі ключі переносять в одну з вершин, а іншу вершину з дерева віддаляють. Зчеп-лення протилежне операції видалення вершин і потребує також пересилання у вершину, що за-лишилася, з початкової вершини ключа, що розділяє дві сусідні вершини. Правда, видалення клю-ча з початкової вершини може викликати в ній антипереповнення, і в гіршому випадку воно може поширитися нагору до кореня. Можливі такі операції для антипереповнення:

-перерозподіл ключів у вершинах;

-зчеплення вершин одного рівня;

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

Що таке В+-дерево?

23) Що таке В+-дерево? В*-дерево чи В+-дерево як поширений варіант В-дерева характеризується спільним роз-ташуванням у листах ключів та асоційованих даних. У В*-дереві здубльовано деякі ключі разом з їхніми даними в листі, чим забезпечено досить швидку обробку як показав досвід реалізації індек-сів M[UMPS]-застосувань, що підтримують БД із необмеженим адресним простором.

Порівняємо показники В*-дерева і В-дерева. 1. В обох випадках завантаження індексу виконують знизу нагору. Перші ключі завантажують на рівень h (у початковий момент h=1), і після розподілу вершини ключ додають у вершину на рівень h–1; процес повторюється, поки не завантажено всі ключі. Обмеження на кількість ключів у вершині В-дерева від k до 2k також відноситься і до В*-дерев; виняток в обох випадках складає корінь. 2. Листи В-дерева складено з k <= NK <= 2k ключів і покажчиків на асоційовані дані, а В*-дерева – з k <= NK <= 2k ключів, асоційованих даних і одного покажчика на наступний лист. Вихо-дить, формати і розміри листів в обох деревах різні. 3. По суті формат розгалуженої вершини В-дерева й В*-дерева однаковий. Відмінність В*-дерева щодо початкового завантаження (та операцій доповнення) полягає в тому, що всі ключі зберігають в листах і, крім того, частина їх дублюють в індексі. На рис.44 наведено приклад поетапного завантаження В-дерева і В*-дерева. Якщо вершина поділяється, то в обох випадках у початкову вершину пересилається значення середнього ключа, а в В*-дереві його копію розміщено в лівій частині правого листа початкової вершини. Процедура розподілу розгалужених вершин в обох деревах виконується однаково. 4. Операція вибірки в В*-дереві завжди займає h доступів до листа. Якщо у вершині індек-су виявлено шукане значення ключа, здійснюється доступ до правого піддерева і пошук продов-жується до листа. Навпаки, при виявленні шуканого ключа у В-дереві пошук може завершитися в середині дерева. 5. Для видалення з В*-дерева досить видалити значення ключа з листа. Усі копії цього ключа в індексі можуть залишатися там, поки це корисно для процесу вибірки. Як наслідок, за ключі індексу в В*-дереві можуть виступати неключові значення. Любий ключ можна видалити з розгалуженої вершини індексу шляхом перерозподілу чи зчеплення вершин. Через відсутність у розгалужених вершинах покажчиків на асоційовані дані В*-дерево про-стіше за В-дерево. Продуктивність операцій поновлення В*-дерева і В-дерева практично однако-ва, за винятком деяких випадків операцій додавання і видалення.

Що таке В*-дерево?

28) Назвіть методи звуження зони пошуку у зв’язних списках? 3.4 Довідники Звуження зони пошуку як термін введено для групи методів, здатних одразу вийти на звужену зону пошуку та обмежити її наступну обробку. При послідовному пошуку аналізують кожен елемент списку в порядку їхнього розташування в основній пам'яті. Пошук у зв'язному списку ви-значено порядком з'єднання елементів. В упорядкованому списку пошук може завершитися до перевірки всіх елементів. Крім очевидної переваги, недоліки цих методів – необхідність продовження пошуку і скла-дніший, чим у зв'язному списку, процес додавання і видалення даних. Для звуження зони пошуку треба вирішити ті ж задачі, що і для збалансованих бінарних дерев пошуку і В-дерев: - перетворення шуканого значення ключа на адресу пам'яті, де розміщено дані; - пошук за ключем чи встановлення факту, що шукані дані в списку відсутні; - зміна при додаванні в список нових даних і видаленні з нього непотрібних; - переповнення області, виділеної спискам чи підспискам, і одержання нової області. У разі застосування методу довідника чи таблиці вмісту список насамперед поділяють на підсписки. Потім формують таблицю вмісту, у якій для кожного підсписку заводять одну стаття, а для входу використовують ключ, за яким шукають статтю. Стаття направляє до підсписку – об-ласті розташування шуканих даних.

--Види довідників-- --множинний довідник-- Як сукупність додаткових довідників побудовано множинний довідник. Головний довідник відсилає до своєї частини – піддовідника, той у свою чергу – до підсписку, де можна знайти шукані дані. Адресу основної пам'яті можна визначити не тільки за допомогою довідника, але і спеціаль-ним перетворенням ключа. Відображаємо ключ на адресу елементу, з якого починається область розташування асоційованих даних. З цього елементу зазвичай рухаємося тільки в прямому на-прямку, хоча пошук допускає переміщення в обох напрямках залежно від ситуації, що склалася після перегляду даних. ==Спільний довідник == отримав таку назву в зв'язку з тим, що для кожного запису в довіднику передбачено одну статтю. Це спрощує пошук, особливо якщо записи мають змінну довжину та область списку розташовано на допоміжному носії, для якого послідовний пошук вимагає значних часових витрат. Стаття складається з двох частин: -ключа запису у файлі; -покажчика, що визначає місце розташування цього запису у зв'язному списку. Довідник забезпечує зв'язок 1:1, тобто для кожного запису файлу він містить одну статтю і кожна стаття від-повідає одному запису. Задавши ключ k, впродовж пошуку запису насамперед переглянемо довідник. Якщо у ньо-му відсутня стаття для ключа k, то відсутній і запис. Якщо запис існує, то знайдемо статтю, що міс-тить шуканий ключ і покажчик. Позиція запису у файлі зазвичай не відповідає позиції статті в дові-днику. По покажчику переходимо у зону, де має знаходитися шуканий запис. Перш ніж додати запис, треба перевірити її відсутність по довіднику. Для визначення віль-ного місця в списку використовують покажчик на вільну пам'ять. При видаленні у файлі варто лік-відувати запис, що там знаходиться. Якщо використано покажчик на вільну пам'ять, то немає по-треби видаляти запис зі списку, але зайнятий елемент стає недоступним. При наявності списку вільної пам'яті цей елемент можна повернути у список і повторно викоантати. Однак у будь-якому випадку треба поновити довідник. Існують два способи поновлення, кожний з яких стосується ви-далення в щільному упорядкованому списку, коли статті можна : -видалити переміщенням інших статей нагору з перекриттям статті, яку видаляють; -зберегти, але розмістивши замість ключа символ @, який показує, що запис недоступ-ний чи елемент порожній. Довідник поновлюється досить швидко, але стаття, що стосується ви-даленого запису, перевірятиметься в багатьох операціях пошуку. Довідник зазвичай щільний і упорядкований; це сприяє швидкому послідовному чи, що до-цільніше, бінарному пошуку. Не складає проблему збереження записів змінної довжини. Однак недолік такого «гроссбуху» – витрати часу на операції видалення і додавання записів у файл, оскільки треба реорганізовувати довідник. У разі значного обсягу змін доцільно використати сис-тему спільного довідника на основі зв'язного списку. Довідник на основі зв'язного списку змінювати простіше, але пошук у такому довіднику мо-жна проводити тільки послідовно. Файл довідника, побудований як бінарне дерево, забезпечує просту зміну і швидкий пошук. ==Єдиний довідник. ==Список, для якого треба утворити довідник зон звуження пошуку, чи довідник підсписків, має бути упорядкованим і щільним. Для файлу довідника підсписків (просто файл довідника) передбачено, що список (назвемо його А) поділено на n підсписків, можливо, різ-ної довжини. Для простоти нехай кожний з них містить однакове число елементів, тому: -розділимо упорядкований список L на певне число підсписків; -утворимо довідник D; -для кожного підсписку Li виділимо одну статтю довідника, що містить: а) точку, з якої варто починати перегляд у підсписку, – покажчик на підсписок Dip; б) ключ для встановлення діапазону записів у підсписку – ключ підсписку Dik. Для формування статті вибираємо: -за покажчик адресу першого запису підсписку; -ключ останнього запису підсписку. Це дає адресу, з якої варто почати перегляд, і діапазон ключів, оскільки ключ у попередній статті довідника задає нижня межа записів у даному підсписку, а ключ у даній статті – верхня ме-жа. Перший підсписок не має явної нижньої границі; тому для нижньої межі використовують най-менший можливий ключ. Критерій порівняння різновидів списку – сумарне число звертань до довідника і списку для знаходження потрібного запису чи з'ясування його відсутності. Для методу довідника це число в середньому визначити дуже просто, проглянувши половину: -довідника; -підсписку після його знаходження по довіднику. Порівняємо метод пошуку за допомогою довідника з двома іншими методами – бінарним і лінійним пошуками. Наприклад, розглянемо досить великий за розміром список, що складається з 10000 записів (N=10000), і припустимо його поділ на 100 підсписків по 100 записів у кожному (n = 100). Одержимо такі результати: -лінійний пошук вимагає N/2 = 5000 звертань; -пошук з використанням довідника вимагає n/2+n/2=100 звертань; -бінарний пошук вимагає близько log2(N-1)= 13 звертань. Тобто для обраних параметрів метод довідника поступається бінарному пошуку, якщо не зважати на необхідні обчислення. Оцінимо оптимальний розмір підсписку. Нехай список містить N записів, а кожен підсписок – Х записів; тоді в довіднику міститься N/X статей.

Число звертань ви-значається як  L=1/2(N/X+X) . Оптимальне значення Х знайдемо, диференціюючи цей вираз по Х, 

прирівнявши його до нуля і помноживши на 2Х^2. Зрештою отримаємо X=sqrt(N) . Отже, найкращий розподіл досягнуто у разі рівності sqrt(N) числа підсписків і числа елементів у кожному підсписку. Ця ситуація показана в наведеному вище прикладі з 10000 записами. ==Дворівневий довідник.== Для простого довідника sqrt(N) визначає оптимальне число елемен-тів підсписку. Іншим варіантом є збереження підсписків невеликого розміру і збільшення розміру довідника. Замість безпосереднього використання довідника для прискорення пошуку розділимо початковий довідник на піддовідники й одержимо: -головний довідник, що вказує на один чи кілька піддовідників; -піддовідник, що вказує на один чи кілька підпідсписків (частин підсписку); -статтю головного довідника, що відповідає одному підсписку, який складається з декіль-кох підпідсписків. Оптимальний розмір підсписку sqrt(N) мають довідник, піддовідник і підпідсписок. Якщо роз-мір кожного з них дорівнює n, то середнє число звертань при пошуку залишиться тим самим.

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

-зменшується сумарне число записів, що переглядаються; -збільшується обсяг пам'яті, зайнятої довідником. Важливо визначити, як одержати найбільший ефект – мінімальне число звертань при най-меншому обсязі пам'яті довідника. З чого складається «золота середина»? Так, для довідника з чотирма рівнями перша частина статті довідника є ключем останньо-го запису підсписку, на який посилається ця стаття. Частина статті, що містить покажчик, указує на піддовідник на наступному нижньому рівні. Цей піддовідник служить для підпідсписків, що склада-ють даний список. Існує п'ять піддовідників 2-го рівня, кожний з який складається з п'яти статей, що вказують на підпіддовідники 3-го рівня. На 3-му рівні маємо 25 підпіддовідників; кожний з них стосується підпідсписку. Процедура знаходження запису полягає в наступному. -У довіднику шукаємо покажчик на піддовідник. -У піддовіднику шукаємо покажчик на підпіддовідник. -У підпіддовіднику шукаємо покажчик на підпідпіддовідник. -У підпідпіддовілнику шукаємо покажчик на підсписок найнижчого рівня. -Шукаємо у цьому підсписку. На кожному з кроків проглядаємо максимум п'ять елементів. Оцінимо виграш від збіль-шення числа довідників. Для порівняння табл. 29 містить дані для довідників розміром 10000, а табл.30 – 1000000. Пам'ять для розміщення довідника зростає, але за обсягом вона і близько не підходить до розміру файлу, оскільки стаття довідника набагато менша за запис. Дворівневий довідник зменшує число звертань з 100 до 32 у випадку 10000 записів і з 1000 до 150 у випадку мільйона записів. Але в обох випадках спостерігаємо значне підвищення продук-тивності. Проте, якщо перейти до трьох рівнів, поліпшення буде порівняно невеликим, а обсяг за-йнятої пам'яті значно зросте.

Назвіть методи звуження зони пошуку у зв’язних списках?

28) Назвіть методи звуження зони пошуку у зв’язних списках? 3.4 Довідники Звуження зони пошуку як термін введено для групи методів, здатних одразу вийти на звужену зону пошуку та обмежити її наступну обробку. При послідовному пошуку аналізують кожен елемент списку в порядку їхнього розташування в основній пам'яті. Пошук у зв'язному списку ви-значено порядком з'єднання елементів. В упорядкованому списку пошук може завершитися до перевірки всіх елементів. Крім очевидної переваги, недоліки цих методів – необхідність продовження пошуку і скла-дніший, чим у зв'язному списку, процес додавання і видалення даних. Для звуження зони пошуку треба вирішити ті ж задачі, що і для збалансованих бінарних дерев пошуку і В-дерев: - перетворення шуканого значення ключа на адресу пам'яті, де розміщено дані; - пошук за ключем чи встановлення факту, що шукані дані в списку відсутні; - зміна при додаванні в список нових даних і видаленні з нього непотрібних; - переповнення області, виділеної спискам чи підспискам, і одержання нової області. У разі застосування методу довідника чи таблиці вмісту список насамперед поділяють на підсписки. Потім формують таблицю вмісту, у якій для кожного підсписку заводять одну стаття, а для входу використовують ключ, за яким шукають статтю. Стаття направляє до підсписку – об-ласті розташування шуканих даних.

Чим відрізняються збалансовані впорядковані бінарні дерева від багатоходових?

15) Чим відрізняються збалансовані впорядковані бінарні дерева від багатоходових? Дерево називають збалансованим, якщо різниця рівнів будь-яких двох листів не перевищує одиниці. Якщо рівноймовірно звертання до кожної з вершин, то у збалансованому дереві мінімізовано середню довжина доступу. Багатоходовs дерева допускають більш двох гілок, що виходять з однієї вершини.

Коли багатоходове дерево є збалансованим впорядкованим бінарним деревом?

16) Коли багатоходове дерево є збалансованим впорядкованим бінарним деревом? Коли В-дерево ступеня 1, у якому з кожної вершини виходять точно дві гілки, – це збалансоване бінарне дерево пошуку.

Назвіть проблеми модернізації (поновлення) В-дерева?

17) Назвіть проблеми модернізації (поновлення) В-дерева? Продуктивність поновлення. Через баланс характеристики поновлення В-дерева і бінарного дерева пошуку збігаються. У гіршому випадку відновлення балансу після операцій додавання і видалення стосується вершин по усій висоті В-дерева; треба видалити стару вершину, потім знайти відповідне місце і додати нову. А найпростіший випадок поновлення – це зміна неключових елементів асоційованих даних після того, як за ключем знайдено відповідну вершину. Операція додавання нового ключа до В-дерева починають з пошуку його місця в конкретній вершині. Оскільки новий ключ можна додати тільки до листка, треба пройти не менше h вершин і після завершення пошуку вершини для нового ключа можливі чотири випадки. Випадок 1, найпростіший, коли в листі є місце для нового ключа. Варто тільки розташувати новий ключ у лексикографічному порядку цього листка. Випадок 2. Лист містить 2k ключів, а після додавання нового ключа їх стане 2k+1. Цей лист варто розділити на два листи, кожний з який містить k ключів, а один з цих ключів (можливо, но-вий) додати до батьківської вершини, припустивши, що ця вершина неповна. Випадок 3. Вершина-батько теж повна і її треба розділити на дві; у гіршому випадку розпо-діл вершин може поширитися на усі вершини аж до кореня, причому висота В-дерева збільшиться на 1. Випадок 4. Замість поділу заповненої вершини для додавання нового ключа можна про-аналізувати праву подібну їй вершину на наявність в ній вільного місця для можливого перегрупу-вання ключів за участю заповненої вершини. Якщо в ній вільні не менше двох ключових позицій, то відповідну кількість ключів із заповненої вершини можна зрушити у початкову вершину, вити-снувши з неї таку ж кількість ключів у праву подібну вершину; причому зберігаються лексико-графічний порядок вершин та однаковий ступінь їхнього корисного застосування. Фактично оцінка методу перерозподілу «переповненої» вершини більше, ніж методу по-ділу вершини, за умови, що поділ не поширюється нагору по дереву. Сполучення цих методів під-вищує ефективність додавання, дозволяючи уникати зайвого поділу вершин. Як і для операції додавання, у разі видалення ключа з В-дерева можливі три випадки. Ви-даленню ключа передує успішний пошук вершини, що містить цей ключ. Випадок 1, найпростіший, коли ключ видаляється з листа, у ньому як і раніше залишається не менше k ключів і відсутнє так зване антипереповнення Випадок 2 пов'язано з видаленням ключа з розгалуженої вершини. Навіть за відсутності антипереповнення його варто замінити іншим ключем, щоб зберегти праве піддерево ключа, що видаляють. Його заміщують на ключ з лівого листа правого піддерева ключа, що видаляють. Аналогічну процедуру застосовують для видалення ключа з незбалансованого бінарного дерева пошуку. Для видалення ключа з кореня треба переглянути максимум h вершин. Як тільки знайдено лист, лівий ключ з нього віддаляють і додають у нову вершину. Якщо видалення ключа з листа не викликає антипереповнення, операцію закінчують. Процедура включає:

-пошук лівого листа у правому піддереві;

-видалення ключа з листа за відсутності антипереповнення (для випадку антиперепов-нення див. випадок 3);

-видалення ключа з розгалуженої вершини з заміною його ключем, обраним з листа.

Випадок 3. Якщо видалення ключа з листа викликає антипереповнення (у вершині зали-шається менше k ключів), то ключ, що бракує, можна зайняти з лівої чи правої сусідньої вершини. Інколи для балансу між двома сусідніми вершинами можна зайняти кілька ключів. Останнє вима-гає наявності в двох вершинах не менш 2k ключів. Якщо ключів менше 2k, то відбувається зчеп-лення вершин і всі ключі переносять в одну з вершин, а іншу вершину з дерева віддаляють. Зчеп-лення протилежне операції видалення вершин і потребує також пересилання у вершину, що за-лишилася, з початкової вершини ключа, що розділяє дві сусідні вершини. Правда, видалення клю-ча з початкової вершини може викликати в ній антипереповнення, і в гіршому випадку воно може поширитися нагору до кореня. Можливі такі операції для антипереповнення:

-перерозподіл ключів у вершинах;

-зчеплення вершин одного рівня;

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

Що таке В+-дерево?

23) Що таке В+-дерево? В*-дерево чи В+-дерево як поширений варіант В-дерева характеризується спільним роз-ташуванням у листах ключів та асоційованих даних. У В*-дереві здубльовано деякі ключі разом з їхніми даними в листі, чим забезпечено досить швидку обробку як показав досвід реалізації індек-сів M[UMPS]-застосувань, що підтримують БД із необмеженим адресним простором.

Порівняємо показники В*-дерева і В-дерева. 1. В обох випадках завантаження індексу виконують знизу нагору. Перші ключі завантажують на рівень h (у початковий момент h=1), і після розподілу вершини ключ додають у вершину на рівень h–1; процес повторюється, поки не завантажено всі ключі. Обмеження на кількість ключів у вершині В-дерева від k до 2k також відноситься і до В*-дерев; виняток в обох випадках складає корінь. 2. Листи В-дерева складено з k <= NK <= 2k ключів і покажчиків на асоційовані дані, а В*-дерева – з k <= NK <= 2k ключів, асоційованих даних і одного покажчика на наступний лист. Вихо-дить, формати і розміри листів в обох деревах різні. 3. По суті формат розгалуженої вершини В-дерева й В*-дерева однаковий. Відмінність В*-дерева щодо початкового завантаження (та операцій доповнення) полягає в тому, що всі ключі зберігають в листах і, крім того, частина їх дублюють в індексі. На рис.44 наведено приклад поетапного завантаження В-дерева і В*-дерева. Якщо вершина поділяється, то в обох випадках у початкову вершину пересилається значення середнього ключа, а в В*-дереві його копію розміщено в лівій частині правого листа початкової вершини. Процедура розподілу розгалужених вершин в обох деревах виконується однаково. 4. Операція вибірки в В*-дереві завжди займає h доступів до листа. Якщо у вершині індек-су виявлено шукане значення ключа, здійснюється доступ до правого піддерева і пошук продов-жується до листа. Навпаки, при виявленні шуканого ключа у В-дереві пошук може завершитися в середині дерева. 5. Для видалення з В*-дерева досить видалити значення ключа з листа. Усі копії цього ключа в індексі можуть залишатися там, поки це корисно для процесу вибірки. Як наслідок, за ключі індексу в В*-дереві можуть виступати неключові значення. Любий ключ можна видалити з розгалуженої вершини індексу шляхом перерозподілу чи зчеплення вершин. Через відсутність у розгалужених вершинах покажчиків на асоційовані дані В*-дерево про-стіше за В-дерево. Продуктивність операцій поновлення В*-дерева і В-дерева практично однако-ва, за винятком деяких випадків операцій додавання і видалення.

Що таке В*-дерево?

28) Назвіть методи звуження зони пошуку у зв’язних списках? 3.4 Довідники Звуження зони пошуку як термін введено для групи методів, здатних одразу вийти на звужену зону пошуку та обмежити її наступну обробку. При послідовному пошуку аналізують кожен елемент списку в порядку їхнього розташування в основній пам'яті. Пошук у зв'язному списку ви-значено порядком з'єднання елементів. В упорядкованому списку пошук може завершитися до перевірки всіх елементів. Крім очевидної переваги, недоліки цих методів – необхідність продовження пошуку і скла-дніший, чим у зв'язному списку, процес додавання і видалення даних. Для звуження зони пошуку треба вирішити ті ж задачі, що і для збалансованих бінарних дерев пошуку і В-дерев: - перетворення шуканого значення ключа на адресу пам'яті, де розміщено дані; - пошук за ключем чи встановлення факту, що шукані дані в списку відсутні; - зміна при додаванні в список нових даних і видаленні з нього непотрібних; - переповнення області, виділеної спискам чи підспискам, і одержання нової області. У разі застосування методу довідника чи таблиці вмісту список насамперед поділяють на підсписки. Потім формують таблицю вмісту, у якій для кожного підсписку заводять одну стаття, а для входу використовують ключ, за яким шукають статтю. Стаття направляє до підсписку – об-ласті розташування шуканих даних.

--Види довідників-- --множинний довідник-- Як сукупність додаткових довідників побудовано множинний довідник. Головний довідник відсилає до своєї частини – піддовідника, той у свою чергу – до підсписку, де можна знайти шукані дані. Адресу основної пам'яті можна визначити не тільки за допомогою довідника, але і спеціаль-ним перетворенням ключа. Відображаємо ключ на адресу елементу, з якого починається область розташування асоційованих даних. З цього елементу зазвичай рухаємося тільки в прямому на-прямку, хоча пошук допускає переміщення в обох напрямках залежно від ситуації, що склалася після перегляду даних. ==Спільний довідник == отримав таку назву в зв'язку з тим, що для кожного запису в довіднику передбачено одну статтю. Це спрощує пошук, особливо якщо записи мають змінну довжину та область списку розташовано на допоміжному носії, для якого послідовний пошук вимагає значних часових витрат. Стаття складається з двох частин: -ключа запису у файлі; -покажчика, що визначає місце розташування цього запису у зв'язному списку. Довідник забезпечує зв'язок 1:1, тобто для кожного запису файлу він містить одну статтю і кожна стаття від-повідає одному запису. Задавши ключ k, впродовж пошуку запису насамперед переглянемо довідник. Якщо у ньо-му відсутня стаття для ключа k, то відсутній і запис. Якщо запис існує, то знайдемо статтю, що міс-тить шуканий ключ і покажчик. Позиція запису у файлі зазвичай не відповідає позиції статті в дові-днику. По покажчику переходимо у зону, де має знаходитися шуканий запис. Перш ніж додати запис, треба перевірити її відсутність по довіднику. Для визначення віль-ного місця в списку використовують покажчик на вільну пам'ять. При видаленні у файлі варто лік-відувати запис, що там знаходиться. Якщо використано покажчик на вільну пам'ять, то немає по-треби видаляти запис зі списку, але зайнятий елемент стає недоступним. При наявності списку вільної пам'яті цей елемент можна повернути у список і повторно викоантати. Однак у будь-якому випадку треба поновити довідник. Існують два способи поновлення, кожний з яких стосується ви-далення в щільному упорядкованому списку, коли статті можна : -видалити переміщенням інших статей нагору з перекриттям статті, яку видаляють; -зберегти, але розмістивши замість ключа символ @, який показує, що запис недоступ-ний чи елемент порожній. Довідник поновлюється досить швидко, але стаття, що стосується ви-даленого запису, перевірятиметься в багатьох операціях пошуку. Довідник зазвичай щільний і упорядкований; це сприяє швидкому послідовному чи, що до-цільніше, бінарному пошуку. Не складає проблему збереження записів змінної довжини. Однак недолік такого «гроссбуху» – витрати часу на операції видалення і додавання записів у файл, оскільки треба реорганізовувати довідник. У разі значного обсягу змін доцільно використати сис-тему спільного довідника на основі зв'язного списку. Довідник на основі зв'язного списку змінювати простіше, але пошук у такому довіднику мо-жна проводити тільки послідовно. Файл довідника, побудований як бінарне дерево, забезпечує просту зміну і швидкий пошук. ==Єдиний довідник. ==Список, для якого треба утворити довідник зон звуження пошуку, чи довідник підсписків, має бути упорядкованим і щільним. Для файлу довідника підсписків (просто файл довідника) передбачено, що список (назвемо його А) поділено на n підсписків, можливо, різ-ної довжини. Для простоти нехай кожний з них містить однакове число елементів, тому: -розділимо упорядкований список L на певне число підсписків; -утворимо довідник D; -для кожного підсписку Li виділимо одну статтю довідника, що містить: а) точку, з якої варто починати перегляд у підсписку, – покажчик на підсписок Dip; б) ключ для встановлення діапазону записів у підсписку – ключ підсписку Dik. Для формування статті вибираємо: -за покажчик адресу першого запису підсписку; -ключ останнього запису підсписку. Це дає адресу, з якої варто почати перегляд, і діапазон ключів, оскільки ключ у попередній статті довідника задає нижня межа записів у даному підсписку, а ключ у даній статті – верхня ме-жа. Перший підсписок не має явної нижньої границі; тому для нижньої межі використовують най-менший можливий ключ. Критерій порівняння різновидів списку – сумарне число звертань до довідника і списку для знаходження потрібного запису чи з'ясування його відсутності. Для методу довідника це число в середньому визначити дуже просто, проглянувши половину: -довідника; -підсписку після його знаходження по довіднику. Порівняємо метод пошуку за допомогою довідника з двома іншими методами – бінарним і лінійним пошуками. Наприклад, розглянемо досить великий за розміром список, що складається з 10000 записів (N=10000), і припустимо його поділ на 100 підсписків по 100 записів у кожному (n = 100). Одержимо такі результати: -лінійний пошук вимагає N/2 = 5000 звертань; -пошук з використанням довідника вимагає n/2+n/2=100 звертань; -бінарний пошук вимагає близько log2(N-1)= 13 звертань. Тобто для обраних параметрів метод довідника поступається бінарному пошуку, якщо не зважати на необхідні обчислення. Оцінимо оптимальний розмір підсписку. Нехай список містить N записів, а кожен підсписок – Х записів; тоді в довіднику міститься N/X статей.

Число звертань ви-значається як  L=1/2(N/X+X) . Оптимальне значення Х знайдемо, диференціюючи цей вираз по Х, 

прирівнявши його до нуля і помноживши на 2Х^2. Зрештою отримаємо X=sqrt(N) . Отже, найкращий розподіл досягнуто у разі рівності sqrt(N) числа підсписків і числа елементів у кожному підсписку. Ця ситуація показана в наведеному вище прикладі з 10000 записами. ==Дворівневий довідник.== Для простого довідника sqrt(N) визначає оптимальне число елемен-тів підсписку. Іншим варіантом є збереження підсписків невеликого розміру і збільшення розміру довідника. Замість безпосереднього використання довідника для прискорення пошуку розділимо початковий довідник на піддовідники й одержимо: -головний довідник, що вказує на один чи кілька піддовідників; -піддовідник, що вказує на один чи кілька підпідсписків (частин підсписку); -статтю головного довідника, що відповідає одному підсписку, який складається з декіль-кох підпідсписків. Оптимальний розмір підсписку sqrt(N) мають довідник, піддовідник і підпідсписок. Якщо роз-мір кожного з них дорівнює n, то середнє число звертань при пошуку залишиться тим самим.

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

-зменшується сумарне число записів, що переглядаються; -збільшується обсяг пам'яті, зайнятої довідником. Важливо визначити, як одержати найбільший ефект – мінімальне число звертань при най-меншому обсязі пам'яті довідника. З чого складається «золота середина»? Так, для довідника з чотирма рівнями перша частина статті довідника є ключем останньо-го запису підсписку, на який посилається ця стаття. Частина статті, що містить покажчик, указує на піддовідник на наступному нижньому рівні. Цей піддовідник служить для підпідсписків, що склада-ють даний список. Існує п'ять піддовідників 2-го рівня, кожний з який складається з п'яти статей, що вказують на підпіддовідники 3-го рівня. На 3-му рівні маємо 25 підпіддовідників; кожний з них стосується підпідсписку. Процедура знаходження запису полягає в наступному. -У довіднику шукаємо покажчик на піддовідник. -У піддовіднику шукаємо покажчик на підпіддовідник. -У підпіддовіднику шукаємо покажчик на підпідпіддовідник. -У підпідпіддовілнику шукаємо покажчик на підсписок найнижчого рівня. -Шукаємо у цьому підсписку. На кожному з кроків проглядаємо максимум п'ять елементів. Оцінимо виграш від збіль-шення числа довідників. Для порівняння табл. 29 містить дані для довідників розміром 10000, а табл.30 – 1000000. Пам'ять для розміщення довідника зростає, але за обсягом вона і близько не підходить до розміру файлу, оскільки стаття довідника набагато менша за запис. Дворівневий довідник зменшує число звертань з 100 до 32 у випадку 10000 записів і з 1000 до 150 у випадку мільйона записів. Але в обох випадках спостерігаємо значне підвищення продук-тивності. Проте, якщо перейти до трьох рівнів, поліпшення буде порівняно невеликим, а обсяг за-йнятої пам'яті значно зросте.

Назвіть методи звуження зони пошуку у зв’язних списках?

28) Назвіть методи звуження зони пошуку у зв’язних списках? 3.4 Довідники Звуження зони пошуку як термін введено для групи методів, здатних одразу вийти на звужену зону пошуку та обмежити її наступну обробку. При послідовному пошуку аналізують кожен елемент списку в порядку їхнього розташування в основній пам'яті. Пошук у зв'язному списку ви-значено порядком з'єднання елементів. В упорядкованому списку пошук може завершитися до перевірки всіх елементів. Крім очевидної переваги, недоліки цих методів – необхідність продовження пошуку і скла-дніший, чим у зв'язному списку, процес додавання і видалення даних. Для звуження зони пошуку треба вирішити ті ж задачі, що і для збалансованих бінарних дерев пошуку і В-дерев: - перетворення шуканого значення ключа на адресу пам'яті, де розміщено дані; - пошук за ключем чи встановлення факту, що шукані дані в списку відсутні; - зміна при додаванні в список нових даних і видаленні з нього непотрібних; - переповнення області, виділеної спискам чи підспискам, і одержання нової області. У разі застосування методу довідника чи таблиці вмісту список насамперед поділяють на підсписки. Потім формують таблицю вмісту, у якій для кожного підсписку заводять одну стаття, а для входу використовують ключ, за яким шукають статтю. Стаття направляє до підсписку – об-ласті розташування шуканих даних.

--Види довідників--

--множинний довідник-- Як сукупність додаткових довідників побудовано множинний довідник. Головний довідник відсилає до своєї частини – піддовідника, той у свою чергу – до підсписку, де можна знайти шукані дані. Адресу основної пам'яті можна визначити не тільки за допомогою довідника, але і спеціаль-ним перетворенням ключа. Відображаємо ключ на адресу елементу, з якого починається область розташування асоційованих даних. З цього елементу зазвичай рухаємося тільки в прямому на-прямку, хоча пошук допускає переміщення в обох напрямках залежно від ситуації, що склалася після перегляду даних. --Спільний довідник -- отримав таку назву в зв'язку з тим, що для кожного запису в довіднику передбачено одну статтю. Це спрощує пошук, особливо якщо записи мають змінну довжину та область списку розташовано на допоміжному носії, для якого послідовний пошук вимагає значних часових витрат. Стаття складається з двох частин: -ключа запису у файлі; -покажчика, що визначає місце розташування цього запису у зв'язному списку. Довідник забезпечує зв'язок 1:1, тобто для кожного запису файлу він містить одну статтю і кожна стаття від-повідає одному запису. Задавши ключ k, впродовж пошуку запису насамперед переглянемо довідник. Якщо у ньо-му відсутня стаття для ключа k, то відсутній і запис. Якщо запис існує, то знайдемо статтю, що міс-тить шуканий ключ і покажчик. Позиція запису у файлі зазвичай не відповідає позиції статті в дові-днику. По покажчику переходимо у зону, де має знаходитися шуканий запис. Перш ніж додати запис, треба перевірити її відсутність по довіднику. Для визначення віль-ного місця в списку використовують покажчик на вільну пам'ять. При видаленні у файлі варто лік-відувати запис, що там знаходиться. Якщо використано покажчик на вільну пам'ять, то немає по-треби видаляти запис зі списку, але зайнятий елемент стає недоступним. При наявності списку вільної пам'яті цей елемент можна повернути у список і повторно викоантати. Однак у будь-якому випадку треба поновити довідник. Існують два способи поновлення, кожний з яких стосується ви-далення в щільному упорядкованому списку, коли статті можна : -видалити переміщенням інших статей нагору з перекриттям статті, яку видаляють; -зберегти, але розмістивши замість ключа символ @, який показує, що запис недоступ-ний чи елемент порожній. Довідник поновлюється досить швидко, але стаття, що стосується ви-даленого запису, перевірятиметься в багатьох операціях пошуку. Довідник зазвичай щільний і упорядкований; це сприяє швидкому послідовному чи, що до-цільніше, бінарному пошуку. Не складає проблему збереження записів змінної довжини. Однак недолік такого «гроссбуху» – витрати часу на операції видалення і додавання записів у файл, оскільки треба реорганізовувати довідник. У разі значного обсягу змін доцільно використати сис-тему спільного довідника на основі зв'язного списку. Довідник на основі зв'язного списку змінювати простіше, але пошук у такому довіднику мо-жна проводити тільки послідовно. Файл довідника, побудований як бінарне дерево, забезпечує просту зміну і швидкий пошук. --Єдиний довідник. --

Список, для якого треба утворити довідник зон звуження пошуку, чи довідник підсписків, має бути упорядкованим і щільним. Для файлу довідника підсписків (просто файл довідника) передбачено, що список (назвемо його А) поділено на n підсписків, можливо, різ-ної довжини. Для простоти нехай кожний з них містить однакове число елементів, тому: -розділимо упорядкований список L на певне число підсписків; -утворимо довідник D; -для кожного підсписку Li виділимо одну статтю довідника, що містить: а) точку, з якої варто починати перегляд у підсписку, – покажчик на підсписок Dip; б) ключ для встановлення діапазону записів у підсписку – ключ підсписку Dik. Для формування статті вибираємо: -за покажчик адресу першого запису підсписку; -ключ останнього запису підсписку. Це дає адресу, з якої варто почати перегляд, і діапазон ключів, оскільки ключ у попередній статті довідника задає нижня межа записів у даному підсписку, а ключ у даній статті – верхня ме-жа. Перший підсписок не має явної нижньої границі; тому для нижньої межі використовують най-менший можливий ключ. Критерій порівняння різновидів списку – сумарне число звертань до довідника і списку для знаходження потрібного запису чи з'ясування його відсутності. Для методу довідника це число в середньому визначити дуже просто, проглянувши половину: -довідника; -підсписку після його знаходження по довіднику. Порівняємо метод пошуку за допомогою довідника з двома іншими методами – бінарним і лінійним пошуками. Наприклад, розглянемо досить великий за розміром список, що складається з 10000 записів (N=10000), і припустимо його поділ на 100 підсписків по 100 записів у кожному (n = 100). Одержимо такі результати: -лінійний пошук вимагає N/2 = 5000 звертань; -пошук з використанням довідника вимагає n/2+n/2=100 звертань; -бінарний пошук вимагає близько log2(N-1)= 13 звертань. Тобто для обраних параметрів метод довідника поступається бінарному пошуку, якщо не зважати на необхідні обчислення. Оцінимо оптимальний розмір підсписку. Нехай список містить N записів, а кожен підсписок – Х записів; тоді в довіднику міститься N/X статей.

Число звертань ви-значається як  L=1/2(N/X+X) . Оптимальне значення Х знайдемо, диференціюючи цей вираз по Х, 

прирівнявши його до нуля і помноживши на 2Х^2. Зрештою отримаємо X=sqrt(N) . Отже, найкращий розподіл досягнуто у разі рівності sqrt(N) числа підсписків і числа елементів у кожному підсписку. Ця ситуація показана в наведеному вище прикладі з 10000 записами.

--Дворівневий довідник.-- Для простого довідника sqrt(N) визначає оптимальне число елемен-тів підсписку. Іншим варіантом є збереження підсписків невеликого розміру і збільшення розміру довідника. Замість безпосереднього використання довідника для прискорення пошуку розділимо початковий довідник на піддовідники й одержимо:

-головний довідник, що вказує на один чи кілька піддовідників; -піддовідник, що вказує на один чи кілька підпідсписків (частин підсписку); -статтю головного довідника, що відповідає одному підсписку, який складається з декіль-кох підпідсписків. Оптимальний розмір підсписку sqrt(N) мають довідник, піддовідник і підпідсписок. Якщо роз-мір кожного з них дорівнює n, то середнє число звертань при пошуку залишиться тим самим.

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

-зменшується сумарне число записів, що переглядаються; -збільшується обсяг пам'яті, зайнятої довідником. Важливо визначити, як одержати найбільший ефект – мінімальне число звертань при най-меншому обсязі пам'яті довідника. З чого складається «золота середина»? Так, для довідника з чотирма рівнями перша частина статті довідника є ключем останньо-го запису підсписку, на який посилається ця стаття. Частина статті, що містить покажчик, указує на піддовідник на наступному нижньому рівні. Цей піддовідник служить для підпідсписків, що склада-ють даний список. Існує п'ять піддовідників 2-го рівня, кожний з який складається з п'яти статей, що вказують на підпіддовідники 3-го рівня. На 3-му рівні маємо 25 підпіддовідників; кожний з них стосується підпідсписку. Процедура знаходження запису полягає в наступному. -У довіднику шукаємо покажчик на піддовідник. -У піддовіднику шукаємо покажчик на підпіддовідник. -У підпіддовіднику шукаємо покажчик на підпідпіддовідник. -У підпідпіддовілнику шукаємо покажчик на підсписок найнижчого рівня. -Шукаємо у цьому підсписку. На кожному з кроків проглядаємо максимум п'ять елементів. Оцінимо виграш від збіль-шення числа довідників. Для порівняння табл. 29 містить дані для довідників розміром 10000, а табл.30 – 1000000. Пам'ять для розміщення довідника зростає, але за обсягом вона і близько не підходить до розміру файлу, оскільки стаття довідника набагато менша за запис. Дворівневий довідник зменшує число звертань з 100 до 32 у випадку 10000 записів і з 1000 до 150 у випадку мільйона записів. Але в обох випадках спостерігаємо значне підвищення продук-тивності. Проте, якщо перейти до трьох рівнів, поліпшення буде порівняно невеликим, а обсяг за-йнятої пам'яті значно зросте.

Оптимальний розмір підсписку довідника

29) Оптимальний розмір підсписку довідника --Єдиний довідник. --Список, для якого треба утворити довідник зон звуження пошуку, чи довідник підсписків, має бути упорядкованим і щільним. Для файлу довідника підсписків (просто файл довідника) передбачено, що список (назвемо його А) поділено на n підсписків, можливо, різ-ної довжини. Для простоти нехай кожний з них містить однакове число елементів, тому: -розділимо упорядкований список L на певне число підсписків; -утворимо довідник D; -для кожного підсписку Li виділимо одну статтю довідника, що містить: а) точку, з якої варто починати перегляд у підсписку, – покажчик на підсписок Dip; б) ключ для встановлення діапазону записів у підсписку – ключ підсписку Dik. Для формування статті вибираємо: -за покажчик адресу першого запису підсписку; -ключ останнього запису підсписку. Це дає адресу, з якої варто почати перегляд, і діапазон ключів, оскільки ключ у попередній статті довідника задає нижня межа записів у даному підсписку, а ключ у даній статті – верхня ме-жа. Перший підсписок не має явної нижньої границі; тому для нижньої межі використовують най-менший можливий ключ. Критерій порівняння різновидів списку – сумарне число звертань до довідника і списку для знаходження потрібного запису чи з'ясування його відсутності. Для методу довідника це число в середньому визначити дуже просто, проглянувши половину: -довідника; -підсписку після його знаходження по довіднику. Порівняємо метод пошуку за допомогою довідника з двома іншими методами – бінарним і лінійним пошуками. Наприклад, розглянемо досить великий за розміром список, що складається з 10000 записів (N=10000), і припустимо його поділ на 100 підсписків по 100 записів у кожному (n = 100). Одержимо такі результати: -лінійний пошук вимагає N/2 = 5000 звертань; -пошук з використанням довідника вимагає n/2+n/2=100 звертань; -бінарний пошук вимагає близько log2(N-1)= 13 звертань. Тобто для обраних параметрів метод довідника поступається бінарному пошуку, якщо не зважати на необхідні обчислення. Оцінимо оптимальний розмір підсписку. Нехай список містить N записів, а кожен підсписок – Х записів; тоді в довіднику міститься N/X статей.

Число звертань ви-значається як  L=1/2(N/X+X) . Оптимальне значення Х знайдемо, диференціюючи цей вираз по Х, 

прирівнявши його до нуля і помноживши на 2Х^2. Зрештою отримаємо X=sqrt(N) . Отже, найкращий розподіл досягнуто у разі рівності sqrt(N) числа підсписків і числа елементів у кожному підсписку. Ця ситуація показана в наведеному вище прикладі з 10000 записами.

Як побудовано множинний довідник?

30) Як побудовано множинний довідник? Як сукупність додаткових довідників побудовано множинний довідник. Головний довідник відсилає до своєї частини – піддовідника, той у свою чергу – до підсписку, де можна знайти шукані дані. Адресу основної пам'яті можна визначити не тільки за допомогою довідника, але і спеціаль-ним перетворенням ключа. Відображаємо ключ на адресу елементу, з якого починається область розташування асоційованих даних. З цього елементу зазвичай рухаємося тільки в прямому на-прямку, хоча пошук допускає переміщення в обох напрямках залежно від ситуації, що склалася після перегляду даних.