НОУ ІНТУІТ, Лекція, Фізичні моделі баз даних
Файли з нещільним індексом, або індексно-послідовні файли
Спробуємо вдосконалити спосіб зберігання файлу: зберігатимемо його в упорядкованому вигляді та застосуємо алгоритм двійкового пошуку для доступу до довільного запису. Тоді час доступу до довільного запису буде значно меншим. Для нашого прикладу це буде:
T = log2KBO = log212500 = 14 звернень до диска.
І це значно менше, ніж 12 500 звернень при довільному зберіганні записів файла. Однак і підтримка основного файлу в упорядкованому вигляді також складна операція.
Нещільний індекс будується саме для впорядкованих файлів. Для цих файлів використовується принцип внутрішнього впорядкування для зменшення кількості індексів, що зберігаються. Структура запису індексу для таких файлів має такий вигляд:
В індексній області ми шукаємо потрібний блок за заданим значенням первинного ключа. Оскільки всі записи впорядковані, то значення першого запису блоку дозволяє швидко визначити, у якому блоці перебуває шуканий запис. Всі інші події відбуваються в основній області. На рис. 9.8 представлений приклад заповнення основної та індексної областей, якщо первинним ключем є цілі числа.
Час сортування великих файлів дуже значний, але оскільки файли підтримуються сортованими з моменту їх створення, накладні витрати в процесі додавання нової інформації будуть набагато меншими.
Оцінимо час доступу до довільного запису для файлів із нещільним індексом. Алгоритм розв'язання задачі аналогічний.
LI = LK + 2 = 14 + 2 = 14 байт.
Тоді кількість індексних записів в одному блоці дорівнюватиме:
KIZB =LB/LI = 1024/14 = 73 індексні записи в одному блоці.
Визначимо кількість індексних блоків, яка потрібна для зберігання необхідних індексних записів:
KIB = KBO/KZIB = 12500/73 = 172 блоки.
Тоді час доступу за попередньою формулою визначатиметься:
Tпошуку = log2KIB + 1 = log2172 + 1 = 8 + 1 = 9 звернень до диска.
Ми бачимо, що при переході до нещільного індексу час доступу зменшився майже в півтора рази. Тому можна визнати, що організація нещільного індексу дає виграш у швидкості доступу.
Розглянемо процедури додавання та видалення нового запису при подібному індексі.
Тут механізм включення нового запису принципово відрізняється від раніше розглянутого. Тут новий запис повинен заноситися відразу в необхідний блок на необхідне місце, що визначається заданим принципом упорядкованості на множині значень первинного ключа. Тому спочатку шукається необхідний блок основної пам'яті, в який треба помістити новий запис, а потім цей блок зчитується, потім в оперативній пам'яті коригується вміст блоку і знову записується на диск на старе місце. Тут, так само як і в першому випадку, повинен бути заданий відсоток початкового заповнення блоків, але тільки стосовно основної області. У MS SQL server цей відсоток називається Full-factor і використовується для формування кластеризованих індексів . Кластеризованими називаються саме індекси, в яких вихідні записи фізично впорядковані за значеннями первинного ключа. При внесенні нового запису індексна область не коригується.
Кількість звернень до диска при додаванні нового запису дорівнює кількості звернень, необхідних для пошуку відповідного блоку плюс одне звернення, яке потрібно для занесення зміненого блоку настаре місце.
T додавання = log2N +1 + 1 звернень.
Знищення запису відбувається шляхом її фізичного видалення з основної області, причому індексна область зазвичай не коригується, навіть якщо видаляється перший запис блоку. Тому кількість звернень до диска при видаленні запису така сама, як і при додаванні нового запису.
Організація індексів у вигляді B-tree (В-дерев)
Калькований термін "B-дерево", в якому поєднується англійський символ "B" та додаткове слово українською мовою, настільки встоявся в літературі, присвяченій організації фізичного зберігання даних, що я не наважусь його коригувати.
Зустрівши якось термін "Б-дерево", я довго його трактувала, тому що звикла вже до усталеного позначення. Тому працюватимемо з цим терміном.
Побудова В-дерев пов'язана з простою ідеєю побудови індексу над вже побудованим індексом. Дійсно, якщо ми побудуємо нещільний індекс, то сама індексна область може бути розглянута нами як основний файл, над яким треба знову побудувати нещільний індекс, а потім знову над новим індексом будуємо наступний і так до того моменту, поки не залишиться лише один індексний блок.
Ми в загальному випадку отримаємо деяке дерево, кожен батьківський блок якого пов'язаний з однаковою кількістю підлеглих блоків, число яких дорівнює кількості індексних записів, що розміщуються в одному блоці. Кількість звернень до диска при цьому для пошуку будь-якого запису однакова і дорівнює кількості рівнів у дереві, що побудовано. Такі дерева називаються збалансованими (balanсed) саме тому, що шлях від кореня до будь-якого аркуша в цьому дереві однаковий. Саме термін "збалансований" від англійського "balanced" - "збалансований, зважений" і дав назву даному методу організаціїіндексу.
Побудуємо подібне дерево для нашого прикладу та розрахуємо для нього кількість рівнів та, відповідно, кількість звернень до диску.
На першому рівні число блоків дорівнює числу блоків основної області, це нам відомо, воно дорівнює 12 500 блоків. Другий рівень утворюється з нещільного індексу, ми його теж вже будували і обчислили, що кількість блоків індексної області в цьому випадку дорівнює 172 блоків. А тепер над цим другим рівнем знову збудуємо нещільний індекс.
Ми не змінюватимемо довжину індексного запису, а вважатимемо її колишньою, що дорівнює 14 байтам. Кількість індексних записів в одному блоці нам теж відома, і вона дорівнює 73. Тому відразу визначимо, скільки блоків нам необхідно для зберігання посилань на 172 блоки.
KIB3 = KIB2/KZIB = 172/73 = 3 блоки
Ми знову округляємо у бік, тому що останній, третій блок буде заповнений не повністю.
І над третім рівнем будуємо новий, і на ньому буде лише один блок, у якому буде лише три записи. Тому кількість рівнів у побудованому дереві дорівнює чотирьом, і кількість звернень до диску для доступу до довільної записи дорівнює чотирьом (рис. 9.9). Це не максимально можливе число звернень, а завжди те саме, однакове для доступу до будь-якого запису.
Механізм додавання і видалення запису при організації індексу у вигляді дерева аналогічний механізму, що застосовується у випадку з нещільним індексом.
І нарешті, останнє, що хотілося б прояснити, — це наявність другої назви для щільного та нещільного індексів.
У разі щільного індексу після визначення місцезнаходження шуканого запису доступ до неї здійснюється прямим способом за номером запису, тому цей спосіб організації індексу називається індексно-прямим.