Структуры и алгоритмы обработки данных. Ключарев А.А - 67 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

67
том, чтобы перейти на следующий блок и узнать, можно ли последнюю
запись найденного блока переместить в начало следующего. Если мож-
но, то осуществляем перенос (освобождая место в найденном блоке),
вставляем новую запись на подходящее место в найденный блок, кор-
ректируем индексный файл. Если следующий блок заполнен полнос-
тью или найденный блок является последним, то у файловой системы
запрашиваем новый блок, помещаем его за найденным блоком, в новый
блок вставляем новую запись и корректируем индексный файл.
Еще одним способом организации файла с использованием индек-
сов является сохранение произвольного порядка записей в файле и со-
здание другого файла, с помощью которого можно отыскивать требуе-
мые записи. Этот файл называется плотным индексом. Плотный
индекс состоит из пар (x, p), где p – указатель на запись с ключом x в
основном файле. Эти пары отсортированы по значениям ключа. Поиск
записи осуществляется подобно поиску с использованием разрежен-
ного индекса (рис. 18).
Если требуется вставить новую запись, отыскивают последний блок
основного файла и туда вставляют новую запись. Если последний блок
полностью заполнен, то запрашивают новый блок у файловой системы.
Одновременно вставляют указатель на соответствующую запись в фай-
ле плотного индекса. Чтобы удалить запись, в ней просто устанавлива-
ют бит удаления и удаляют соответствующий указатель в плотном ин-
дексе.
1.4.2. B-деревья
1.4.2.1. Представление файлов B-деревьями
Как мы уже видели, очень эффективным является хранение множе-
ства данных в виде дерева. Поэтому в качестве типового способа орга-
низации внешней памяти стало B-дерево, которое обеспечивает при
своем обслуживании относительно небольшое количество обращений
к внешней памяти (рис. 19).
B-дерево представляет собой дерево поиска степени m, характеризу-
ющееся следующими свойствами:
1) корень либо является листом, либо имеет не менее двух потомков;
2) каждый узел, кроме корня и листьев, имеет от (m/2) до m по-
томков;
3) все пути от корня до любого листа имеют одинаковую длину.

Страницы