Увидеть за лесом деревья

2006 г.

Увидеть за лесом деревья

George Judkin, Королевство Delphi

Постановка задачи
Простое дерево
Фиксированное дерево
Неограниченное дерево
Пример реализации
Ответы на предполагаемые часто задаваемые вопросы

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

Так как задача не была критичной, то я не просиживал ночи напролет, пытаясь ее решить, а просто возвращался к ней время от времени, когда хотелось поразмять мозги. И, в конце концов, что-то напридумывал. Этими придумками я и хочу поделиться.

На кого рассчитана данная статья? В основном, на программистов, которые более-менее знакомы с реляционными базами данных и языком SQL (плюс некоторое знакомство с Delphi), и которые имеют желание совершенствоваться в разработке баз данных. Начинающим, пожалуй, будет тяжеловато, так как я не опускаюсь до деталей. А вот профессионалы, возможно, найдут для себя кое-что интересное.

Постановка задачи

В этой статье я рассматриваю несколько различных вариантов представления деревьев в базах данных, то есть структуры таблиц и реализацию некоторых операций по работе с деревьями через SQL-запросы к этим таблицам. Подчеркиваю, что речь идет о структуре данных и об операциях обработки. Вопросы написания компонент для представления деревьев здесь не рассматриваются.

Сразу уточню кое-какие моменты: эта статья написана для показа идеи, но не реализации. Отсюда несколько следствий. Я по возможности старался использовать максимально простые запросы, ориентируясь на Local SQL. Это сделано специально, чтобы идея была понятна как можно большему числу читателей. Если начать использовать более оптимальные конструкции, характерные для какой-либо продвинутой СУБД, это может привести к сложностям понимания для людей, работающих с другой СУБД. По той же причине вся программная обработка запросов в примерах написана на Delphi (то есть на стороне клиента), хотя на практике это лучше реализовать на сервере через хранимые процедуры и триггеры. Также в некоторых местах я, возможно, упускаю особенности обработки данных в некоторых экстремальных условиях (добавление первой записи в пустую таблицу, удаление последней записи из таблицы). Просто чтобы не загромождать код примера обработкой различных вариантов, которые усложнят понимание той самой идеи.

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

unit SpecialFunctions;

interface

uses
  DBTables;

{Процедура выводит узел с идентификатором ID,
текстом Name и уровнем номер Level}
procedure OutNode(ID,Level : Integer; const Name : String);


{Функция создает запрос с текстом, переданным через StrSQL,
открывает и возвращает его. Подразумевается запрос SELECT}
function OpenQuery(const StrSQL : String) : TQuery;


{Процедура выполняет запросы UPDATE, INSERT и DELETE,
текст которых передан через StrSQL}
procedure ExecQuery(const StrSQL : String);


{Функция возвращает идентификатор последней записи,
добавленной через запрос INSERT}
function LastInsertID : Integer;

Используя процедуру OutNode, мы последовательно выводим узлы дерева. Как и куда будут выводиться эти узлы, не важно. Параметр Level определяет уровень узла (для древовидного отображения). Предполагается также, что запросы, полученные от функции OpenQuery, автоматически уничтожаются, после использования. Чтобы не загромождать код вызовом метода Free, обработкой исключений и прочими деталями, не представляющими сейчас интереса.

В статье рассматриваются три варианта представления деревьев. Для каждого из них приведены реализации пяти операций, которые показались мне наиболее необходимыми. Вот эти операции:

{Процедура выводит поддерево, начиная с узла Root (нижнее замыкание).
Для вывода используется вспомогательная процедура OutNode.
Как и куда осуществляется вывод, не важно)
procedure OutTree(Root : Integer);

{Процедура добавляет узел с названием Name, делая его потомком узла Parent.}
procedure AddNode(Parent : Integer; const Name : String);



{Процедура удаляет поддерево, начиная с узла Node}
procedure DeleteNode(Node : Integer);

