Организация данных и структуры данных
Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора |
Инвертированные файлыОбычные файлы данных конструируются так, чтобы обслуживать отдельные приложения, такие, как управление запасами и ведение текущих счетов. Если необходимо получить заданный в алфавитном порядке список студентов университета с указанием посещаемых ими курсов и список всех университетских курсов с указанием фамилий студентов, которые их изучают, то в традиционной файловой системе есть две возможности решения такой задачи. Одно решение заключается в том, чтобы завести два отдельных файла, один упорядоченный по фамилиям студентов, а другой по названиям курсов. Тогда любой из списков может быть немедленно получен. Такая файловая организация ориентирована на минимизацию времени выполнения программы. Она обеспечивает быстрый ответ, но приводит к очень неэффективному использованию внешней памяти. Вся информация в данном случае дублируется, и памяти требуется вдвое больше, чем это действительно необходимо. При другом решении заводится только один файл, упорядоченный согласно чаще всего используемому ключу (например, по фамилиям студентов), и если необходимо получить список курсов, то весь файл рассортировывается согласно этому ключу прежде, чем список будет выдан. Такой подход сводит к минимуму требуемый объем памяти, но увеличивает время работы центрального процессора, поскольку всякий раз, когда надо получить список, упорядоченный не по основному ключу, необходимо провести сортировку. Поскольку существуют эффективные программы сортировки (разд. 9.5), то каждый из этих методов имеет свою область преимущественной применимости. Так, если файл немноготошый, то лучше может оказаться первый способ, тогда как для больших объемов данных более целесообразным представляется второй подход. С другой стороны, если данные обрабатываются, не последовательно, а в произвольном порядке, то частая рассортировка всегда приведет к тому, что второй подход окажется очень неэффективным. Использование дублированных файлов ускоряет случайный поиск данных и в известной степени облегчает его, однако затрудняет выполнение корректировки данных. Всякий раз, когда изменяется некоторое поле в записи, аналогичные изменения должны быть внесены во все другие файлы, содержащие это же поле в некоторой другой записи. Поскольку обращение к другим файлам непосредственно по значению этого поля невозможно при обычной файловой структуре, то внесение изменений, как правило, сопряжено с последовательным просмотром всех связанных файлов. Для эффективного решения рассматриваемой проблемы используются так называемые инвертированные файлы. |