5.3.4. Інвертовані списки

Досить часто в БД виникає необхідність проводити операції індексації за вторинними ключами. Вторинним ключем може бути атрибут або набір атрибутів. До вторинного ключа не висувається вимога унікальності. Вторинному ключу відповідає набір даних з однаковим значенням цього вторинного ключа. Пошук за вторинним ключем має на меті вибірку набору даних з однаковим значенням вторинного ключа упорядкованих за первинним ключем.

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

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

Значення вторинного ключа	№ блока		№ блока	№ запису в БД
Білий	1		1	1
				5
				25
				78
Вишневий	2		2	3
				6
				8
			3	2
				4
				11
			…	….
Зелений	3		N

Рис. 5.4. Індексна структура у вигляді інвертованого списка

Кількість блоків дорівнює кількості вторинних ключів. Кількість звернень до зовнішнього пристрою визначається таким же чином, як і для файлів з нещільним індексом .

5.3.5.Хешовані файли

Хешовання - спосіб збереження даних, в якому адреса блока вираховується як функція від значення ключа. Головна ідея організації файлів з хешованим доступом полягає в розподілі записів файла між ділянками, кожна з яких складається з декількох блоків пам‘яті. Для хешованого файла існує хеш-функція, яка використовує в якості аргумента значення ключа файла і продуцює деяке число від 0 до максимального значення . Якщо ν - значення ключа, то h(v) вказує номер ділянки , де зберігається запис з цим значенням ключа.

Формування h(v) функції є складною задачею, яка не має однозначного рішення. Головна вимога до h(v) функції полягає в тому, що всі її значення повинні мати приблизно однакову ймовірність, для забезпечення рівномірного розміщення записів БД по всіх ділянках. Одна з стратегій знаходження h(v) функції має наступний алгоритм [ ]:

1. Інтерпритуємо значення ключа, як послідовність бітів, сформовану шляхом конкатенації значень всіх полів ключа. Ця послідовність має фіксовану довжину.

2. Поділимо послідовність бітів на групи, що складаються з фіксованого числа бітів, наприклад 16, або 32. Останню групу за необхідністю доповнюємо нулями.

3. Складаємо групи бітів як цілі числа.

4. Ділимо суму на кількість ділянок і використовуємо залишок як номер ділянки.

Додатково до файла з даними складається довідник ділянок, що вміщує набір показників. Кожний показник є адресою першого блока своєї ділянки. Якщо блоків в ділянці декілька, то перший блок має в своєму заголовку вказівку на другий блок, другий - на третій і т.д. В кожному блоці передбачене збереження фіксованої кількості записів - r. Простір необхідний для збереження одного запису називається субблоком.

Розглянемо базу даних з індексацією та хешованням на прикладі розділу британської енциклопедії, присвяченому динозаврам [ ]. Структуру таблиці та її вміст легко зрозуміти з рис. 5.5. Поле Назва утворює ключ для цієї таблиці. Один блок складається з двох субблоків. Один запис зай має один субблок, тобто, в одному блоці може бути розташовано тільки два записи. На початку блока є показчик, в якому відмічено стан субблоків - “1”, якщо субблок занятий, “0”, якщо вільний. Ліворуч зображено список ділянок ( можливо сторінок) до яких входять блоки. Слід відмітити, що структура файла та функція хешовання спрощені відносно реальних для полегшення розуміння матеріалу. В якості функції хешовання виберемо ділення по модулю 5 довжини ключового поля, тобто довжини назви. Номером ділянки тут буде залишок від ділення довжини ключового поля на 5. Якщо назва динозавра налічує 10 літер, то залишок від ділення на 5 дорівнює 0, отже опис цього динозавра слід помістити до ділянки з номером «0». Якщо всі субблоки ділянки з номером «0» заповнені, то її доповнюють новим блоком. Приклад: внести в базу даних динозаврів відомості про Еласмозавра (Elasmosaurus). Латиною назва динозавра складається з 12 літер (всі назви записують латиною). При діленні на 5 отримаємо залишок, що дорівнює 2, Тобто, Еласмозавр потрапить до другої ділянки, в перший субблок другого блока, тому що перший блок увесь заповнений. Між собою блоки однієї ділянки зв‘язані прямими посиланнями.

Вільний простір

Заповнено-незаповнено

0			11	Диплодок	Юрсь-кий	Озеро	Травоїдний	90	15	Аллозавр	Юрський	Суша	Плотоїдний	35	5
1			11	Птеродак-тиль	Крейдя-ний	Повітря	Плотоїдний	1	0	Стегозавр	Юрський	Суша	Травоїдний	20	2
2			10	Трайсератопс	Крейдя-ний	Суша	Травоїдний	25	10
3			11	Платео-завр	Третич-ний	Суша	Травоїдний	30	5	Бронтозавр	Юрський	Озеро	Травоїдний	70	25
								2	0
4			11	Брахио-завр	Юрсь-кий	Озеро	Травоїдний	80	50	Компсогнат	Юрський	Суша	Плотоїдний
5			10	Тиранно-завр	Крейдя-ний	Суша	Плотоїдний	50	8

Рис. 5.5. Таблиця з хешованим індексом та показниками ділянок