{Функция возвращает true, если узел Node находится в поддереве узла Parent.
Данная функция необходима для проверки того, можно ли изменить структуру
дерева и сделать узел Parent потомком узла Node. Если проверку не проводить,
то возможно появление циклов, которые в дереве недопустимы.}
function NodeInSubtree(Node,Parent : Integer) : Boolean;

{Процедура изменяет структуру дерева, назначая узел Parent родителем узла Node.}
procedure SetParent(Node,Parent : Integer);

Простое дерево

Наиболее простой и распространенный способ представления деревьев в базах данных состоит из одной таблицы примерно следующей структуры:

Таблица MainTable

Название поля Тип поля Комментарий

ID Autoincrement Первичный ключ

ParentID Integer Ссылка на родительский узел

Name Char Название узла

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

procedure OutTree(Root : Integer);
var
  L : Integer;

  procedure MakeLevel(ParentID : Integer; const ParentName : String);
  var

    S : String;
    Q : TQuery;
  begin
    OutNode(ParentID,L,ParentName);
    Inc(L);
    S:='SELECT ID,Name FROM MainTable WHERE ParentID=%d ORDER BY ID';
    Q:=OpenQuery(Format(S,[ParentID]));
    while NOT Q.Eof do

      begin
      MakeLevel(Q.FieldByName('ID').AsInteger,Q.FieldByName('Name').AsString);
      Q.Next;
      end;
    Dec(L);
  end;

begin
  L:=0;
  with OpenQuery('SELECT Name FROM MainTable WHERE ID='+IntToStr(Root)) do

    MakeLevel(Root,FieldByName('Name').AsString);
end;

procedure AddNode(Parent : Integer; const Name : String);
var

  S : String;

begin
  S:='INSERT INTO MainTable (ParentID,Name) VALUES (%d,"%s")';
  ExecQuery(Format(S,[Parent,Name]));
end;

procedure DeleteNode(Node : Integer);

  procedure DeleteLevel(Parent : Integer);
  var

    S : String;
    Q : TQuery;
  begin

    S:='SELECT ID FROM MainTable WHERE ParentID=%d';
    Q:=OpenQuery(Format(S,[Parent]));
    while NOT Q.Eof do

      begin
      DeleteLevel(Q.FieldByName('ID').AsInteger);
      Q.Next;
      end;
    S:='DELETE FROM MainTable WHERE ID=%d';
    ExecQuery(Format(S,[Parent]));
  end;


begin
  DeleteLevel(Node);

end;

function NodeInSubtree(Node,Parent : Integer) : Boolean;
var
  S : String;
  Q : TQuery;
begin

  Result:=false;  
  while Node <> Parent do

    begin
    S:='SELECT ParentID FROM MainTable WHERE ID=%d';
    Q:=OpenQuery(Format(S,[Node]));
    Node:=Q.FieldByName('ParentID').AsInteger;
    if Node = 0 then Exit;
    end;
  Result:=true;


end;

procedure SetParent(Node,Parent : Integer);
var
  S : String;
begin
  S:='UPDATE MainTable SET ParentID=%d WHERE ID=%d';
  ExecQuery(Format(S,[Parent,Node]));


end;

При такой организации дерева, только добавление нового узла и назначение узлу нового родителя (то есть операции, для выполнения которых знание структуры дерева не требуется) реализуются достаточно эффективно. А вывод дерева и удаление поддерева требуют рекурсивной обработки. Проверка вхождения узла в поддерево хотя и реализуется без рекурсии, однако количество вызовов запросов также зависит от структуры дерева (от глубины, если быть точнее), что не является эффективным. Надо попробовать другие варианты представления дерева.

Фиксированное дерево

Для того чтобы устранить недостатки простого дерева, нужно иметь указатель не только на непосредственного предка, но и на всех остальных предков выше по иерархии. Если максимальная глубина дерева ограничена, то это можно сделать в той же самой таблице путем введения дополнительных полей-ссылок. Если еще добавить поле для хранения уровня узла (что поможет в реализации операций с деревом), то получим следующую структуру (в данном случае максимальная глубина дерева равна 5):

