Структура sql таблицы для хранения дерева папок
Обновлено: 18.09.2024
Сегодня большинство хранилищ данных, как простых так и сложных, построены на основе реляционных баз данных. В них используются либо файл-серверные системы (dBase, Paradox, Clipper, FoxPro, Access), либо SQL-серверы (Oracle, Informix, Sybase, Borland InterBase, MS SQL и т. д.). Реляционные базы данных в большинстве случаев удовлетворяют требования какой-либо предметной области данных, но часты и случаи когда требуется представление и хранение данных в иерархическом виде. Варианты построения таких представлений в реляционной модели и будут рассмотрены в данной статье.
Используемые инструменты
В качестве инструмента разработки клиентского приложения в данной статье применяется Delphi, а в качестве SQL-сервера – Borland InterBase SQL Server 4.x. На самом деле для теоретической части статьи это несущественно, а практическая часть содержит минимум специфики использования указанных инструментов.
Таблицы-объекты
Для того, чтобы подойти к построению "деревьев", мы должны рассмотреть, что представляет собой реляционная таблица.
Рис. 1
Таблица имеет структуру, т. е. состоит из полей, описывающих характеристики некоего объекта, например, "Человек". Записи такой таблицы (можно назвать ее "Люди") представляют собой характеристики экземпляров объектов одного и того же типа. Идентификатор позволяет найти среди множества экземпляров один экземпляр требуемого типа.
Однотипные связанные объекты
Предположим что мы действительно хотим создать таблицу "Люди", в которой нужно отслеживать родственные связи типа родитель-потомок. Для простоты представим себе, что у потомков родитель может быть только один (например, "Родитель"):
Рис. 2
Для того, чтобы хранить информацию о родителе экземпляра объекта, любой объект в таблице должен помимо идентификатора иметь атрибут "родитель". На рисунке видно, что все "Потомки" имеют родителя, кроме самого "Родитель1". Экземпляр "Родитель1" может в принципе вообще отсутствовать – можно принять что у потомков первого уровня всегда один и тот же родитель, поэтому хранить информацию о нем необязательно (в каких случаях это необходимо, мы рассмотрим дальше).
Читатель может заметить – а как же множественное наследование? А никак. В природе такового не существует – все объекты реального мира являются или цельными, или составными. Множественное наследование было создано только как методика проектирования классов, когда разработчик не обладает полной информацией о самих классах. Автор статьи считает, что множественное наследование только запутывает реализацию прикладной области. Например, в ряде книг приводится случай, когда объект "тесто" получается множественным наследованием объектов "вода" и "мука". На самом деле это не так – даже при диффузии отдельные материалы все равно остаются сами собой, т. е. в данном случае мы имеем совершенно новый объект "тесто", который имеет среди атрибутов указатели на два класса – "тесто" и "вода" (или список составляющих "тесто" классов, как угодно). Характеристики "теста" при этом зависят не только от состава "воды" и "муки", но и от их процентного соотношения. То же самое относится и к биологическому "рождению" – ребенок наследует свойства родителей, т. е. их наборы хромосом, и представляет собой типичный составной объект при отсутствии какого бы то ни было множественного наследования. Конечно, множественное наследование в редких случаях облегчает программирование, однако это не значит, что оно отражает суть реальных вещей, которые можно описать в программе.
Итак, структура нашей "родовитой" таблицы будет выглядеть следующим образом:
Рис. 3
Поле "Родитель" всегда ссылается на значение поля "Идентификатор". Здесь нас поджидает подводный камень – если бы мы решили, что "…ссылается на существующее значение поля…", и в соответствии с реляционными правилами объявили-бы связь конструкцией SQL "alter table … add constraint … foreign key", то попали-бы в замкнутый круг "курица и яйцо". Как создать экземпляр объекта если родителя нет? Действительно, может-ли существовать экземпляр объекта без указания родителя? Чтобы избавиться на начальном этапе хотя-бы от первого вопроса, нужно отказаться от декларации связи Родитель->Идентификатор на уровне сервера. Это снизит защищенность данных, но избавит нас от долгих раздумий в самом начале пути. На второй вопрос (может-ли существовать экземпляр без родителя) можно безболезненно ответить "нет", установив ограничение целостности для поля "Родитель" как "значение обязательно" (NOT NULL).
Поскольку мы отказались от создания FK, по полю "родитель" не будет автоматически построен индекс, который был бы нужен оптимизатору для ускорения запросов, выбирающих группы потомков для конкретного родителя. Не забудьте добавить такой индекс потом, вручную.
Давайте теперь посмотрим, как будет выглядеть таблица, заполненная экземплярами объектов с рисунка 2:
| Идентификатор | Родитель | Остальные атрибуты … |
|---|---|---|
| Родитель1 | . | |
| Потомок1 | Родитель1 | |
| Потомок2 | Родитель1 | |
| Потомок3 | Потомок1 |
Такую таблицу можно создать конструкцией SQL:
CREATE TABLE OBJECTS(
ID INTEGER NOT NULL,
PARENT INTEGER NOT NULL,
NAME VARCHAR(30),
constraint PK_OBJECTS primary key (ID))
Пусть идентификаторы экземпляров объектов будут начинаться с номера 1. Тогда родителем экземпляра "Родитель1" можно принять значение 0 (корневой элемент). Фактически экземпляров с родителем = 0 может быть сколько угодно, и именно они будут представлять "корень" нашего дерева. Названия экземпляров пусть находятся в поле "NAME". Пронумеруем идентификаторы экземпляров объектов. В этом случае таблица будет иметь вид
| ID | PARENT | NAME |
|---|---|---|
| 1 | 0 | Родитель1 |
| 2 | 1 | Потомок1 |
| 3 | 1 | Потомок2 |
| 4 | 2 | Потомок3 |
Теперь, для того чтобы получить всех потомков например экземпляра "Родитель1", нужно использовать его ID в том же самом запросе как идентификатор родителя:
Представить такую информацию можно в виде "каталогов" и "файлов", например, как в Windows Explorer. Щелчок мыши по каталогу приводит к "проваливанию" на более глубокий уровень, и т. д.
Конечно, для того чтобы иметь возможность вернуться назад по дереву нужно в приложении хранить "список возврата", т. е. список элементов, по которым мы углубились внутрь, с идентификаторами их владельцев (своеобразный "стек"). С другой стороны, нужно иметь возможность выбрать весь путь вплоть до корня начиная с произвольного элемента. Это можно сделать написав хранимую процедуру (если ваш SQL-сервер поддерживает стандарт ANSI SQL 3 в части хранимых процедур (PSM) и позволяет из хранимых процедур возвращать наборы записей). Вот как выглядит такая процедура для InterBase:
CREATE PROCEDURE GETPARENTS (ID INTEGER)
RETURNS (DID INTEGER, OID INTEGER, NAME VARCHAR(30))
AS
BEGIN
WHILE (:ID > 0) DO /* ищем до корня */
BEGIN
SELECT O.ID, O.PARENT, O.NAME
FROM OBJECTS O
WHERE O.ID = :ID
INTO :DID, :OID, :NAME;
/* код родителя для следующей выборки */
SUSPEND;
END
END
В процедуру передается идентификатор, с которого нужно подниматься “вверх” по дереву. В цикле, пока идентификатор не стал равным 0 (не поднялись выше корневого элемента) происходит выборка записи с указанным идентификатором, затем идентификатор меняется на идентификатор родителя.
Выполнение этой процедуры для наших данных привело бы к следующему результату (запрос SELECT * FROM GETPARENTS 4):
Соединяя поля "NAME" справа налево мы получим полный "путь" от текущего элемента до корня: “Родитель1/Потомок2/Потомок3”. Этот путь можно использовать либо для показа пользователю, либо для внутренних целей приложения.
Визуализация древовидной структуры
Для визуализации подобной структуры можно воспользоваться компонентом TTreeView, поставляемым в Delphi 2.0 и 3.0. Этот компонент формирует представление типа "outline" при помощи объектов TTreeNode. К сожалению, с этим типом объекта работать не очень удобно, поскольку он произведен от стандартного элемента GUI и при разработке нельзя использовать наследование. Для хранения дополнительных данных узла дерева приходится использовать поле TTreeNode.Data, представляющее собой указатель на произвольный объект или структуру данных.
Рис. 4
При отображении небольшого количества записей (до 1000) можно считывать в память всю таблицу и формировать TTreeView в памяти, не обращаясь затем к базе данных. Однако если нужно периодически перечитывать "дерево", то такой подход будет слишком медленным. Оптимальным было бы перечитывание только раскрываемой ветви дерева. При этом перечитывание будет происходить максимально быстро, т. к. даже самая сложная древовидная структура содержит максимум 200-500 элементов в одной ветви.
Для реализации перечитывания записей по "распахиванию" ветви дерева можно использовать приведенный выше запрос с выборкой элементов одной ветви.
procedure TMainForm.NodeViewExpanding(Sender: TObject; Node: TTreeNode;
var AllowExpansion: Boolean);
begin
GetExpandingItems(Node);
end;
procedure TMainForm.GetExpandingItems(var Node: TTreeNode)
var NewNode: TTreeNode;
begin
< если не передан "раскрываемый" узел, то это самый первый узел.
иначе нужно в качестве Parent передать в запрос идентификатор
элемента, который мы не совсем корректно будем хранить в
Node.Data как целое число, а не как указатель на структуру данных>
if Node = nil then
Query1.ParamByName('Parent').asInteger:=0
else
begin
Query1.ParamByName('Parent').asInteger:=integer(Node.Data);
Node.DeleteChildren; < удалить "подэлементы" если они были >
end;
Query1.Open;
Query1.First;
while not Query1.EOF do
begin
NewNode:=TreeView1.Items.AddChildObject(Query1.FieldByName('NAME').asString)
integer(NewNode.Data):=Query1.FieldByName('ID').asInteger;
Query1.Next;
end;
Query.Close;
end;
После выполнения этой функции создаются элементы, дочерние для указанного Node, или корневые элементы, если Node=nil.
Однако в этом случае структура данных таблицы OBJECTS не дает нам возможности узнать (без дополнительного запроса) есть ли у элемента его "подэлементы". И TreeView для всех элементов не будет показывать признак “раскрываемости” или значок “+”.
Для этих целей без расширения нашей структуры данных не обойтись. Очевидно необходимо добавить в таблицу OBJECTS поле, которое будет содержать количество дочерних элементов (0 или больше). Такое поле можно добавить
Но кто будет модифицировать это поле, записывая туда новое количество дочерних элементов? Можно, конечно, делать это и из клиентского приложения. Однако самым правильным решением будет добавление триггеров на вставку, изменение и удаление записей в таблице OBJECTS.
Триггер по вставке записи должен увеличить количество "детей" у своего родителя:
CREATE TRIGGER TBI_OBJECTS FOR OBJECTS
ACTIVE BEFORE INSERT POSITION 0
AS
BEGIN
UPDATE OBJECTS O
SET O.CCOUNT = O.CCOUNT + 1
WHERE O.ID = new.PARENT;
END
Триггер по изменению проверяет, не меняется ли родитель элемента. Если да, то значит элемент перемещается от одного родителя к другому и нужно соответственно уменьшить CCOUNT у старого и увеличить у нового.
CREATE TRIGGER TBU_OBJECTS FOR OBJECTS
ACTIVE BEFORE UPDATE POSITION 0
AS
BEGIN
if (old.PARENT <> new.PARENT) then
begin
UPDATE OBJECTS O SET O.CCOUNT = O.CCOUNT - 1
WHERE O.ID = old.PARENT;
UPDATE OBJECTS O SET O.CCOUNT = O.CCOUNT + 1
WHERE O.ID = new.PARENT;
end
END
CREATE TRIGGER TBD_OBJECTS FOR OBJECTS
ACTIVE BEFORE DELETE POSITION 0
AS
BEGIN
UPDATE OBJECTS O
SET O.CCOUNT = O.CCOUNT - 1
WHERE O.ID = old.PARENT;
END
(Обратите внимание, что во всех триггерах при обращении к таблице используетс псевдоним O, а для полей в триггере используется уточнитель new. или old. Это сделано для того, чтобы SQL-сервер не перепутал изменяемые поля в UPDATE и поля таблицы в контексте триггера).
Теперь таблица OBJECTS полностью автоматически отслеживает количество "детей" у каждого элемента.
Для того чтобы TTreeNode "знал" о наличии у него детей, поле Data должно уже указывать на некую структуру данных. Нам нужно хранить идентификатор узла, на всякий случай идентификатор родителя, и количество дочерних записей, а текст (NAME) можно хранить в TTreeNode, как это сделано в приведенном выше примере. Итак, создадим дополнительную структуру:
.
var R: PItemRec;
.
NewNode:=TreeView1.Items.AddChildObject(Query1.FieldByName('NAME').asString);
New(R);
NewNode.Data:=R;
R^.Id:=Query1.FieldByName('ID').asInteger;
R^.Parent:=Query1.FieldByName('PARENT').asInteger;
R^.CCount:=Query1.FieldByName('CCOUNT').asInteger;
NewNode.HasChildren:=R^.CCount > 0;
.
(Для того чтобы правильно освобождать память, занимаемую операцией New(R), необходимо в методе TTreeView.OnDeletion написать одну строку – Dispose(PItemRec(Node.Data); Это освободит занятую память при удалении любого элемента TTreeNode или группы элементов).
Свойство HasChildren приведет к автоматической прорисовке значка "+" в TreeView у элемента, который имеет дочерние элементы. Таким образом мы получаем представление дерева без необходимости считывать все его элементы сразу.
Древовидные структуры данных являются одним из способов представления иерархической структуры и встречаются во многих предметных областях. Данная статья на простом примере рассматривает четыре наиболее популярных способа представления деревьев в реляционной базе данных.
Представление и хранение данных в виде дерева - часто встречающаяся задача в разработке программного обеспечения:
Древовидные структуры данных являются одним из способов представления иерархической структуры и встречаются во многих предметных областях:
- двоичное дерево в информатике,
- филогенетическое дерево в биологии,
- финансовая пирамида в бизнесе,
- структура декомпозиции работ в управлении проектами;
- с помощью деревьев моделируют многоуровневые связи вида “главный - подчиненный”, “предок - потомок”, “целое - часть”, “общее - частное”.
Рассмотрим четыре наиболее популярных способа хранения деревьев в реляционной базе данных. В качестве примера возьмем каталог строительных материалов (рис. 1) и СУБД Postgres 9.6.
Рис 1. Каталог строительных материалов.
В теории графов деревом называется связный граф без циклов, в то время как лесом называется произвольный граф (возможно, несвязный) без циклов. Описываемые в данной статье методы могут без ограничения общности применяться для хранения как деревьев, так и лесов.
1. Список смежности (Adjacency List)
В теории графов списки смежности - один из способов представления графа, в котором для каждой вершины хранится список смежных с ней вершин. В случае дерева, если рассматривать все ребра как направленные от дочерних вершин к родительским, такие списки вырождаются в единственное значение, которое можно хранить вместе с самой вершиной. Этот способ хранения является самым часто встречающимся и интуитивно понятным: таблица ссылается сама на себя (рис. 2). Корневые узлы записываются с пустой ссылкой на предка ( NULL ).
Рис. 2. Использование списка смежности
В этом способе для выполнения наиболее популярных выборок данных требуется поддержка рекурсивных запросов. PostgreSQL поддерживает такой вид запросов, в случае, если СУБД их не поддерживает, то выборки придется строить с помощью временных таблиц и хранимых процедур. Рассмотрим примеры запросов.
Выборка поддерева по заданному узлу:
Путь к узлу от корня:
Проверка, входит ли узел дерева Cement (code=5) в Construction Material/Fixtures(code=1):
Преимуществами этого метода являются:
- интуитивное представление данных (пары значений code, parent_code однозначно соответствуют ребрам дерева);
- при использовании списка смежности нет избыточности хранения, не требуется дополнительная поддержка целостности, кроме ссылочной (и, при необходимости, для предотвращения возникновения циклов);
- уровень вложенности дерева не ограничен;
- быстрые и простые операции вставки, перемещения и удаления узлов дерева, так как они не требуют изменений других узлов дерева.
К недостаткам можно отнести:
- необходимость использовать рекурсию для выборки всех потомков или предков узла, определения его уровня и количества потомков; данный способ хранения требует поддержки специфических функций СУБД и не может быть реализован эффективно в том случае, если СУБД такие функции не поддерживает. В случаях, когда использование рекурсии является невозможным или непроизводительным, часть преимуществ списка смежности может быть достигнута при помощи одноуровневой таблицы (flat table).
2. Подмножества (Subsets)
Также closure table (таблица связей) или bridge table (соединительная таблица).
В этом способе хранения дерево представляется в виде вложенных подмножеств, корневой узел содержит в себе все подмножества первого уровня, которые в свою очередь включают подмножества второго уровня, и так далее (рис. 3).
Рис 3. Представление дерева в виде вложенных подмножеств
Для хранения дерева таким способом понадобятся две таблицы: в одну таблицу записываются все подмножества (таблица goods_category , рис. 4), во вторую - список вхождений каждого подмножества в другие, а также их уровни (таблица subset , рис. 4).
Рис. 4. Использование подмножеств
Таким образом, для каждого нового узла в таблицу subset необходимо добавить количество записей, равное уровню вложенности этого узла. Нетрудно заметить, что количество записей растет в арифметической прогрессии, но и типовые запросы становятся короче и работают быстрее, чем в предыдущем способе.
Выборка поддерева по заданному узлу:
Путь к узлу от корня
Проверка, входит ли Blocks (code=3) в Construction Material/Fixtures(code=1):
При перемещении или вставке узла целостность данных сохраняется за счет триггеров, которые перезаписывают связанные с изменяемым узлом записи.
Главное достоинство метода подмножеств - быстрые, простые, не рекурсивные операции с деревом: выборка поддерева, всех предков узла, определение количества потомков узла и его уровня.
К недостаткам относятся:
- относительно неинтуитивное представление данных (восприятие усложняется из-за наличия избыточных связей между непрямыми потомками),
- избыточность хранения,
- использование триггеров для поддержки целостности данных;
- операции перемещения и вставки узлов в методе подмножеств сложнее, чем при использовании таблицы смежности. Для вставки нового узла придется добавить новые записи для всех его дочерних узлов, а при перемещении узла придется обновить записи у его предков и потомков.
3. Вложенные множества (Nested sets)
Идея этого метода заключается в хранении маршрута обхода дерева в префиксном порядке. В этом случае сначала посещается корень дерева, затем узлы левого поддерева в префиксном порядке, после - узлы правого поддерева также в префиксном порядке. Порядок обхода хранится в двух дополнительных полях left_key и right_key . В поле left_key записывается порядковый номер при входе в поддерево, а в right_key порядковый номер при выходе из поддерева (рис 5). Таким образом, номера потомков всегда располагаются в интервале между соответствующими номерами предка, независимо от их уровня относительно друг друга. Пользуясь этим свойством при составлении типовых запросов к дереву, можно легко обойтись без рекурсии.
Рис. 5 Использование вложенных множеств
Выборка поддерева по заданному узлу:
Путь к узлу от корня:
Проверка, входит ли Blocks (code=3) в Construction Material/Fixtures(code=1):
Положительными сторонами метода вложенных множеств можно назвать быстрые и простые операции выборки всех потомков, предков узла, их количества и уровня без использования рекурсии.
Основная сложность этого способа - необходимость переопределения порядка обхода при добавлении нового или перемещении существующего узла. Так, если добавить новый элемент в самый нижний уровень, то придется обновить поля left_key и right_key у всех узлов, которые находится “правее” и ”выше”, что, фактически, означает пересчет всего маршрута по дереву. Можно сократить количество обновлений маршрута обхода, если нумеровать left_key и right_key с некоторым интервалом, например, вместо “1” и “20” “10 000” и “200 000” соответственно. Это позволит вставить новый узел без полной перенумерации всех последующих. Аналогичным образом можно использовать в качестве left_key и right_key дробные числа.
4. Материализованные пути (Materialized paths)
Также lineage column (столбец преемственности)
Суть метода состоит в том, чтобы хранить полный путь от вершины до узла в явном виде в качестве первичного ключа (рис 6). Материализованные пути являются очень наглядным способом кодирования элементов дерева: каждый узел имеет интуитивно понятное значение, код узла и его части несут смысловую нагрузку. Это свойство является важным для классификаций, предназначенных для широкого пользования, таких как, справочник медицинских диагнозов, универсальная десятичная классификация (УДК), используемая в научных статьях, ее зарубежная коллега PACS (Physics and Astronomy Classification Scheme). Запросы при использовании этого метода выглядят лаконичными, но не всегда эффективны, так как часто используют поиск по подстроке.
Рис. 6 Использование материализованных путей
Выборка поддерева по заданному узлу:
Путь к узлу от корня:
Проверка, входит ли Cement в Construction Material/Fixtures:
В случае, если заранее известно максимальное количество уровней и максимальное число потомков на каждом уровне, можно обойтись без разделителей и использовать числовые коды с фиксированной разбивкой на группы разрядов. Пустые разряды заполняются нулями. Также возможно использование отдельных столбцов для каждого уровня иерархии (multiple lineage columns): при таком подходе пропадает необходимость использовать поиск по подстроке. Подобная схема применяется во многих классификациях, например, ОКАТО, NAICS.
К преимуществам метода материализованных путей можно отнести интуитивность представления данных и простоту типовых запросов.
Недостатками метода являются сложные вставка нового узла дерева перемещение и удаление узла, избыточность хранения, сложность реализации поддержки целостности данных, неэффективные запросы, так как поиск выполняется по подстроке. Если материальные пути не используют разделители, а только числовые коды, то еще одним недостатком будет ограниченность количества уровней дерева.
4.1. Модуль ltree в PostreSQL
Рассмотрим запросы к нашему дереву с ltree:
Установим плагин, создадим таблицу и заполним ее данными:
Выборка поддерева по заданному узлу:
Путь к узлу от корня:
Проверка, входит ли Cement в Construction Material/Fixtures:
Определить количество меток в пути (уровень)
Заключение
Мы рассмотрели четыре популярных способа хранения древовидной структуры в реляционной базе данных. У каждого способа есть как свои достоинства, так и недостатки.
Из четырех методов только у списка смежности нет избыточности, нет необходимости в дополнительной поддержке целостности (кроме ссылочной); вставка и перемещение узлов дерева не затрагивают другие записи в таблице. Однако большинство типовых запросов для списка смежности используют рекурсию.
Для всех остальных рассмотренных способов рекурсия в запросах не требуется, но вставка и перемещение узлов не могут быть выполнены без обновления других, связанных с ними, узлов. Для способов хранения с помощью материализованных путей и вложенных множеств можно применить оптимизацию, хотя она и не убирает всех ограничений этих методов.
На следующих рисунках зеленым цветом условно обозначены данные, хранящиеся в реляционных таблицах, для рассмотренных способов представления иерархических структур.
| Список смежности | Подмножества |
|---|---|
 |  |
| Вложенные множества | Материализованные пути |
|---|---|
 |  |
Для списка смежности и материализованных путей хранимая структура соответствует изначальной структуре в предметной области. Для подмножеств структура усложняется наличием рефлексивных и транзитивных связей между потомками и предками. В случае вложенных множеств хранимые значения имеют весьма опосредованное отношение к изначальной структуре.
ещё такой вопрос. допустим что дерево будет храниться вот так:
id | path |
1 | /root |
2 | /root/docs |
3 | /root/img |
4 | /root/docs/1 |
5 | /lib/obj/ |
6 | /lib |
то есть в колонке path будет храниться полный путь (получается, что тип данных будет примерно TEXT, если дерево большое).
плюс в том, что проверить путь можно всего одним sql-запросом. и получить id тоже можно одним запросом (id соответственно используется в других таблицах чтобы указать принадлежность к директории).
ещё нужно каким-то образом получать листинг директорий, которые находятся в директории с определённым id.
собственно, это все планируемые операции над такой таблицей. Так что интересно узнать насколько подходит такое хранение. И главное, как оно будет по скорости с другими возможными методами
а ещё интересно, если дадите каких-нибудь полезных ссылок, где про это можно почитать. желательно что-нибудь новомодное )
ну наверное стандартно
lft
rght
parent_id
поле path можно рассматривать как некий кэш для того, чтобы не строить каждый раз путь заново при поиске по пути.
nested sets думаю подойдет.
Спокойно одним запросам можно получить
(id, parent_id) или nested set в зависимости от того, как дальше будет использоваться и от движка базы. В случае (id,parent_id) нужно будет делать рекурсивные запросы. В случае nested set все вышеперечисленные операции можно делать одним запросом (кроме получение id по пути вида /path/to/dir, но его можно и хранимой процедурой сделать)
А разумно для удобства хранить отображени реальной ФС сайта в базе? Т.е. как бы данные привязаны по бд, а файл создаются как контроллеры по какому-то грубо говоря шаблону.
Аннотация: Эта лекция посвящена сохранению древовидных структур в базе данных. Вы узнаете, как можно сохранить дерево с неограниченным количеством ветвей в таблицу, и как считать его обратно в компонент TreeView.
Древовидные структуры не относятся напрямую к программированию баз данных, тем не менее, программисту нередко приходится "изобретать велосипед", придумывая различные решения сохранения таких структур в таблице, и обратное их считывание в дерево .
Типичный пример дерева - всем знакомое дерево каталогов. Примеров таких структур множество - это могут быть отделы в каком-либо учреждении или разделы библиотеки. Посмотрим на рисунок с фрагментом дерева разделов библиотеки:
Основная сложность хранения деревьев в таблице - это то, что мы не знаем заранее, какова будет глубина вложенности разделов. Можно было бы создать таблицу с 10 полями, например. Но если вложенных разделов будет меньше, то таблица будет неэффективна - останется много пустых полей. А если больше - ограничивать пользователя?
Самый простой способ сохранения структуры дерева и ее считывания обратно - воспользоваться тем, что дерево - это список узлов, и имеет хорошо знакомые нам методы:
Однако этот способ имеет массу недостатков. Во-первых, в результате получим простой текстовый файл , в котором вложенные узлы располагаются ниже родителя и имеют отступ . Пользователь легко может случайно или намеренно испортить такой файл , отредактировав или просто удалив его с диска, и программа будет работать с ошибками. Во-вторых, обычно древовидная структура тесно связана с другими данными, например, таблица отделов предприятия связана со служащими этого предприятия - запись каждого служащего имеет ссылку на отдел, где он работает. Если структуру предприятия хранить в простом текстовом файле, то такую связь сложно будет обеспечить.
Когда программист впервые сталкивается с необходимостью хранения древовидных структур в базе данных, обычно он первым делом подключается к Интернету и ищет какой-нибудь компонент , который бы позволил это делать. Но не все нестандартные компоненты работают качественно, да и зачем искать какой-то новый компонент , когда имеется стандартный TreeView на вкладке Win32 Палитры компонентов ? Именно с этим компонентом мы и будем работать в данной лекции.
Рецептов работы с деревьями в базах данных много, мы рассмотрим лишь один из них, достаточно эффективный и в то же время простой. Смысл этого способа состоит в том, чтобы в каждой записи таблицы сохранять номер узла раздела, номер его родителя, если он есть, и название узла. В случае если узел не имеет родителя (главный узел, например, "Художественная литература" в рисунке 10.1), то в соответствующее поле запишем ноль.
Подготовка проекта
Для реализации примера нам потребуется новая база данных . Загрузите MS Access и создайте базу данных " TreeBD ", а в ней таблицу " Razdels ". Вообще-то, в базе данных MS Access как таблицы, так и поля могут иметь русские названия, однако мы будем использовать средства SQL , который не всегда корректно обрабатывает русские идентификаторы. Кроме того, данный способ можно использовать в любой СУБД , а далеко не все из них так предупредительны, как MS Access , поэтому название таблицы и ее полей выполним латиницей.
Таблица будет иметь три поля:
Созданную базу данных сохраните в папке, где будем разрабатывать наш проект (не забудьте сделать резервную копию пустой базы данных на всякий случай.).
Далее создадим в Delphi новый проект и простую форму:
Как всегда, назовите форму fMain , в свойстве Caption напишите "Реализация сохранения дерева в БД ", модуль формы сохраните как Main , а проект в целом назовите, например, TreeToBD . Сделанная база данных TreeBD должна быть в той же папке, что и проект.
Далее установите компонент TreeView ( дерево ) с вкладки Win32. Его свойству Align присвойте alLeft, чтобы дерево заняло весь левый край. Затем можете установить сплиттер - разделитель, ухватившись за который пользователь сможет менять ширину дерева. Компонент Splitter находится на вкладке Additional и его свойство Align по умолчанию равно alLeft - разделитель "прилепится" к правому краю дерева.
Правее установите сетку DBGrid с вкладки Data Controls, и его свойству Align присвойте alClient, чтобы сетка заняла все оставшееся место . Ни главное меню , ни панель инструментов нам здесь не потребуются, используем лишь два всплывающих PopupMenu - первый для дерева, второй для сетки (выберите соответствующие PopupMenu в свойстве PopupMenu этих компонентов).
Далее с вкладки ADO нам потребуется компонент ADOConnection для соединения с базой данных, таблица ADOTable и запрос ADOQuery для вспомогательных нужд. С вкладки Data Access - компонент DataSource, для связи сетки с таблицей. Подключите ADOConnection к базе данных и откройте соединение ( "ADO. Связь с таблицей MS Access" ). Таблицу подключите к ADOConnection (свойство Connection ), затем выберите в свойстве TableName нашу таблицу " Razdels ", а свойство Name переименуйте в tRazdels - так будем обращаться к таблице. Для удобства отображения названия полей откройте редактор полей таблицы (дважды щелкнув по ней), добавьте все поля и у каждого поля измените свойство DisplayLabel, соответственно, на "№", "Родитель" и "Название". Не забудьте открыть таблицу.
Компонент DataSource подключите к tRazdels , а сетку - к DataSource, в сетке должны отобразиться поля. Кроме того, переименуйте свойство Name запроса ADOQuery1 в Q1, ведь нам часто придется обращаться к нему по имени. Запрос также подключите к ADOConnection, но делать его активным не нужно.
На этом приготовления закончены.
Создание и сохранение в таблицу дерева разделов
Работа с деревьями состоит из двух этапов:
- Сохранение дерева в таблицу.
- Считывание дерева из таблицы.
В этом разделе лекции разберем первый этап. Щелкните дважды по компоненту PopupMenu1, который "привязан" к дереву, и создайте в нем следующие разделы :
- Создать главный раздел
- Добавить подраздел к выделенному
- Переименовать выделенный
- Удалить выделенный
- -
- Свернуть дерево
- Развернуть дерево
Все эти команды относятся к работе с разделами дерева. Прежде всего, создадим обработчик для команды "Создать главный раздел". Листинг процедуры смотрите ниже:
Разберем код. Переменная NewRazd имеет тип TTreeNode , к которому относятся все разделы и подразделы (узлы) дерева. В текстовую переменную s с помощью функции InputQuery() мы получаем имя нового главного узла. Функция имеет три строковых параметра:
- Заголовок окна.
- Пояснительная строка.
- Переменная, куда будет записан введенный пользователем текст.
Если переменная , передаваемая в качестве третьего параметра, пуста, то поле ввода будет пустым. Если же в ней содержался текст - он будет выведен как текст "по умолчанию". Функция возвращает True, если пользователь ввел (или изменил) текст, и False в противном случае. В результате работы функции для пользователя будет выведено простое окно с запросом:
мы снимаем выделение, если какой либо раздел был выделен, ведь мы создаем главный раздел, не имеющий родителя. Свойство Selected компонента TreeView указывает на выделенный узел и позволяет производить с ним различные действия, например, получить текст узла:
А присваиваемое значение nil (ничто) снимает всякое выделение, если таковое было. Далее мы создаем сам узел:
Разберем эту строку подробней. Переменная NewRazd - это новый узел дерева. Каждый узел - объект , обладающий своими свойствами и методами. Все узлы хранятся в списке - свойстве Items дерева TreeView, а метод Add() этого свойства позволяет добавить новый узел. У метода два параметра - выделенный узел (у нас он равен nil ) и строка текста, которая будет присвоена новому узлу. Таким образом, в дереве появляется новый главный узел.
Затем мы сохраняем его в базу данных, предварительно добавив в таблицу новую запись :
Вы помните, что такие методы, как Append или Insert автоматически переводят таблицу в режим редактирования, поэтому вызывать метод Edit излишне?
Обратите внимание на то, что мы сохраняем ноль в поле "R_ Parent ", так как это - главный раздел, не имеющий родителя. Свойство Text нового узла NewRazd содержит название нового узла, которое мы присваиваем полю "R_Name".
Далее сгенерируем процедуру для команды меню "Добавить подраздел к выделенному":
Код этой процедуры очень похож на код предыдущей, но есть и отличия. Прежде всего, мы проверяем - а имеется ли выделенный раздел? Ведь фокус ввода мог быть и на сетке DBGrid, когда пользователь щелкнул правой кнопкой по дереву, и выбрал эту команду. В этом случае, если не делать проверки, мы получим ошибку, пытаясь добавить дочерний узел к пустоте.
Далее, мы ввели строковую переменную z , чтобы сформировать запрос . Ведь пользователю будет удобней, если в окне InputQuery() он сразу увидит, к какому именно разделу он добавляет подраздел.
Затем, при добавлении дочернего узла вместо метода Add() мы используем метод AddChild() .
Ну и, наконец, при сохранении узла в таблицу мы записываем не только созданный узел, но и номер его родителя, получив его с помощью запроса
Запрос формирует набор данных с единственной строкой - записью родителя добавляемого элемента. Поле Q1['R_Num'], как вы понимаете, хранит номер этого родителя в запросе.
Код процедуры переименования выделенного раздела выглядит так:
Здесь комментарии достаточно подробны, чтобы вы разобрались с кодом. Следует обратить внимание на то, что вначале мы исправляем запись в таблице, и только потом - в узле. Если бы мы сначала исправили текст узла, как бы затем нашли старую запись в таблице? Пришлось бы вводить дополнительную переменную для хранения старого текста.
Удаляется выделенный узел еще проще:
Далее нам осталось сгенерировать процедуры для сворачивания и разворачивания дерева. Делается это одной строкой:
Итак, метод FullCollapse дерева TreeView сворачивает его узлы, а метод FullExpand разворачивает.
Теперь сохраните проект и скомпилируйте его. Попробуйте заполнить дерево разделами и подразделами, убедитесь, что параллельно данные сохраняются и в таблице.
Читайте также: