Таблиці

З фізичної точки зору таблиця представляє собою вектор, елементами якого є записи. Характерною логічною рисою таблиць, що і визначила їхній розгляд в окремому розділі, є те, що доступ до елементів таблиці виконується не за номером (індексом), а за ключем – за значенням однієї з властивостей об'єкта, описуваного записом – елементом таблиці. Ключ – це властивість, що ідентифікує даний запис у множині однотипних записів. Як правило, до ключа пред'являється вимога унікальності в даній таблиці. Ключ може включатись до складу запису і бути одним з його полів, але може і не включатись в запис, а обчислюватись за положенням запису. Таблиця може мати один чи декілька ключів. Наприклад, при інтеграції в таблицю записів про студентів вибірка може виконуватись як за особистим номером студента, так і за прізвищем.

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

Іноді розрізняють таблиці з фіксованою і зі змінною довжиною запису. Очевидно, що таблиці, які поєднують записи зовсім ідентичних типів, будуть мати фіксовані довжини записів. Необхідність у змінній довжині може виникнути в задачах, подібних тим, що розглядались для записів з варіантами. Як правило, таблиці для таких задач і складаються із записів з варіантами, тобто зводяться до фіксованої (максимальної) довжині запису. Значно рідше зустрічаються таблиці з дійсно змінною довжиною запису. Хоча в таких таблицях і заощаджується пам'ять, але можливості роботи з такими таблицями обмежені, тому що за номером запису неможливо визначити її адресу. Таблиці з записами змінної довжини обробляються тільки послідовно – у порядку зростання номерів записів. Доступ до елементу такої таблиці звичайно здійснюється за два кроки. На першому кроці вибирається постійна частина запису, у якій міститься – у явному чи неявному вигляді – довжина запису. На другому кроці вибирається змінна частина запису відповідно до її довжини. Додавши до адреси поточного запису його довжину, одержують адресу наступного запису.

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