Таблица MainTable

Название поля Тип поля Комментарий

ID Autoincrement Первичный ключ

Lev Integer Уровень текущего узла

Parent1 Integer Ссылка на родителя 1-го уровня (корень)

Parent2 Integer Ссылка на родителя 2-го уровня

Parent3 Integer Ссылка на родителя 3-го уровня

Parent4 Integer Ссылка на родителя 4-го уровня

Parent5 Integer Ссылка на родителя 5-го уровня

Name Char Название узла

Поле Lev может принимать значения от 1 (корень дерева) до 5 (узел максимально возможной глубины). Значение поля ParentN для любого N равно:

значению первичного ключа предка уровня N (при N < Lev);
значению первичного ключа текущего узла (при N = Lev);
0 (при N > Lev).

{GetLevel -- вспомогательная функция, которая возвращает уровень узла Node.
Выделена для упрощения реализации основных процедур.}
function GetLevel(Node : Integer) : Integer;
begin
  with OpenQuery(Format('SELECT Lev FROM MainTable WHERE ID='+IntToStr(Node))) do
    Result:=Fields[0].AsInteger;


end;

procedure OutTree(Root : Integer);
var
  S : String;
  Q : TQuery;
  L : Integer;
begin
  L:=GetLevel(Root);
  S:='SELECT * FROM MainTable WHERE Parent%d=%d '+
     'ORDER BY Parent1,Parent2,Parent3,Parent4,Parent5';
  Q:=OpenQuery(Format(S,[L,Root]));
  while NOT Q.Eof do

    begin
    OutNode(Q.FieldByName('ID').AsInteger,
            Q.FieldByName('Lev').AsInteger-L,
            Q.FieldByName('Name').AsString);
    Q.Next;
    end;
end;

procedure AddNode(Parent : Integer; const Name : String);


var
  S : String;
  L : Integer;
begin
  L:=GetLevel(Parent);
  if L >= 5 then Exit;
  // Следующий запрос не будет работать в Local SQL.

  S:='INSERT INTO MainTable (Lev,Parent1,Parent2,Parent3,Parent4,Parent5,Name) '+
     'SELECT Lev+1,Parent1,Parent2,Parent3,Parent4,Parent5,"%s" FROM MainTable '+;
     'WHERE ID=%d';
  ExecQuery(Format(S,[Name,Parent]));
  S:='UPDATE MainTable SET Parent%d=ID WHERE ID=%d';
  ExecQuery(Format(S,[L+1,LastInsertID]));

end;


procedure DeleteNode(Node : Integer);
var
  S : String;
begin
  S:='DELETE FROM MainTable WHERE Parent%d=%d';
  ExecQuery(Format(S,[GetLevel(Node),Node]));

end;


function NodeInSubtree(Node,Parent : Integer) : Boolean;
var
  S : String;
  Q : TQuery;
begin
  S:='SELECT Parent%d FROM MainTable WHERE ID=%d';
  Q:=OpenQuery(Format(S,[GetLevel(Parent),Node]));
  Result:=(Q.Fields[0].AsInteger = Parent);


end;

procedure SetParent(Node,Parent : Integer);
var
  S : String;
  Q : TQuery;
  NodeL,ParentL,dL,i : Integer;

  function DecLevel : String;
  var

    j : Integer;
  begin
    Result:='';
    for j:=NodeL to 5 do

      Result:=Result+Format('Parent%d=Parent%d,',[j-dL,j]);
    for j:=5-dL+1 to 5 do

      Result:=Result+Format('Parent%d=0,',[j]);
    Result:=Result+Format('Lev=Lev-%d,',[dL]);
  end;

  function IncLevel : String;
  var
    DelS : String;
    j : Integer;
  begin

    Result:='';
    DelS:='DELETE FROM MainTable WHERE (Parent%d=%d) AND (Lev>%d)';
    ExecQuery(Format(DelS,[NodeL,Node,5+dL]));
    for j:=5 downto (NodeL-dL) do

      Result:=Result+Format('Parent%d=Parent%d,',[j,j+dL]);
    Result:=Result+Format('Lev=Lev+%d,',[-dL]);
  end;

