Как представить дерево данных в SQL?

Question

Я пишу структуру древовидной структуры данных, которая объединена из дерева и TreeNode. Дерево будет содержать действия root и верхнего уровня данных. Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме окна, где я могу привязать дерево к TreeView.

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

1. Интуитивно понятная реализация.
2. Легкое связывание. Будет легко перемещаться из дерева в структуру БД и обратно (если есть)

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

Любые идеи?

Answer 1

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

Если вы хотите сохранить каждый элемент в виде строки, вы должны сначала прочитать Managing Hierarchical Data in MySQL (зависит от MySQL, но совет сохраняется и для многих других баз данных).

Если вы только когда-либо доступ к всему дереву, модель списка смежности делает его трудно получить все узлы, под корень, не используя рекурсивный запрос. Если вы добавите дополнительный столбец, который ссылается на голову, вы можете сделать SELECT * WHERE head_id = @id и получить все дерево в одном нерекурсивном запросе, но он денормализует базу данных.

В некоторых базах данных есть пользовательские расширения, которые упрощают хранение и извлечение данных с иерархической точки зрения, например Oracle имеет CONNECT BY.

Answer 2

Самой простая реализация листа смежности структуры:

id parent_id data 

Однако некоторые базы данных, в частности MySQL, есть некоторые проблемы в работе с этой моделью, поскольку она требует возможности запускать рекурсивные запросы, которые MySQL испытывают недостаток.

Другая модель Вложенные наборы:

id lft rgt data 

где lft и rgt являются произвольными значениями, которые определяют иерархию (любой ребенок lft, rgt должен быть в пределах любого родителя lft, rgt)

Это не требует рекурсивных запросов, но это медленнее и труднее поддерживать.

Однако в MySQL это можно улучшить, используя SPATIAL abitilies.

Смотрите эти статьи в моем блоге:

• Adjacency list vs. nested sets: PostgreSQL
• Adjacency list vs. nested sets: SQL Server
• Adjacency list vs. nested sets: Oracle
• Adjacency list vs. nested sets: MySQL

для более подробного объяснения.

Answer 3

Что-то вроде табличных «узлов», где каждая строка узла содержит родительский идентификатор (в дополнение к данным обычного узла). Для root родитель имеет значение NULL.

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

Answer 4

я закладка это slidshare о SQL-Antipatterns, в котором рассматривается несколько вариантов: http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed

рекомендацию есть использовать Closure таблицу (это объясняется в слайдах).

Вот резюме (слайд 77):

    | Query Child | Query Subtree | Modify Tree | Ref. Integrity 
Adjacency List | Easy  |  Hard  | Easy  |  Yes 
Path Enumeration | Easy  |  Easy  | Hard  |  No 
Nested Sets  | Hard  |  Easy  | Hard  |  No 
Closure Table  | Easy  |  Easy  | Easy  |  Yes 

Answer 5

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

1. Если вы хотите обновить узел, вам нужно только переписать данные этого узла.
2. Если вы хотите запросить только определенный узел, вы можете получить именно ту информацию, которая вам нужна, тем самым имея меньше накладных расходов на подключение к базе данных.
3. Многие языки программирования имеют функциональные возможности для преобразования данных mysql в XML или json, что упростит открытие приложения с помощью api.

Answer 6

Я удивлён, что никто не упомянул материализовался тракту решение, которое, вероятно, самый быстрый способ работы с деревьями в стандартном SQL.

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

Посмотрите на примере таблицы узел:

+---------+-------+ 
| node_id | path | 
+---------+-------+ 
| 0  |  | 
| 1  | 1  | 
| 2  | 2  | 
| 3  | 3  | 
| 4  | 1.4 | 
| 5  | 2.5 | 
| 6  | 2.6 | 
| 7  | 2.6.7 | 
| 8  | 2.6.8 | 
| 9  | 2.6.9 | 
+---------+-------+ 

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

SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%') 

Keep в помните, что колонка путь должен быть проиндексирован, чтобы выполнить быстро с помощью LIKE claus е.

Answer 7

Если вы используете PostgreSQL, вы можете использовать ltree, пакет в расширении contrib (поставляется по умолчанию), который реализует структуру данных дерева.

docs От:

CREATE TABLE test (path ltree); 
INSERT INTO test VALUES ('Top'); 
INSERT INTO test VALUES ('Top.Science'); 
INSERT INTO test VALUES ('Top.Science.Astronomy'); 
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics'); 
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology'); 
INSERT INTO test VALUES ('Top.Hobbies'); 
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy'); 
INSERT INTO test VALUES ('Top.Collections'); 
INSERT INTO test VALUES ('Top.Collections.Pictures'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies'); 
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts'); 
CREATE INDEX path_gist_idx ON test USING GIST (path); 
CREATE INDEX path_idx ON test USING BTREE (path); 

Вы можете сделать запросы, как:

ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science'; 
       path 
------------------------------------ 
Top.Science 
Top.Science.Astronomy 
Top.Science.Astronomy.Astrophysics 
Top.Science.Astronomy.Cosmology 
(4 rows)