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


Использование деревьев для индексирования - часть 2


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

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

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

В примере с полем name

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

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

type

    pterm = ^term;

    term = record

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

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

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

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

    end;


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

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

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




- Начало -  - Назад -  - Вперед -



Книжный магазин