begin
  NodeL:=GetLevel(Node);
  Q:=OpenQuery(Format('SELECT * FROM MainTable WHERE ID=%d',[Parent]));
  ParentL:=Q.FieldByName('Lev').AsInteger;
  dL:=NodeL-ParentL-1;
  S:='UPDATE MainTable SET ';
  if dL <> 0

  then
    begin
    if dL > 0 then S:=S+DecLevel else S:=S+IncLevel;
    end;
  for i:=1 to ParentL do

    S:=S+Format('Parent%d=%d,',[i,Q.Fields[i+1].AsInteger]);
  S[Length(S)]:=#32;
  ExecQuery(Format(S+'WHERE Parent%d=%d',[NodeL,Node]));
end;

Как видно из приведенных примеров, в реализации всех операций удалось уйти от рекурсии. Количество запросов не зависит ни от количества узлов в дереве, ни от его глубины. Да и сама реализация стала несколько проще за исключением процедуры SetParent. На самом деле в ней не так все страшно, как кажется. Просто я попытался в одну процедуру запихнуть обработку нескольких различных ситуаций, которые, по уму, должны обрабатываться самостоятельно. На всякий случай (если кому-то сложно разбирать мои паскалевские каракули) хочу привести примеры запросов, которые реализуют эту операцию для различных ситуаций (запросы не сработают на Local SQL).

Ситуация 1. При изменении родителя происходит уменьшение уровня узла. Пусть мы узлу Node уровня 3 назначаем родителем узел Parent уровня 1. В результате выполнения операции уровень всех узлов поддерева Node уменьшится на 1.

UPDATE MainTable AS T1,MainTable AS T2


SET T1.Lev=T1.Lev-1,T1.Parent1=T2.Parent1,T1.Parent2=T1.Parent3,
    T1.Parent3=T1.Parent4,T1.Parent4=T1.Parent5,T1.Parent5=0
WHERE (T1.Parent3=Node) AND (T2.ID=Parent);

Ситуация 2. При изменении родителя происходит увеличение уровня узла. Пусть мы узлу Node уровня 2 назначаем родителем узел Parent уровня 2. В результате выполнения операции уровень всех узлов поддерева Node увеличится на 1. Если в поддереве узла Node имеются узлы уровня 5, то они должны быть предварительно удалены, так как выйдут за пределы допустимой глубины дерева.

DELETE FROM MainTable WHERE (Parent2=Node) AND (Lev>=5);

UPDATE MainTable AS T1,MainTable AS T2


SET T1.Parent5=T1.Parent4,T1.Parent4=T1.Parent3,T1.Parent3=T1.Parent2,
    T1.Parent2=T2.Parent2,T1.Parent1=T2.Parent1,T1.Lev=T1.Lev+1
WHERE (T1.Parent2=Node) AND (T2.ID=Parent);

Ситуация 3. При изменении родителя не происходит изменение уровня узла. Пусть мы узлу Node уровня 3 назначаем родителем узел Parent уровня 2. В результате выполнения операции уровень всех узлов поддерева Node не меняется.

UPDATE MainTable AS T1,MainTable AS T2
SET T1.Parent1=T2.Parent1,T1.Parent2=T2.Parent2
WHERE (T1.Parent2=Node) AND (T2.ID=Parent);

Кстати, фиксированное дерево -- единственный вариант представления дерева, для которого мне удалось в полном объеме решить вставшую изначально проблему: вывести все узлы поддерева в нужном порядке одним запросом.

Неограниченное дерево

