Таблиці з довідниками

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

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

– по-перше, якщо основна таблиця розташована на зовнішній пам'яті, то довідкова таблиця (чи значна її частина) може бути розміщена в оперативній пам'яті і пошук ключа, таким чином, буде виконуватися в оперативній пам'яті, що набагато швидше;

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

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