В-дерева та індексація БД

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

Основна причина застосування будь-якого індексу полягає в тому, що він дозволяє виключити необхідність у фізичному послідовному перегляді індексованого файлу Але фізичний послідовний перегляд все ще потрібно виконувати в індексі Якщо індексований файл стає дуже великим, то і сам індекс може придбати досить значні розміри, тому послідовний перегляд навіть тільки одного індексу може зажадати досить тривалого часу Вирішення цієї проблеми є таким же, як і колись – індекс розглядається просто як звичайний файл і на ньому формується другий індекс (індекс на індексі) Ця ідея може бути здійснена на будь-якому необхідній кількості рівнів (на практиці найчастіше застосовується три рівня для того щоб файлу потурбувалися більше трьох рівнів індексації, він дійсно повинен стати дуже великим) Кожен рівень індексу діє в якості нещільного індексу для нище рівня (зрозуміло, він обовязково повинен бути нещільним, тому що в противному випадку використання ще одного рівня не дозволило б домогтися якихось переваг – на рівні п знаходилося б така ж кількість елементів, як і на рівні n +1, і тому перегляд індексу більш високого рівня займав би такий же час, як і перегляд попереднього)

Тепер перейдемо до опису В-дерев Будь-яке В-дерево являє собою один з конкретних типів деревовидного індексу В-дерева як такі були вперше запропоновані Байєром (Bayer) і Маккрейтом (McCreight) в 1972 році [Г16] З того часу було проаналізовано безліч варіантів однієї і тієї ж основної ідеї, як самим Байєром, так і багатьма іншими дослідниками як вже було сказано, В-дерева того чи іншого типу в даний час, імовірно, складають найбільш широко застосовувану структуру зберігання у всіх сучасних системах баз даних Нижче описаний варіант, який розглядається в роботі Кнута (Knuth) [Г 1] До речі, слід зазначити, що структура індексу в методі віртуального доступу до памяті (Virtual Storage Access Method – VSAM) компанії IBM [Г 18] вельми нагадує структуру Кнута проте, версія VSAM була розроблена незалежно і включає власні додаткові засоби, такі як використання методів стиснення Насправді, варіант, що передує структурі VSAM, був описаний ще в 1969 році [Г 19]

У варіанті Кнута, описаному нижче, індекс складається з двох частин (для позначення яких використовується термінологія VSAM) – послідовного набору (Sequence set) і індексного набору (index set)

■&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Послідовний набір являє собою однорівневий індекс до фактичних даних цей індекс зазвичай є щільним, але може бути і нещільним, якщо індексований файл кластеризувати по індексуватися полю Елементи цього індексу (безумовно) сгруппі рова в сторінки, а сторінки (безумовно) зєднані ланцюжками покажчиків таким чином, що логічне впорядкування, представлене індексом, можна відновити, зчитуючи записи у фізичній послідовності на першій сторінці в ланцюжку, потім – записи у фізичній послідовності на другій сторінці в ланцюжку і тд Таким чином, послідовний набір забезпечує швидкий послідовний доступ до індексованих даними

■&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp Індексний набір, в свою чергу, дає можливість отримати швидкий прямий доступ до після довательности набору (і таким чином також і до самих даних) Індексний набір фактично являє собою деревовидний індекс до послідовного набору в дійсності, строго кажучи, справжнім В-деревом є саме індексний набір Комбінація індекс ного набору і послідовного набору іноді іменується В *-деревом. Верхній рівень індексного набору складається з єдиного вузла (тобто з однієї сторінки, але, безумовно, що містить багато елементів індексу, як і всі інші вузли) Верхній вузол індексу називається коренем

На рис Г 13 наведено простий приклад Цей малюнок можна пояснити наступним чином Насамперед, значення 6, 8, 12, .., 97, 99 – це значення індексованого поля, скажімо, F Розглянемо верхній вузол, який складається з двох значень F (50 і 82) і трьох покажчиків (фактично номерів сторінок) Записи даних зі значенням F, меншим або рівним 50, можна знайти (зрештою), переслідував по лівому вказівником з цього вузла, аналогічним чином, записи зі значенням F, більшим ніж 50 і меншим або рівним 82, можна знайти, слідуючи за середнім вказівником, а записи зі значенням F, більшим ніж 82, можна отримати, слідуючи по правому покажчику Інші вузли в цьому індексному наборі інтерпретуються аналогічним чином зверніть увагу на те, що (наприклад), перейшовши по правому вказівником з першого вузла на другий вузол, можна отримати всі записи зі значенням F, більшим ніж 32, а також меншим або рівним 50 (в силу того факту, що ми вже перейшли по лівому вказівником з вузла більш високого рівня)

Проте, В-дерево (тобто індексний набір), показане на рис Г 13, не зовсім реалістично за описаними нижче причин

■ По-перше, всі вузли В-дерева зазвичай не містять однакову кількість значень даних

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

Взагалі кажучи, будь-яке В-дерево порядку п має не менше п і не більше 2п значень даних в будь-якому конкретному вузлі (і якщо у вузлі знаходиться до значень даних, то мається також до +1 покажчик) Жодне значення даних не зустрічається в дереві більше одного разу Нижче наведено алгоритм пошуку конкретного значення V в структурі, що на рис Г13 (див стор 1334) алгоритм для В *-дерева загального види порядку п являє собою просто узагальнення даного алгоритму

set N to the root node

do until N is a sequence-set node

let X, Y (X &lt Y) be the data values in node N

if V &lt X    then set N to the left  lower node of N if X &lt V &lt Y then set N to the middle lower node of N if V &gt Y    then set N to the right  lower node of N

end

if V occurs in node N then exit / * знайдено * / if V does

not occur in node N then exit / * не знайдено * /

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

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

На відміну від цього, чудовим перевагою В-дерев є те, що алгоритми вставки і видалення гарантують, що дерево завжди залишається збалансованим (З цієї причини іноді доводиться чути, що абревіатура В в терміні В-дерево позначає balanced – Збалансований) Нижче коротко розглядається процедура вставки нового значення, скажімо, V, у В-дерево порядку п У вживаному при цьому алгоритмі розглядається тільки індексний набір, оскільки (як було описано вище) власне В-деревом є саме індексний набір щоб поширити дія цього алгоритму також на послідовний набір, потрібно лише найпростіше додаток

■ Спочатку виконується алгоритм пошуку для виявлення не вузла послідовного набору, а того вузла (скажімо, N) на самому нижньому рівні індексного набору, до якого логічно відноситься значення V Якщо вузол N містить вільний простір, то значення V вставляється в N і процес завершується

■ В іншому випадку вузол N (який таким чином містить 2п значень) розділяється на два вузла, N1 і N2 Припустимо, що S – ряд первинних 2п значень поряд з новим значенням V в їх логічній послідовності Найменші п значень з ряду S поміщаються в лівий вузол, N1, найбільші п значень з ряду S поміщаються в правий вузол, N2, а середнє значення, скажімо, W, просувається в батьківський вузол вузла N, скажімо, Р, для використання в якості розділового значення для вузлів N1 і N2 Надалі при пошуку значення і цей пошук після досягнення вузла Р буде направлений у вузол N1, якщо U < W, і в вузол N2, якщо і> W

■ Тепер робиться спроба вставити значення W в вузол Р і описаний процес повто ряется

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

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

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*