Фиксированное дерево очень удобно в работе. Но что делать, если по условию задачи невозможно ограничить максимальную глубину дерева? В этом случае придется задавать отношения между узлами более привычным способом. Родительские и дочерние узлы находятся в отношении many-to-many (каждому родительскому узлу может соответствовать множество дочерних, а каждому дочернему -- множество родительских, начиная с непосредственного предка и кончая корнем всего дерева). В соответствии с теорией, такое отношение реализуется вводом дополнительной таблицы.

Таблица MainTable

Название поля Тип поля Комментарий

ID Autoincrement Первичный ключ

Name Char Название узла

Таблица LinkTable

Название поля Тип поля Комментарий

ParentID Integer Ссылка на родительский узел

ChildID Integer Ссылка на дочерний узел

Distance Integer Расстояние между узлами

Значение поля Distance равно 0, если ParentID и ChildID совпадают. В противном случае оно равно порядковому номеру узла ChildID при движении к нему по дереву от узла ParentID.

procedure OutTree(Root : Integer);
var
  L : Integer;

  procedure MakeLevel(ParentID : Integer; const ParentName : String);
  var

    S : String;
    Q : TQuery;
  begin
    OutNode(ParentID,L,ParentName);
    Inc(L);
    S:='SELECT ID,Name FROM MainTable AS M JOIN LinkTable AS L ON (M.ID=L.ChildID) '+
       'WHERE (L.ParentID=%d) AND (L.Distance=1) ORDER BY ID';
    Q:=OpenQuery(Format(S,[ParentID]));
    while NOT Q.Eof do

      begin
      MakeLevel(Q.FieldByName('ID').AsInteger,Q.FieldByName('Name').AsString);
      Q.Next;
      end;
    Dec(L);
  end;

begin
  L:=0;
  with OpenQuery('SELECT Name FROM MainTable WHERE ID='+IntToStr(Root)) do

    MakeLevel(Root,FieldByName('Name').AsString);
end;

procedure AddNode(Parent : Integer; const Name : String);
var

  S : String;
  NewNode : Integer;

begin
  ExecQuery(Format('INSERT INTO MainTable (Name) VALUES ("%s")',[Name]));
  NewNode:=LastInsertID;
  // Следующий запрос не будет работать в Local SQL.
  S:='INSERT INTO LinkTable (ParentID,ChildID,Distance) '+
     'SELECT ParentID,%d,Distance FROM LinkTable '+
     'WHERE ChildID=%d';
  ExecQuery(Format(S,[NewNode,Parent]));
  S:='INSERT INTO LinkTable (ParentID,ChildID,Distance) VALUES (%d,%0:d,0)';
  ExecQuery(Format(S,[NewNode]));


end;

procedure DeleteNode(Node : Integer);
var
  S : String;
begin
  S:='DELETE FROM MainTable '+
     'WHERE ID IN (SELECT ChildID FROM LinkTable WHERE ParentID=%d)';
  ExecQuery(Format(S,[Node]));
  S:='DELETE FROM LinkTable '+
     'WHERE ChildID IN (SELECT ChildID FROM LinkTable WHERE ParentID=%d)';
  ExecQuery(Format(S,[Node]));


end;

function NodeInSubtree(Node,Parent : Integer) : Boolean;
var
  S : String;
  Q : TQuery;
begin
  S:='SELECT Count(*) FROM LinkTable WHERE (ParentID=%d) AND (ChildID=%d)';
  Q:=OpenQuery(Format(S,[Parent,Node]));
  Result:=(Q.Fields[0].AsInteger > 0);


end;

procedure SetParent(Node,Parent : Integer);
var
  S : String;
  Parents,Subtree : String;
