1. Последовательная организация.
Если отведенная память для СУБД – это логически связанная последовательность, то для файловой системы – это последовательность кластеров.
Последовательное распределение – простой и естественный способ хранения линейного списка. В этом случае узлы списка размещаются в последовательных элементах памяти.
Нужно иметь доступ к любой записи и обеспечить эффективность следующих операций с ними:
– чтение записи;
– модификация записи;
– удаление записи.
Длина записи может быть фиксированной или переменной.
а) Записи фиксированной длины
Записи размещаются последовательно непосредственно друг за другом. Вектор данных логически отделен от описания структуры хранимых данных. Например, если структура данных представляет собой линейный список (файл записей фиксированной длины), то описание структуры хранится в отдельной записи и содержит:
а) N – размер вектора данных, т.е. количество элементов списка записей;
б) т – размер элемента списка, т.е. размер записи, например, в байтах;
в) β – адрес базы, указывающий на начало вектора данных в памяти.
В этом случае адрес каждой записи можно вычислить с помощью адресной функции, отображающей логический индекс, идентифицирующий запись в структуре, в адрес физической памяти
б) Записи имеют различную длину
При неравной длине записей для определения границ между записями требуются дополнительные средства. Это может быть хранение в записи адреса начала следующей записи или длины текущей записи, введение специальных меток начала (конца) записи.
При неравной длине записи выборка замедляется из-за необходимости последовательного перебора до нужной записи. Для повышения быстродействия в этом случае может использоваться искусственное выравнивание записей.
1) Хранение адреса следующей записи
2) Хранение длины следующей записи
3) Выравнивание записей.
Добавление записи при последовательной организации трудоемко из-за необходимости перемещения всех записей, следующих за добавляемой, для освобождения места под новую запись. Поэтому прямая вставка не эффективна, рекомендуется добавление в конец.
При страничной организации для улучшения характеристик применяют неполное заполнение страниц, что позволяет локализовать перемещение записей одной страницей.
Аналогичные трудности возникают при операции удаления, когда записи перемещаются для заполнения освободившегося места. Здесь для повышения быстродействия и для избавления от массовой перезаписи файла часто используется пометка записей на удаление без немедленного сжатия данных. При этом разделяют физическое и логическое удаление (например, в Visual Fox Pro: PACK – физическое удаление, DELETE – логическое удаление. Физическое удаление предполагает монопольный режим и выполняется медленно, поэтому вызывается редко).
Модификация записи при равной длине выполняется просто, но при неравной длине записей снова могут возникать проблемы, связанные с необходимостью перезаписи больших объемов данных. При записях одинаковой длины, просто добавляется в пустое место или в конец, иначе при записях неодинаковой длины – запись в конец.
Для повышения эффективности доступа применяют также выравнивание записей. Для этого существует два метода:
1) Выполняется поиск записи максимальной длины, выполняется расширение до этого размера (плюс некоторый запас) всех строк. Используется: когда разброс длин невелик и длина небольшая. (VARCHAR – строка переменной длины).
2) Невыравненные части записей выносятся в отдельное хранение. Используется при большом разбросе длин записей (Например, в VisualFoxPro используется описание "memo", в InterBase – "blob", указатель занимает 4 байта).