Сортировка дисковых файлов произвольного доступа

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

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

{пример программы сортировки списка почтовых адресов}

programm MlistSort;
type
 address = record
 name: string[30]; street: string[40];
 sity: string[20]; state: string[2]; 
 zip: string[9];
end;
 str80 = string[80];
DataItem = addres;
DataArray = array [1..80] of DataItem
recfil = file of DataItem

var
 test: DataItem; t, t2:integer; testfile: recfil;
 { найти запись в файле }
function Find(var fp:recfil; i:integer): str80
 var
 t:address;
begin
 i := i-1;
 Seek(fp, i)
 Read(fp, t)
 Find := t.name;
end;

procedure QsRand(var var fp:recfil; count:integer)

procedure Qs(l, r:integer)

var
 i, j, s:integer ;
 x, y, z:DataItem;
begin
 i := l; j := r; s := (l+r) div 2;
 Seek(fp,s-1); { получить запись }
 Reed(fp,x);
 repeat
 while Find(fp, i) < x.name do i := i+1;
 while x.name < Find(fp, j) do j := j-1;
 if i <= j then
 begin
 Seek(fp,i-1); Reed(fp,y);
 Seek(fp,j-1); Reed(fp,z);
 Seek(fp,j-1); Write(fp,y);
 Seek(fp,i-1); Write(fp,z); i := i+1; j := j-1;
end;
until i > y; if l < j then qs(l, j) if l < r then qs(i, r)
end;

begin
 qs(1,count);
end; { конец быстрой сортировки файла произвольного доступа }

begin
 Assign(testfile, ‘rectest.dat’);
 Reset(testfile);
 t := 1;
 while not EOF(testfile) do begin
 Read(testfile,test); { подсчет числа записей в файле}
 t := t+1;
end;
 t := t-1;

QsRand(testfile,t) end.

Функция Find используется для того, чтобы оставить в основном неизменным программу быстрой сортировки. Результатом этой функции является символьная строка «name» из записи, расположенной на диске. Необходимо постоянно вычитать единицу из аргументов функций Seek и Find, так как записи дискового файла нумеруются начиная с нуля, а массивы нумеруются с единицы.