Объем данных, помещенных в каждую из записей файла, может
быть столь большим, что при сортировке перемещение самих записей
является нецелесообразным из-за больших накладных расходов.(рис.1)
а – файл до сортировки, б – файл после сортировки.
При индексной сортировке создается вспомогательная таблица указателей (файл) на записи файла данных(информационного). Вместо перемещения записей в информационном файле перемещаются указатели в индексном файле.
Этот метод называется сортировкой таблицы адресов(индексная сортировка).
Таким образом, сортировке подвергается не сам информационный файл, а вспомогательный файл, каждая запись которого состоит из поля указателя на запись информационного файла и поля ключа этой записи.
Рис.2
Первоначально элемент в позиции j индексного файла указывает на j-ю запись информационного файла. После окончания сортировки первый указатель указывает на запись файла с наименьшим ключом. Второй указатель - на запись файла со следующим по порядку сортировки ключом и т.д.
Сортировку таблицы указателей можно выполнять одним из методов внутренней сортировки.
Преимущество – скорость;
недостаток – дополнительная память для хранения индексного файла и дополнительный набор операций для работы с индексными файлами.
