Структуры данных и алгоритмы для внешней памяти

При обработке данных в большом объеме (большем, чем позволяет обрабатывать оперативная память) для увеличения эффективности необходимо использовать специальные алгоритмы, рассчитанные на то, что обрабатываемая информация находится на вторичных устройствах памяти (жестком диске).

В Си предусмотрен файловый тип данных, предназначенный для представления данных, хранящихся во вторичной памяти.

ОС делит вторичную память на блоки одинакового размера. Размер блока зависит от типа ОС.

Файл можно рассматривать как связный список блоков, хотя чаще всего ОС использует древовидную организацию блоков, при которой блоки, составляющие файл, являются листьями дерева, а каждый внутренний узел содержит указатели на множество блоков файла.

Базовой операцией, выполняемой по отношению к файлам, является перенос одного блока в буфер, находящийся в основной памяти. Буфер представляет собой зарезервированную область в основной памяти, размер которой соответствует размеру блока. Обычно ОС обеспечивает чтение блоков в линейном порядке, т.е. сначала заносится первый блок файла, затем он заменяется на второй и т.д.

Мерой качества алгоритма, работающего со внешней памятью, является количество обращений к блокам.

Изучение алгоритмов начнем с рассмотрения способов внешней сортировки.

Внешняя сортировка

Алгоритм сортировки слиянием позволяет отсортировать файл с n записями за O(log n) проходов через файл.

Сортировка слиянием выглядит следующим образом: сначала мы разбиваем массив на две половины меньшего размера. Затем мы сортируем каждую из половин отдельно. После этого соединяем два упорядоченных массива в один.

Рекурсивное разбиение на подзадачи происходит до тех пор, пока размер массива не дойдет до 1 (любой массив длины 1 можно считать упорядоченным).

Соединение двух отсортированных массивов происходит методом слияния.

Напишем процедуру сортировки слиянием MergeSort( a, p, r), которая сортирует участок массива а с индексами от р до r, не меняя остальную часть массива. При р>=r участок содержит максимум 1 элемент, и тем самым уже отсортирован. В противном случае мы отыскиваем число q, которое делит участок на две примерно равные части от р до q и от q+1 до r.

void MergeSort(element_type a[], int p, int r)

{

int q;

if(p < r)

{

q = (p+r)/2;

MergeSort(a, p, q);

MergeSort(a, q+1, r);

Merge(a,p,q,r); /* слияние двух упорядоченных массивов в один */

}

}

Весь массив теперь можно отсортировать с помощью вызова MergeSort(a, 0, n-1);

Временная сложность этого алгоритма O(n log n).

Хранение данных в файлах

Рассмотрим структуры данных и алгоритмы для хранения и поиска информации в файлах, находящихся во внешней памяти. Файл мы будем рассматривать как последовательность записей, причем каждая запись состоит из одной и той же совокупности полей. Поля могут иметь либо фиксированную длину (заранее определенное количество байт), либо переменную. Файлы с записями фиксированной длины широко используются в системах управления базами данных для хранения данных со сложной структурой. Файлы с записями переменной длины, как правило, используются для хранения текстовой информации.

Рассматривая операции с файлами, в первом приближении можно считать, что файлы – это просто совокупности записей, над которыми можно выполнять операторы. Однако имеются два важных отличия. Во-первых, когда мы говорим о файлах, хранящихся на устройствах внешней памяти, то при оценивании тех или иных стратегий организации файлов нужно использовать меру затрат. Другими словами, мы предполагаем, что файлы хранятся в виде некоторого количества физических блоков, а затраты на выполнение оператора пропорциональны количеству блоков, которые мы должны считать в основную память или записать из основной памяти на устройство во внешней памяти.

Второе отличие заключается в том, что для записей, представляющих собой конкретные типы данных в большинстве языков программирования, могут быть предусмотрены указатели, в то время как для абстрактных элементов из некоторой совокупности никакие «указатели» предусмотреть нельзя. Например, в системах баз данных при организации данных часто используются указатели на записи. Следствием применения подобных указателей является то, что записи часто приходится считать закрепленными: их нельзя перемещать во внешней памяти, поскольку не исключено, что какой-то неизвестный нам указатель после таких перемещений записи будет указывать неправильный адрес этой записи.

Простой способ представления указателей на записи заключается в следующем. У каждого блока есть определенный физический адрес, т. е. Место начала этого блока на устройстве внешней памяти. Отслеживание физических адресов является задачей файловой системы. Одним из способов представления адресов записей является использование физического адреса блока, содержащего интересующую нас запись, со смещением, указывающим количество байт в блоке, предшествующих началу этой записи. Такие пары «физический адрес-смещение » можно хранить в полях типа « указатель на запись».