мо, що всі записи мають фіксовану довжину, тоді як покажчика можна використовувати номер запису. Зсув запису у файлі в цьому випадку буде Обчислити як ([номер_запісі] -1) * [дліна_запісі]. Нехай аргумент пошуку "Петров". На малюнку 1.2 показані одне з можливих для цього набору даних бінарних дерев пошуку і шлях пошуку.
В
Рис. 1.2
Таблиця 1.1
студент
бал
Іванов
3,4
Васильєв
4,2
Кузнєцов
3,5
Петров
3,2
Сидоров
4,6
Тихомиров
3,8
Зауважимо, що тут використовується наступне правило порівняння строкових змінних: вважається, що значення символу відповідає його порядковому номеру в алфавіті. Тому "І" менше "К", а "К" менше "С". Якщо поточні символи в порівнюваних рядках збігаються, то порівнюються символи в наступних позиціях.
Бінарні дерева особливо ефективні в разі коли безліч ключів заздалегідь невідомо, або коли це безліч інтенсивно змінюється. Очевидно, що при змінному безлічі ключів краще мати збалансоване дерево.
Бінарне дерево називають збалансованим (balanced), якщо висота лівого піддерева кожного вузла відрізняється від висоти правого піддерева не більше ніж на 1.
При пошуку даних у зовнішній пам'яті дуже важливою є проблема скорочення числа переміщень даних із зовнішньої пам'яті в оперативну. Тому, в даному випадку по порівняно з бінарними деревами більш вигідними виявляться сильно розгалужені дерева - тому що їх висота менше, то при пошуку буде потрібно менше звернень до зовнішньої пам'яті. Найбільше застосування в цьому випадку отримали В-дерева (В - balanced).
В-деревом порядку n називається сильно гілкуються дерево ступеня 2n +1, що має такими властивостями:
В· Кожен вузол, за винятком кореня, містить не менше n і не більше 2n ключів.
В· Корінь містить не менше одного і не більше 2n ключів.
В· Всі листя розташовані на одному рівні.
В· Кожен нелістовой вузол містить два списки: упорядкований за зростанням значень список ключів і соответсвующий йому список покажчиків (для листових вузлів список покажчиків відсутня).
Для такого дерева:
В· порівняно просто може бути організований послідовний доступ;
В· всі листя розташовані на одному рівні;
В· при додаванні і зміні ключів всі зміни обмежуються, як правило, одним вузлом.
Слід відзначити, що B-дерева найкращим чином підходять тільки для організації доступу до досить простим (одновимірним) структурам даних. Для доступу до більш складним структурам, таким, наприклад, як просторові (багатовимірні) дані останнім часом все частіше використовують R-дерева.
R-дерево (R-Tree) це індексна структура для доступу до просторових даних, запропонована А.Гуттманом (Каліфорнійський університет, Берклі). R-дерево допускає довільне виконання операцій додавання, видалення та пошуку даних без періодичної переиндексации.
Хешування
Цей метод використовується тоді, коли всі безліч ключів заздалегідь відомо і на час обробки може бути розміщено в оперативній пам'яті. У цьому випадку будується спеціальна функція, однозначно відображає безліч ключів на безліч покажчиків, звана хеш-функцією (від англійського "to hash" - різати, подрібнювати). Маючи таку функцію можна обчислити адресу запису у файлі по заданому ключу пошуку. У загальному випадку ключові дані, які використовуються для визначення адреси запису організовуються у вигляді таблиці, званої хеш-таблицею.
Якщо безліч ключів заздалегідь невідомо або дуже велике, то від ідеї однозначного обчислення адреси запису за її ключу відмовляються, а хеш-функцію розглядають просто як функцію, розсіювальну безліч ключів в безліч адрес.
Для більш просунутого користувача можна навести наступне визначення:
Хешування (іноді хешування, англ. hashing) - перетворення вхідного масиву даних довільної довжини в вихідну бітову рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки, а їх результати називають хешем, хеш-кодом або дайджестом повідомлення (англ. message digest).
Хешування застосовується для порівняння даних: якщо у двох масивів хеш-функції різні, масиви гарантовано розрізняються; якщо однакові - масиви, шви...