begin
  Parents:=Format('SELECT ParentID FROM LinkTable '+
                  'WHERE (ChildID=%d) AND (ParentID<>%0:d)',[Node]);
  Subtree:=Format('SELECT ChildID FROM LinkTable '+
                  'WHERE ParentID=%d',[Node]);
  S:='DELETE FROM LinkTable '+
     'WHERE (ParentID IN ('+Parents+')) AND (ChildID IN ('+Subtree+'))';
  ExecQuery(S);
  // Следующий запрос не будет работать в Local SQL.

  S:='INSERT INTO LinkTable (ParentID,ChildID,Distance) '+
     'SELECT T1.ParentID,T2.ChildID,T1.Distance+T2.Distance+1 '+
     'FROM LinkTable AS T1,LinkTable AS T2 '+
     'WHERE (T1.ChildID=%d) AND (T2.ParentID=%d)';
  ExecQuery(Format(S,[Parent,Node]));
end;

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

Сравнительный анализ

Проведем небольшой сравнительный анализ различных вариантов представления дерева с точки зрения качества реализации рассмотренных в статье операций. Будем считать, что операция реализуется хорошо, если количество запросов для реализации не зависит от характеристик дерева (количества узлов, глубины и др.). Если же зависимость есть, то будем считать, что операция реализуется плохо.

№ п/п Операция Варианты дерева

Простое Фиксированное Неограниченное

1 Вывод дерева плохо хорошо плохо

2 Добавление узла хорошо хорошо хорошо

3 Удаление узла плохо хорошо хорошо

4 Вхождение узла в поддерево плохо хорошо хорошо

5 Изменение родителя хорошо хорошо хорошо

Из таблицы видно, что простое дерево слабо годится для работы с ним на уровне БД. Только две операции из пяти будут выполняться эффективно. Но так как для изменения родителя нужно сначала определить, допустимо ли такое изменение, а операция проверки вхождения узла в поддерево также реализуется плохо, то остается одно лишь добавление нового узла. Для задачи, в которой в основном выполняется только операция добавления нового узла, а остальные операции выполняются крайне редко, такой вариант подойдет. Но я как-то слабо могу себе представить такую задачу (ведение древовидных логов что ли?). Так что применять простое дерево имеет смысл для сравнительно небольших деревьев, которые выгружаются из БД в какие-либо компоненты (например, TTreeView), а вся дальнейшая работа производится уже на уровне компонентов.

Для фиксированного дерева все операции реализуются хорошо. Так что, если по условиям задачи допустимо ограничить максимальную глубину дерева, то, возможно, это будет лучший вариант (если не будет придуман способ хорошей реализации вывода неограниченного дерева). Имейте в виду, что максимальную глубину для фиксированного дерева можно задать и побольше, чем 5. Можно взять с запасом. Главное -- чтобы глубину можно было хоть как-то ограничить.

Ну, а если таких ограничений задать невозможно (или если скорость вывода не критична), то можно воспользоваться вариантом неограниченного дерева.

Пример реализации

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

Программа достаточно проста. В выпадающем списке выбираем тип дерева и по данным из БД соответствующее дерево строится на главной панели (слегка модифицированный ListBox). Операции по изменению дерева выполняются из контекстного меню. Обращаю внимание, что команды относятся к текущему узлу дерева (выделенному цветом), а не к тому, над которым произведен клик мышью. Если текущего узла нет, то операции невозможны. Операция изменения родителя вызывается методом Drag and Drop (берем мышью узел и перетаскиваем его на нового родителя). Для вывода поддерева, начиная с некоторого узла, можно выполнить Double Click на этом узле. Обратного перехода (или возможности подняться выше по дереву) нет. Чтобы от поддерева вернуться к полному дереву, нужно снова выбрать дерево того же типа из выпадающего списка типов.

Все три дерева хранятся в БД на Paradox 7. Это было сделано, чтобы обеспечить максимальную совместимость с программным обеспечением всех желающих попробовать программу: не уверен, что у каждого жителя Королевства имеется на компьютере Oracle или MS SQL, но уж BDE наверняка проинсталлировали все. Для работы программы файлы БД должны находится в директории DATA, которая, в свою очередь, должна находится там же, где и исполняемый файл (DBTree.exe). База данных уже частично заполнена. Все необходимый файлы содержатся в том же архиве, что и исходники программы. На случай, если у кого-то возникнут проблемы с компиляцией (а побаловаться с программой захочется), в отдельном архиве выкладываю скомпилированный EXE-файл.

