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



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


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

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

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

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

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

    type

        pterm = ^term;

        term = record

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

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

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

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

        end;

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

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

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




    Содержание  Назад  Вперед