ної пам'яті прямо пропорційний кількості елементів у базі даних. Кожен запис у таблиці зберігається не окремо, а в якомусь блоці ( bucket ). Ці блоки збігаються з фізичними блоками на пристрої зберігання даних. Якщо в блоці немає більше місця, щоб вмістити запис, то блок ділиться на два, а на його місце ставиться покажчик на два нові блоки.
Завдання полягає в тому, щоб побудувати бінарне дерево, на кінцях гілок якого були б покажчики на блоки, а навігація здійснювалася б на основі псевдоключа. Вузли дерева можуть бути двох видів: вузли, які показують на інші вузли або вузли, які показують на блоки. Наприклад, нехай вузол має такий вигляд, якщо він показує на блок:
ZeroNullBucketУказательOneNull
Якщо ж він буде показувати на два інших вузла, то він буде мати такий вигляд:
ZeroАдрес aBucketNullOneАдрес b
Спочатку є тільки покажчик на динамічно виділений порожній блок. При додаванні елемента обчислюється псевдоключ, і його біти по черзі використовуються для визначення місця розташування блоку. Наприклад, елементи з псевдоключа 00 ... будуть поміщені в блок A, а 01 ... - в блок B. Коли А буде переповнений, він буде розбитий таким чином, що елементи 000 ... і 001 ... будуть розміщені в різних блоках. br/>
2.2 Застосування хешування
Досі розглядалися способи пошуку в таблиці по ключах, що дозволяє однозначно ідентифікувати запис. Такі ключі називаються первинними ключами. Можливий варіант організації таблиці, при якому окремий ключ не дозволяє однозначно ідентифікувати запис. Така ситуація часто зустрічається в базах даних. Ідентифікація запису здійснюється за деякою сукупністю ключів. Ключі, що не дозволяють однозначно ідентифікувати запис у таблиці, називаються вторинними ключами. p align="justify"> Навіть за наявності первинного ключа, для пошуку записи можуть бути використані вторинні. Наприклад, пошукові системи internet часто організовані як набори записів, які відповідають Web-сторінок. В якості вторинних ключів для пошуку виступають ключові слова, а сама задача пошуку зводиться до вибірці з таблиці деякого безлічі записів, що містять необхідні вторинні ключі. br/>
РОЗДІЛ 3. ПРОГРАМНА РЕАЛІЗАЦІЯ
3.1 Організація структури даних
Всі дані організовані в структурі що є дерево:
class BH_Tree
{
private:
BH * Head;: _Tree ();
~ BH_Tree (); * Key_Gen (String * data, int coll); insert (String * data, int coll); Past (BH * root, String * data, int coll, int pos) ; paintTree (TImage * img, int x, int y, int _x = 0, int _y = 0); paintRoot (TImage * img, BH * root, int x, ...