И еще, программа является довеском к статье, но никак не предметом рассмотрения. Отсюда несколько следствий. Во-первых, хотя я и старался писать код поаккуратнее, но вот комментариями, мягко выражаясь, не злоупотреблял. Так что возможны трудности при разборках с исходниками. Во-вторых, это все же не законченный программный продукт, ориентированный на конечного пользователя, а маленькая демонстрашка. Так что в ней не реализована в полной мере противодураковая защита. Заранее известные глюки: не проверяется длинна строки для имени узла (максимальное значение не должно быть более 40 символов), под первичный ключ отводится всего 16 бит (если попытаться создавать более 32767 узлов, то возникнут глюки), под последним добавленным узлом понимается узел с максимальным значением первичного ключа (возможны сбои при работе в многопользовательском режиме). Так что погонять дерево туда-сюда можно, но серьезно насиловать программу не стоит. Она для этого не предназначена.

Ответы на предполагаемые часто задаваемые вопросы

1. Я скопировал кусок кода из статьи к себе в программу, после чего... (компилятор выдал ошибку, запрос не выполняется, компьютер виснет).

Не копируйте код из статьи. Если хочется что-нибудь скопировать, то скачайте исходники демонстрационной программы и копируйте оттуда ;-)

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

Тысяча извинений. Термины Простое Дерево, Фиксированное Дерево и Неограниченное Дерево не являются общеупотребительными. Я их придумал для данной статьи, чтобы как-то называть различные варианты представления деревьев, которые я рассматриваю.

3. Не кажется ли Вам, что использование других вариантов представления (отличных от простого дерева) -- это избыточные затраты дискового пространства?

Нет, не кажется. Если Вы взялись за базы данных, то Вы заведомо приняли решение пожертвовать эффективностью использования дискового пространства ради повышения быстродействия обработки больших объемов данных. Например, в демонстрационной программе я отвел под название узла 40 символов, хотя при тестировании не использовал названий длиннее 10 символов. Итого, таблица на 75% состоит из "воздуха". Если Вас заботит дисковое пространство, то вместо баз данных используйте, например, формат Tab Delimited Text и будет Вам счастье ;-)

4. Приведенные структуры ... (недостаточны, неоптимальны). Будет лучше сделать...

Делайте ;-)

5. Почему Вы не используете параметры в запросах? Ведь это более правильно.

Есть два варианта ответа: короткий и длинный. Короткий: мне показалось, что так будет нагляднее. Длинный приводить не буду, чтобы не раздувать размер статьи.

6. Зачем вообще нужны эти хитрые структуры, ведь сервер СУБД оптимизирует выполнение хранимых процедур?

Если сервер СУБД действительно умеет оптимизировать хранимые процедуры, в которых выполняются рекурсивные вызовы запросов, то данная статья представляет исключительно академический интерес.

7. Вывод всего дерева целиком в реальных задачах не требуется.

Если этот так, то значит Вы и я всего лишь напрасно потратили время ;-)

И еще несколько слов, если можно. В процессе работы над статьей, я решил поискать по Королевству другие материалы аналогичной тематики. Статей похожих мне не попалось (может быть, плохо искал?), а вот на Круглом Столе я обнаружил ответы Елены Филипповой на один из вопросов (http://www.delphikingdom.com/asp/answer.asp?IDAnswer=29168). Приятно видеть, что два умных человека могут независимо прийти к одним и тем же выводам ;-) Кстати, одну небольшую идейку я у Елены украл (так как ее вариант показался мне более интересным) в чем готов принародно покаяться.

Специально для Королевства Delphi

К материалу прилагаются файлы:

Исполняемый файл (342 K) обновление от 5/4/2006 5:24:00 AM
Исходные коды (9 K) обновление от 5/4/2006 5:24:00 AM