Копитко М.Ф. Основи інформаційних технологій (на укр. языке)

Подождите немного. Документ загружается.

словами, оскільки блок уміщає тільки два записи, то середній

рівень заповнення сегментів не повинен перевищувати 85% від

місткості блока.

16.8. Вставка записів у лінійну геш-таблицю

За необхідності вставки в геш-таблицю нового запису для

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

алгоритм, розглянутий у пункті 16.7. Спочатку для заданого

значення К ключа пошуку запису обчислюють геш-функцію h(K), і

як шуканий номер m сегмента використовують і молодших бітів

послідовності h(K). Якщо m<n, то запис заноситься у сегмент m;

якщо ж m≥n, то запис розташовується у сегменті m-2

i-1

. Якщо в

обраному сегменті немає вільного місця, то створюється блок

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

Під час виконання кожної операції вставки значення співвідно-

шення r/n аналізують з урахуванням кількості r записів, яка зросла.

Якщо співвідношення стає надто великим, то в таблицю додається

новий сегмент. Зауважимо, що сегмент, який додається, не має

відношення до того, в який вставляється черговий запис. Якщо

бінарним представленням номера доданого сегмента є послідов-

ність 1а

...а

, то розділяється сегмент 0а

...а

. Записи заносяться в

один із двох отриманих сегментів залежно від значення бітів а

Зазначимо, що всі ці записи повинні мати геш-коди, які

завершуються послідовністю а

...а

і,

і розглядатиметься тільки

значення і-го біта з правого боку.

Ще один важливий аспект стосується ситуації, коли значення n

перевищує 2

. У цьому випадку біжучий вміст і збільшується на

одиницю і на початку бітового представлення номера кожного

сегмента заноситься додатковий 0. Насправді нічого не змінюється,

оскільки бітові послідовності, які інтерпретуються як цілі десяткові

числа, залишаються попередніми.

Приклад 70. Продовжимо розгляд структури, представленої на

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

що гешується у бітову послідовність 0101. Оскільки останнім бітом

є 1, то запис необхідно розташувати у другому (нижньому)

сегменті. Сегмент має достатньо вільного простору, отож блок

переповнення не створюється.

191

Тепер, отже, 4 записи розташовано у 2-х сегментах, тобто задане

відношення 1,7 перевищене, і ми зобов’язані збільшити значення n

до 3-х. Оскільки

⎡

⎤

,23log

то номерами сегментів замість 0 і 1

стають значення 00 і 01, проте структура даних залишається

попередньою. Таблиця доповнюється новим сегментом з номером

10. Потім сегмент з номером 00 (який відрізняється від номера

щойно створеного сегмента лише одним бітом) розділяється. У

цьому випадку запис з геш-кодом 0000 залишається в сегменті 00

(геш-код завершується бітами 00), а запис з геш-кодом 1010,

аналогічно, переноситься в сегмент 10. Результат наведено на

рис. 74.

0000

0101

1111

i =2

r = 4

1010

Рис. 74. Результат вставки запису з геш-кодом 0101 і долучення

сегмента в лінійну таблицю, проілюстровану на рис. 73

Розглянемо тепер операцію вставки запису з геш-кодом 0001.

Два останніх біти коду – це 01, отож запис підлягає розміщенню в

існуючий сегмент з номером 01. На жаль, сегмент вже заповнено, і

до нього приєднується блок переповнення. Три записи

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

порядку слідування їхніх геш-кодів (вибір певного порядку не дуже

192

важливий). Оскільки відношення кількості записів до числа

сегментів таблиці зараз дорівнює 5/3, тобто є меншим від 1,7, то

новий сегмент не створюватимемо. Результат відображено на

рис. 75.

Опишемо послідовність дій, необхідних для вставки запису з

ключем, гешованим в 0111. Останні два біти геш-коду, 11,

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

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

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

займає вільне місце у блоці переповнення сегмента 01.

0000

0001

0101

1010

1111

Рис. 75. Результат вставки запису з геш-кодом 0001 і долучення блока

переповнення в геш-таблицю, проілюстровану на рис. 74

Однак тепер відношення кількості записів до числа сегментів

геш-таблиці вже перевищує поріг 1,7, отож необхідно створити

новий сегмент з черговим номером, 11. Так сталось, що це якраз

той сегмент, в який потрібно було помістити новий запис. Записи з

геш-кодами 0001 і 0101, які належать сегменту 01, залишаються на

місці, а два інші (0111 і 1111) переносяться в новий сегмент.

Оскільки сегмент 01 тепер містить тільки два записи, то блок пере-

повнення є зайвим і видаляється. Остаточну структуру представ-

лено на рис. 76.

193

Зауважимо, що чергова можлива операція вставки запису в геш-

таблицю на рис. 76 спричинить до перевищення порогу 1,7, отож

необхідно збільшити значення n та і до 5 і 3, відповідно.

0001

010

0000

i = 2

