Файлы с неплотным индексом или индексно-последовательные файлы, Организация индексов в виде В-дерева -- многоуровневой иерархической структуры - Проблема организации и хранения данных

Структура записей данных в таких файлах имеет вид, представленный на рис. 4.

Рис. 4 Структура записей данных в файлах с неплотным индексном

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

Определяется номер блока основной области, в который необходимо поместить новую запись;

Найденный блок считывается в оперативную память;

В оперативной памяти производится корректировка блока;

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

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

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

Организация индексов в виде В-дерева -- многоуровневой иерархической структуры

Данное направление совершенствования организации файловой структуры связано с преобразованием индексной области файлов с неплотным индексом, который изначально предполагает описание этой области как одного упорядоченного списка, в вид иерархического симметрического поискового дерева. В таких деревьях число узлов на каждом уровне одинаково. Теоретические основы организации машинной памяти при построении таких иерархических систем были изложены в 1967 г. автором языка ассоциативного программирования АЛГЭМ, преподавателем Московского энергетического института А. И. Китовым.

Однако в современной литературе по теории баз данных иерархическую поисковую структуру принято называть B-деревом (читается: "Б-деревом") (от англ. B-tree - сбалансированное дерево).

На рис. 5 показан пример организации файловой структуры в виде В-дерева.

Рис. 5 Пример организации файловой структуры в виде B-дерева

Похожие статьи




Файлы с неплотным индексом или индексно-последовательные файлы, Организация индексов в виде В-дерева -- многоуровневой иерархической структуры - Проблема организации и хранения данных

Предыдущая | Следующая