Багатофазне сортування. Прийнято називати ≪зовнішнім≫ сортування послідовних файлів, розташованих у зовнішній пам'яті і дуже великих

Прийнято називати ≪зовнішнім≫ сортування послідовних файлів, розташованих у зовнішній пам'яті і дуже великих, щоб можна було повністю перемістити їх в основну пам'ять і застосувати один з розглянутих у попередньому розділі методів внутрішнього сортування. Найчастіше зовнішнє сортування застосовується в системах керування базами даних при виконанні запитів, і від ефективності вживаних методів істотно залежить продуктивність СУБД.

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

Вся річ у тому, що практично всі використовувані на сьогодні дискові пристрої забезпечені рухомими магнітними головками. При виконанні обміну з дисковим накопичувачем виконується підведення головок до потрібного циліндра, вибір потрібної головки (доріжки), прокручування дискового пакету до початку необхідного блоку і,нарешті, читання або запис блоку. Серед всіх цих дій найбільший час займає підведення головок. Саме цей час визначає загальний час виконання операції. Єдиним доступним прийомом оптимізації доступу до магнітних дисків є якомога ≪ближче≫ розташування файла на накопичувачіблоків, що послідовно адресуються. Але і в цьому випадку рух головок буде мінімізованим у тому випадку, коли файл читається або пишеться в послідовному режимі. Саме з такими файлами при потребі сортування працюють сучасні СУБД.

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