Організація даних для прискорення пошуку за вторинними ключами

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

Навіть при наявності первинного ключа, для пошуку запису можуть використовуватися вторинні. Наприклад, пошукові системи Internet часто організовані як набори записів, які відповідають Web-сторінкам. В якості вторинних ключів для пошуку виступають ключові слова, а сама задача пошуку зводиться до вибірки з таблиці деякої множини записів, які містять потрібні вторинні ключі.

Інвертовані індекси

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

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

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

Система інвертованих індексів є досить зручною й ефективною при організації пошуку в великих таблицях.

Бітові карти

Для таблиць невеликого об’єму використовують організацію допоміжної структури даних у вигляді бітових карт. Для кожного значення вторинного ключа записів основного набору даних записується послідовність бітів. Довжина послідовності бітів рівна кількості записів. Кожен біт в бітовій карті відповідає одному значенню вторинного ключа і одному запису. Одиниця означає наявність ключа в запису, а нуль – відсутність.

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

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