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

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


Дерево называется бинарным, если каждая вершина имеет не более двух подчиненных (не более двух слуг). Бинарные деревья принято задавать иначе, чем произвольные деревья. Вместо ссылок от вершины “вниз” и “вправо” структура дерева задается ссылками к первому (“левому”) и второму (“правому”) слуге данного хозяина. Если один или оба слуги отсутствуют, соответствующие ссылки равны Nil. Путь на бинарном дереве от корня до любой вершины кодируется последовательностью нулей и единиц: нуль соответствует переходу к левому слуге, а единица - к правому. Классификация с помощью бинарного дерева называется бинарной классификацией.

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

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

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

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


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


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

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



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

      type

          pterm = ^term;

          term = record

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

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

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

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

          end;

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

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

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



                                                                               нет

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

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

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

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

                            да                           нет                                                  да                       нет

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

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

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

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

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

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

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

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

                            да                           нет                                                               да                       нет

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

              слугу текущим       качестве правого слуги              слугу текущим          качестве правого слуги

      Более сложно устроены другие процедуры: переход к следующей и предыдущей записи, составление списка записей в возрастающем порядке, удаление вершины из индексного дерева и т.д.Мы не будем приводить их здесь. Фактически базы данных, как и индексы баз данных, размещаются в файлах. Запись файла индекса базы данных имеет те же четыре компоненты, что были указаны выше. Роль ссылки на запись базы данных играет порядковый номер записи в файле базы данных. Роль ссылки на вершину дерева индекса играет номер записи ? описания вершины индексного дерева в файле индекса базы данных.


      Содержание раздела