r = 6

n = 4

1010

0111

1111

Рис. 76. Результат вставки запису з геш-кодом 0111 і долучення сегмента в геш-

таблицю, проілюстровану на рис. 75

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

відповідно до описаної вище процедури, яку використовують при

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

ся. Якщо шуканого запису в обраному сегменті немає, то його

немає ніде. Щоб проілюструвати сказане, звернемось до структури

геш-таблиці, наведеної на рис. 74, де і=2 і n=3. Спочатку

намагатимемось знайти запис з ключем, гешованим у бітову

послідовність 1010. Оскільки і=2, то звернемо увагу на два

останніх біти геш-коду запису – 10. Якщо їх інтерпретувати як ціле

десяткове число, то це означатиме m = 2. Оскільки m<n, то

194

сегмент 10 існує і за записом необхідно звернутися саме до нього.

Зверніть увагу, що факт відшукання запису з геш-кодом 1010 ще не

означає, що це шуканий запис. Для впевненості необхідно

перевірити повне значення ключа запису.

Тепер розглянемо процес пошуку запису з геш-кодом 1011.

Цього разу необхідно звернутися до сегмента з номером 11.

Оскільки значення 11, потрактоване як ціле десяткове число, є

m=3, то маємо m≥n, а це означає, що сегмента 11 у таблиці немає.

Замінимо початкову одиницю номера на нуль і перейдемо до

сегмента 01. Однак у цьому сегменті немає запису з геш-кодом

1011, і ми можемо бути впевнені, що його немає і в усій таблиці.

Вправи для опрацювання

Вправа 51. Поясніть, як вплинуть на вміст сегментів геш-таблиці,

наведеної на рис. 67, перелічені нижче операції вставки і заміни

записів із заданими ключами:

а) записи g-j вставляються у сегменти 0-3, відповідно;

б) записи a і b видаляються;

в) записи k-n вставляються у сегменти 0-3, відповідно;

г) записи c і d видаляються.

Вправа 52. Припустимо, що ключі записів гешуються в 4-бітові

послідовності (як у всіх прикладах з розширеним і лінійним гешу-

ванням, розглянутих вище). Вважатимемо, що блоки володіють

місткістю, достатньою для зберігання трьох (а не двох, як раніше)

записів, і розглянемо геш-таблицю з двома порожніми блоками (з

номерами 0 і 1). Як виглядатиме структура після вставки записів з

наступними геш-кодами:

а) 0000, 0001, ..., 1111; геш-таблиця, що розширюється;

б) 0000, 0001, ..., 1111; геш-таблиця є лінійною з

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

числа сегментів, яке дорівнює 100%;

в) 1111, 1110, ..., 0000; геш-таблиця, що розширюється;

195

г) 1111, 1110, ..., 0000; геш-таблиця є лінійною з

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

числа сегментів, яке дорівнює 75%.

Вправа 53. Нехай існує файл даних з 1 000 000 записів, які необхід-

но гешувати в таблицю з 1 000 сегментів. Один блок може вмістити

100 записів. Необхідно підтримувати настільки високий рівень

заповнення блоків, наскільки це можливо, враховуючи, що блоки

не повинні використовуватися спільно декількома сегментами.

Якої кількості блоків (мінімальної і максимальної) достатньо для

зберігання зазначеної структури?

196

ІНДЕКСИ ДЛЯ БАГАТОВИМІРНИХ ДАНИХ

Усі структури, які розглянуто раніше, є одновимірними, тобто

мають єдиний ключ пошуку і дають змогу знаходити записи даних,

що задовольняють значенням цього ключа. До цього часу ми

вважали, що функцію ключа пошуку виконує окремий атрибут або

поле. До категорії одновимірних можуть належати і такі індекси,

ключ пошуку яких утворюється на основі декількох полів. Якщо

необхідний одновимірний індекс з ключем пошуку, сформованим

зі списку полів (F

, F

,…, F

), то вміст ключа можна представляти

у вигляді ланцюга зв’язаних разом значень полів F

, F

і т.д.,

розділених спеціальними символами.

Приклад 72. Якщо поле F

належить до рядкового типу, а поле

– до цілочислового і роздільником слугує символ #, який у

цьому випадку заборонено використовувати в середині рядкових

значень, то комбінацію величин F

=‘abcd’ і F

=123 можна

оформити як рядок ‘abcd#123’.

У попередньому розділі ми зазначили переваги одновимірного

простору значень ключа пошуку.

• Ефективність В-дерев та індексів для послідовних файлів

зумовлена тим, що ключові значення розташовано

упорядковано.

• Пошук у геш-таблиці стає можливим тільки в тому

випадку, якщо значення ключа пошуку достовірно

відоме. Якщо ключ утворено з декількох полів і вміст

одного з них не визначено, то геш-функцію застосову-

вати не вдається – замість цього необхідно переглянути

вміст всіх сегментів таблиці.

