Впорядковані файли

Запису у файлі можна відсортувати по значеннях одного або декількох полів і таким чином утворити набір даних, впорядкований по деякому ключу. Поле (або набір полів), по якому сортується файл, називається по­лем впорядкування. Якщо поле впорядкування є також ключем доступу до файлу і тому гарантується наявність в кожному записі унікального значення цього поля, воно називається ключем впорядкування для даного файлу. Розглянемо, наприклад, приведений нижче запит SQL.

SELECT *

FROM Staff

ORDER BY staffNo;

Якщо кортежі відношення Staff вже впорядковані по полю staffNo, час виконання запиту скорочується, оскільки не потрібно виконувати сортування. (Хоча в розділі 3.2 вказано, що кортежі стосунків не впорядковані, при цьому малася на увазі їх зовнішня (логічне), а не внутрішня (фізичне) вистава. Річ у тому, що з точки зору фізичної організації серед записів завжди перша, друга і так далі) Якщо кортежі впорядковані по полю staffNo, то за певних умов при обробці запитів можна застосовувати бінарний пошук – в тих випадках, коли запит містить умову пошуку з використанням значення поля staffNo. Як приклад розглянемо запит SQL, приведений нижче.

SELECT *

FROM Staff

WHERE staffNo = 'SG37';

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

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

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

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

В даному випадку середньою є сторінка 3, але запис на цій сторінці (SG14) не є шуканим (SG37). Значення ключового поля запису на страни це 3 менше необхідного значення, тому вся ліва половина файлу виключається з області пошуку. Тепер слід витягувати середню сторінку з частини файлу (його правої половини), що залишилася, тобто сторінку 5. Цього разу значення ключового поля (SL21) більше шуканого значення (SG37), що дозволяє виключити з поточної зони пошуку її праву половину. Після витягання середньої сторінки з частини файлу (тобто сторінки 4), що залишилася на даний момент, можна переконатися в тому, що саме вона і є шуканою.

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

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

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

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