Организация и функционирование компьютеров

• задание порядка в множестве записей (в простейшем случае согласно значению заданного поля); при этом предпочтительнее, чтобы задание порядка не сопровождалось физическим изменением расположения элементов в базе данных;

• переход от текущей записи к последующей и к предыдущей (при условии, что порядок задан);

• вывод всех записей в порядке возрастания (при условии, что порядок задан);

• поиск записи по заданному значению какого-то поля или по сложному критерию;

• поддержание порядка при добавлении, изменении и удалении данных.

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

Пусть данные – это запись, а порядок задается одним из полей этой записи (например, наименованием name). Будем формально различать в бинарном дереве стрелки “вниз влево” и “вниз вправо” (соответственно, говорить о левом подчинении и правом подчинении). Бинарное дерево задает упорядочение массива данных при выполнении следующих условий:

• существует взаимнооднозначное соответствие между записями массива и вершинами дерева;

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

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

Перейдем к вопросу о том, как устроено формальное описание дерева индекса массива данных. В описание вершины индексного дерева будут входить четыре компоненты:

type

pterm = ^term;

term = record

num: longint; {Номер записи, соответствующей вершине}

val: type_val; {Поле упорядочения (type_val – тип поля упорядочения ) }

pleft: pterm; {Cсылка на левую подчиненую вершину (Nil в случае ее отсутствия) }

pright: pterm {Cсылка на правую подчиненую вершину (Nil в случае ее отсутствия) }

end;

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

Назначить текущей вершиной корневую вершину дерева индекса

Значение поля в текущей вершине совпадает с искомым ¬¬да Запись найдена

нет

Значение поля в текущей вершине больше (меньше) искомого значения

больше меньше

У текущей вершины У текущей вершины

есть левый слуга есть правый слуга

да нет да нет

Сделать левого Запись не найдена Сделать правого Запись не найдена

слугу текущим слугу текущим

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

Назначить текущей вершиной корневую вершину дерева индекса

Значение поля в текущей вершине больше (меньше) искомого значения

больше меньше или равно