Існує чимало застосувань, які вимагають, щоб дані трактувались

у контексті 2-, 3- або навіть n-вимірних просторів. Деякі з таких

застосувань підтримуються традиційними СКБД, однак розроблено

спеціалізовані системи, орієнтовані на обслуговування застосувань,

що взаємодіють з багатовимірними даними. Одна з головних

особливостей подібних систем стосується підтримки ними таких

структур даних, які передбачають обробку деяких різновидностей

запитів, що не є типовими для традиційних застосувань SQL. У

197

темі 17 представлено деякі зразки запитів, ефективність обслугову-

вання яких суттєво зростає за використання індексів для багатови-

мірних даних. Теми 18 і 19 присвячено обговоренню характеристик

перелічених нижче структур даних.

1. Сіткові файли (grid files) – багатовимірна версія геш-

таблиць.

2. Роздільні геш-функції (partitioned hash functions) –

альтернативний спосіб реалізації механізму геш-таблиць у

застосуванні до багатовимірних даних.

3. Індекси з декількома ключами (multiple-key indexes) –

структури, в яких індексні значення одного ключа пов’язані

зі значеннями ключа індексів наступного рівня і т.д.

4. kd-дерева (kd-trees) – узагальнені моделі В-дерева у

застосуванні до множин точок.

5. Дерева квадрантів (quad trees) − дерева, кожна дочірня

вершина яких представляє один із квадрантів площі, що

описується батьківською вершиною.

6. R-дерева (R-trees) – узагальнення моделі В-дерева для

представлення множин областей простору.

Тема 17. Застосування моделі багатовимірних даних

У цій темі розглянемо два класи застосувань, які реалізують

модель багатовимірних даних. Один стосується географічних

інформаційних систем, де елементи даних описують сутності

двовимірного (інколи тривимірного) світу. У застосуваннях друго-

го класу поняття виміру трактується дещо абстрактно: кожен

атрибут відношення можна інтерпретувати як деякий вимір; тоді

кортежі доцільно сприймати як певні точки у просторі, обмеже-

ному атрибутами-вимірами.

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

них індексів, таких як В-дерева, для підтримки запитів до

багатовимірних даних. У деяких випадках подібний підхід доціль-

ний і ефективний, хоча в інших значно розумніше використовувати

певні структури спеціального призначення.

198

17.1. Географічні інформаційні системи

Типова географічна інформаційна система має справу з

об’єктами двовимірного (рідше – тривимірного) простору. Часто в

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

інформація, яка описує положення і взаємну орієнтацію споруд,

доріг, мостів, трубопроводів і багатьох інших фізичних об’єктів.

Приклад подібної карти наведено на рис. 77.

Рис. 77. Декілька об’єктів двовимірного простору

Існує чимало інших областей застосування подібних систем.

Наприклад, монтаж інтегральної схеми виглядає як набір

двовимірних карт прямокутних областей, виконаних зі спеціальних

матеріалів і організованих у формі «шарів». Вікна і піктограми на

екрані комп’ютера також можна трактувати як об’єкти двовимір-

ного простору.

199

Запити, які обслуговуються географічними інформаційними

системами, не належать до традиційної сфери використання SQL,

хоча за певних умов їх все-таки вдається записати операторами

SQL. Нижче перелічено деякі з різновидів подібних запитів.

1. Запити до даних зі збіганням окремих координат: задаються

значення координат одного або декількох вимірів і

повертається інформація про всі точки простору даних, які

задовольняють критерію пошуку.

2. Запити в діапазонах значень: задаються діапазони значень

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

точки, координати яких належать до цих діапазонів

(прикладом може бути запит, який передбачає відшукання

усіх двовимірних геометричних фігур, що частково або

цілковито належать зазначеним областям площини). Подібні

запити є узагальненням моделі одновимірних запитів у

діапазонах значень, про яку ми розповідали у пункті 15.4.

3. Пошук найближчих сусідніх об’єктів. Наприклад, згадаємо

запит, який передбачає виявлення точки, найближчої до

заданої. Якщо точки представляють міста, то одним із

подібних запитів може бути такий: знайти місто з

населенням, що перевищує задану межу чисельності, яке

найближче до вказаного міста.

4. Визначення місцезнаходження об’єкта: задається точка і

вимагаються відомості про приналежність точки до тих чи

інших фігур, областей чи об’єктів. Характерним прикладом

може бути задача визначення положення курсора щодо

екранних об’єктів у момент натискання клавіші миші.

17.2. Куби даних

Одне з недавніх досягнень в області технологій баз даних, яке

реалізоване в деяких комерційних СКБД, стосується підтримки

моделі кубів даних, де інформація інтерпретується у контексті

багатовимірного простору. Багато корпорацій зайняті збиранням

багатовимірних даних, які використовують у застосуваннях під-

тримки прийняття рішень, що дає змогу, наприклад, проаналізу-

вати показники господарської діяльності підприємства на основі

200