Файлы с записями переменной длины

Преимущество плотного индекса.

Файлы с плотным индексом.

Пусть нет необходимости поддерживать файл в отсортированном порядке. Допуская возможность хранения записей в произвольном порядке, можно избегать появления в главном файле большого числа частично заполненных блоков. При этом облегчается операция включения, для чего необходимо хранить только адрес последнего блока в файле и добавлять в него новую запись (при его заполнении получить адрес нового блока из OS). Если удаления производятся часто, то в файле появляются незаполненные места. Можно просто игнорировать тот факт, что определенные субблоки становятся при удалении свободными. (Напомнить технологию DELETE–PACK). Другой подход– использование отдельного файла с записями, содержащими одно поле, которое является указателем на блок с одним или более свободными субблоками (или хранить указатель на свободный субблок– кратко о безпаковочной технологии в DBF-файлах (INDEX с опциейFOR)).

При использовании не сортированного файла проблема заключается в организации поиска записей по заданному значению ключа.

Для организации такого поиска используют еще один файл, который называется плотным индексом.

Одна запись плотного индекса соответствует одной записи главного файла. Структура записи индекса: (v,p); где v–ключ записи главного файла, р – указатель на запись главного файла с ключом v.

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

Внимание! При использовании плотного индекса записи главного файла закреплены.

1) Записи главного файла могут быть закреплены, но записи индекса всегда не закреплены, следовательно, можно использовать более простую организацию и функции доступа к индексу. Нет понятия «участков» как в разряженном индексе.

2) Если записи главного файла длинные, то общее число блоков меньше, чем у разряженного индекса, т.к. все блоки (кроме последнего) заполнены плотно.

Постановка задачи: В файле одно или несколько полей имеют переменную длину.

Пример: 1) ФИО.

2) Адрес.

3) Название банка.

4) Комментарии к платежному поручению.

5) Список номерных знаков, закрепленных за а/т.

6) Список детей данного сотрудника.

Обозначение записи переменной длины α(β)*= αβ₁β_2…β_n, где α- постоянная часть.

Основные стратегии решения.

1) Запись переменной длины заменяется одной или несколькими записями фиксированной длинны.

2) Использование принципа – конец записи (конец поля).

Качество стратегии характеризуется двумя показателями:

1) Объемом дискового пространства, которое занимает файл с записями переменной длинны.

2) Временем доступа к записям файла.

Небольшую экономию дискового пространства предоставляет вторая стратегия, но это стратегия обычно требует и большого времени доступа.

Файловые системы персональных ЭВМ обычно не содержат функций организации и доступа к файлам с переменной длинной записи. Такие функции имелись в OS IBM 360. Таким образом, реализация второй стратегии возможна только за счет программного обеспечения самой СУБД.

Пример: Представить, как необходимо переделать функции доступа к файлу формата DBF, что бы реализовать доступ к файлу с записями переменной длинны.

Варианты реализации первой стратегии значительно и могут быть реализованы прикладными программистами.

Известны 3 метода реализации 1-й стратегии.

I. Метод зарезервированного пространства.

Рассмотрим методы на примере задачи: за а/т закрепляется несколько номеров гос. регистрации (оперативная работа уголовного розыска).

1) Резервируется максимально возможное число полей. Заполняется часть полей. В первое свободное поле записать признак – поле свободно.

Пример: База AUTO.DBF, поля SIGN,SIGN1, SIGN2.

2) Два поля комментария для платежных поручений.

3) Одно поле большой длинны для адреса.

4) Шаблон для З.П.

Преимущества: скорость доступа ко всей информации.

Недостатки: большие потери в занимаемом на диске пространстве, если вероятность появления записи с большой длинной мала.

II. Метод указателей.

В основной записи указатель на начало списка из записей фиксированной длинны (в том числе возможно и из другого файла) следовательно цепной список.

Пример: 1. Мемо поля Fox.

2. Организация списков с помощью индексов.

DO SCAN WHILE

.

.

.

ENDSCAN

Большое время доступа. Особенно невыгодно, если вероятность появления записи малой длинны мала.

III. Комбинированный метод.

Если среднее и максимальное число блоков существенно различаются, то при резервировании по максимуму больше число блоков не используется.

Методы доступа с указателями экономят место, но повышается время доступа.

Компромисс: резервируют несколько полей (блоков), при их заполнении выделяют новый блок (организуют список).

Пример: С базой AUTO.DBF: резервируем одно поле SIGN, а для других записей организуем список в дополнительной базе. Только в основной базе необходимо предусмотреть: есть информация в списке (например, логического типа).

Операции над записями переменной длины соответствуют операции над списками.

Дата добавления: 2014-01-05