Какой самый эффективный / элегантный способ преобразовать плоскую таблицу в дерево?

Предполагая, что вы знаете, что корневые элементы равны нулю, вот псевдокод для вывода в текст:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

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

Обновлено: сначала я бы прочитал всю таблицу в массиве, поэтому он не будет повторно запрашивать БД. Конечно, это будет непрактично, если ваш стол очень большой.

После того, как структура построена, я должен сначала пройти через нее глубину и распечатать HTML.

Нет лучшего фундаментального способа хранения этой информации с использованием одной таблицы (хотя я могу ошибаться;) и хотел бы увидеть лучшее решение). Однако если вы создадите схему для использования динамически создаваемых таблиц БД, то вы откроете совершенно новый мир за счет простоты и риска ада SQL;).

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

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

Что касается того, есть ли «лучший» способ сохранить дерево в базе данных, это зависит от того, как вы собираетесь использовать данные. Я видел системы с известной максимальной глубиной, в которых для каждого уровня иерархии использовались разные таблицы. Это имеет большой смысл, если уровни в дереве не совсем эквивалентны (категории верхнего уровня отличаются от листьев).

Если бы у меня был выбор, я бы использовал объекты. Я бы создал объект для каждой записи, где каждый объект имеет коллекцию children, и сохранил бы их все в ассоциативном массиве (/ hashtable), где Id является ключом. И просмотрите всю коллекцию один раз, добавив потомков в соответствующие дочерние поля. Простой.

Но поскольку вам не нравится ограничивать использование какого-нибудь хорошего ООП, я, вероятно, буду повторять, основываясь на:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Обновлено: это похоже на пару других записей, но я думаю, что это немного чище. Я добавлю одну вещь: это чрезвычайно интенсивное использование SQL. Это противный. Если у вас есть выбор, идите по маршруту ООП.

Теперь, когда MySQL 8.0 поддерживает рекурсивные запросы, мы можем сказать, что все популярные базы данных SQL поддерживают рекурсивные запросы в стандартном синтаксисе.

WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

Я тестировал рекурсивные запросы в MySQL 8.0 в своей презентации Выпадение рекурсивных запросов в 2017 году.

Ниже мой первоначальный ответ от 2008 года:

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

• Список смежности («родительский» столбец) и
• Перечисление путей (номера с точками в столбце с вашим именем).

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

Я обычно предпочитаю дизайн под названием Закрытие таблицы (он же «Связь смежности») для хранения данных с древовидной структурой. Для этого требуется еще одна таблица, но тогда запросы к деревьям довольно просты.

Я освещаю Closure Table в своей презентации Модели для иерархических данных с SQL и PHP и в моей книге Антипаттерны SQL: как избежать ловушек программирования баз данных.

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

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

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

Теперь вы можете получить дерево, начинающееся с узла 1, вот так:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

Результат (в клиенте MySQL) выглядит следующим образом:

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

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

Re: комментарий от e-satis о ближайших потомках (или непосредственных родителях). Вы можете добавить столбец «path_length» к ClosureTable, чтобы упростить запрос непосредственно для непосредственного дочернего или родительского (или любого другого расстояния).

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

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

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

Ответ от @ashraf: "Как насчет сортировки всего дерева [по имени]?"

Вот пример запроса, чтобы вернуть все узлы, являющиеся потомками узла 1, присоединить их к FlatTable, которая содержит другие атрибуты узла, такие как name, и отсортировать по имени.

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

Ответ от @Nate:

SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

Сегодня пользователь предложил внести правку. Модераторы SO одобрили правку, но я отменяю ее.

При редактировании предлагалось, чтобы ORDER BY в последнем запросе выше был ORDER BY b.path_length, f.name, предположительно, чтобы убедиться, что порядок соответствует иерархии. Но это не сработает, потому что он разместит «Узел 1.1.1» после «Узла 1.2».

Если вы хотите, чтобы порядок соответствовал иерархии разумным образом, это возможно, но не просто путем упорядочивания по длине пути. Например, см. Мой ответ на Иерархическая база данных MySQL Closure Table - Как извлечь информацию в правильном порядке.

Это было написано быстро, и оно не является ни красивым, ни эффективным (к тому же в нем много автобоксов, преобразование между int и Integer раздражает!), Но это работает.

Вероятно, это нарушает правила, поскольку я создаю свои собственные объекты, но, эй, я делаю это как отвлечение от реальной работы :)

Это также предполагает, что resultSet / table полностью считывается в какую-то структуру до того, как вы начнете создавать узлы, что не было бы лучшим решением, если у вас есть сотни тысяч строк.

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id = " + id + ", name = " + name + ", parent = " + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

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

Затем, пожертвовав небольшим количеством памяти, особенно если ваше дерево разреженное и / или несбалансированное, вы можете с небольшой математикой индекса получить доступ ко всем строкам случайным образом, сохранив свое дерево, сначала ширину в массиве, например (для двоичного дерево):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

ты знаешь длину своей строки, ты это знаешь

Я сейчас на работе, поэтому не могу тратить на это много времени, но с интересом могу получить для этого немного кода.

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

Начиная с Oracle 9i, вы можете использовать CONNECT BY.

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

Начиная с SQL Server 2005, вы можете использовать рекурсивное общее табличное выражение (CTE).

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

Оба выдадут следующие результаты.

Name
'Node 1'
'    Node 1.1'
'        Node 1.1.1'
'    Node 1.2'
'Node 2'
'    Node 2.1'

Если элементы расположены в древовидном порядке, как показано в вашем примере, вы можете использовать что-то вроде следующего примера Python:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

Это поддерживает стек, представляющий текущую позицию в дереве. Для каждого элемента в таблице он выталкивает элементы стека (закрывая соответствующие блоки div), пока не найдет родителя текущего элемента. Затем он выводит начало этого узла и помещает его в стек.

Если вы хотите вывести дерево с использованием отступов, а не вложенных элементов, вы можете просто пропустить операторы печати, чтобы распечатать блоки div, и вывести количество пробелов, равное некоторому кратному размеру стека перед каждым элементом. Например, в Python:

print "  " * len(stack)

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

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

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

Это строит дерево массивов кортежей (!). idx [0] представляет корень (и) дерева. Каждый элемент в массиве представляет собой кортеж из двух элементов, состоящий из самого узла и списка всех его дочерних элементов. После создания вы можете сохранить idx [0] и отбросить idx, если только вы не хотите получать доступ к узлам по их идентификатору.

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

Для джанго-mptt я использовал такую ​​структуру:

id  parent_id  tree_id  level  lft  rght
--  ---------  -------  -----  ---  ----
 1       null        1      0    1    14
 2          1        1      1    2     7
 3          2        1      2    3     4
 4          2        1      2    5     6
 5          1        1      1    8    13
 6          5        1      2    9    10
 7          5        1      2    11   12

Это описывает дерево, которое выглядит следующим образом (с id, представляющим каждый элемент):

 1
 +-- 2
 |   +-- 3
 |   +-- 4
 |
 +-- 5
     +-- 6
     +-- 7

Или, как диаграмма вложенных наборов, которая делает более очевидным, как работают значения lft и rght:

 __________________________________________________________________________
|  Root 1                                                                  |
|   ________________________________    ________________________________   |
|  |  Child 1.1                     |  |  Child 1.2                     |  |
|  |   ___________    ___________   |  |   ___________    ___________   |  |
|  |  |  C 1.1.1  |  |  C 1.1.2  |  |  |  |  C 1.2.1  |  |  C 1.2.2  |  |  |
1  2  3___________4  5___________6  7  8  9___________10 11__________12 13 14
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

Как видите, чтобы получить все поддерево для данного узла в древовидном порядке, вам просто нужно выбрать все строки, которые имеют значения lft и rght между его значениями lft и rght. Также просто получить дерево предков для данного узла.

Столбец level - это немного денормализация для удобства, а столбец tree_id позволяет перезапустить нумерацию lft и rght для каждого узла верхнего уровня, что уменьшает количество столбцов, затронутых вставками, перемещениями и удалениями, как lft и столбцы rght должны быть соответствующим образом скорректированы, когда происходят эти операции, чтобы создать или закрыть пробелы. Я сделал заметки о развитии в то время, когда пытался осмыслить запросы, необходимые для каждой операции.

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

Подробнее о MPTT:

• Деревья в SQL
• Хранение иерархических данных в базе данных
• Управление иерархическими данными в MySQL

Ответ Билла чертовски хорош, этот ответ добавляет к нему некоторые вещи, которые заставляют меня желать, чтобы поддерживаемые потоки ответы были SO.

В любом случае я хотел поддержать древовидную структуру и свойство Order. Я включил одно свойство в каждый узел под названием leftSibling, которое делает то же самое, что Order должен делать в исходном вопросе (поддерживать порядок слева направо).

mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

Более подробная информация и код SQL в моем блоге.

Спасибо, Билл, твой ответ был полезен для начала!

Подумайте об использовании инструментов nosql, таких как neo4j, для иерархических структур. например, сетевое приложение, такое как linkedin, использует couchbase (другое решение nosql)

Но используйте nosql только для запросов уровня витрины данных, а не для хранения / поддержки транзакций.

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

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

Позвольте мне показать вам, как это будет работать в PostgreSQL 9.1.

1. Создать структуру

   CREATE TABLE tree (
       id int  NOT NULL,
       name varchar(32)  NOT NULL,
       parent_id int  NULL,
       node_order int  NOT NULL,
       CONSTRAINT tree_pk PRIMARY KEY (id),
       CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
         REFERENCES tree (id) NOT DEFERRABLE
   );
   
   
   insert into tree values
     (0, 'ROOT', NULL, 0),
     (1, 'Node 1', 0, 10),
     (2, 'Node 1.1', 1, 10),
     (3, 'Node 2', 0, 20),
     (4, 'Node 1.1.1', 2, 10),
     (5, 'Node 2.1', 3, 10),
     (6, 'Node 1.2', 1, 20);
   

2. Написать запрос

   WITH RECURSIVE 
   tree_search (id, name, level, parent_id, node_order) AS (
     SELECT 
       id, 
       name,
       0,
       parent_id, 
       1 
     FROM tree
     WHERE parent_id is NULL
   
     UNION ALL 
     SELECT 
       t.id, 
       t.name,
       ts.level + 1, 
       ts.id, 
       t.node_order 
     FROM tree t, tree_search ts 
     WHERE t.parent_id = ts.id 
   ) 
   SELECT * FROM tree_search 
   WHERE level > 0 
   ORDER BY level, parent_id, node_order;
   

   Вот результаты:

    id |    name    | level | parent_id | node_order 
   ----+------------+-------+-----------+------------
     1 | Node 1     |     1 |         0 |         10
     3 | Node 2     |     1 |         0 |         20
     2 | Node 1.1   |     2 |         1 |         10
     6 | Node 1.2   |     2 |         1 |         20
     5 | Node 2.1   |     2 |         3 |         10
     4 | Node 1.1.1 |     3 |         2 |         10
   (6 rows)
   

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

   Для каждого уровня они упорядочены по parent_id и node_order внутри родительского. Это говорит нам, как представить их в выходном узле - связать узел с родительским в указанном порядке.

   Имея такую ​​структуру, не составит труда сделать действительно красивую презентацию в HTML.

   Рекурсивные CTE доступны в PostgreSQL, IBM DB2, MS SQL Server и Oracle.

   Если вы хотите узнать больше о рекурсивных SQL-запросах, вы можете либо проверить документацию своей любимой СУБД, либо прочитать две мои статьи по этой теме:

   • Сделайте это в SQL: рекурсивный обход дерева
   • Узнайте о возможностях рекурсивных запросов SQL

Есть действительно хорошие решения, которые используют внутреннее представление индексов sql в виде btree. Это основано на большом исследовании, проведенном еще в 1998 году.

Вот примерная таблица (в mysql).

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

Единственные поля, необходимые для представления в виде дерева:

• tw: индекс предварительного заказа DFS слева направо, где root = 1.
• pa: ссылка (с использованием tw) на родительский узел, root имеет значение null.
• sz: размер ветви узла, включая его самого.
• nc: используется как синтаксический сахар. это tw + nc и представляет собой tw "следующего потомка" узла.

Вот пример из 24 узлов, отсортированных по tw:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

Каждый результат дерева может быть получен нерекурсивно. Например, чтобы получить список предков узла по адресу tw = '22 '

Предки

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Братья и сестры и дети тривиальны - просто используйте упорядочение полей pa по tw.

Потомки

Например, набор (ветвь) узлов с корнем tw = 17.

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Дополнительные замечания

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

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

Стоимость вставки / удаления высока, потому что значения tw index и sz (размер ветви) необходимо будет обновить на всех узлах после точки вставки и для всех предков соответственно.

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

• Переместите ветку из зоны досягаемости.
• Закройте оставшийся пробел. (оставшееся дерево теперь нормализовано).
• Откройте брешь, куда он пойдет.
• Переместите ветку в новое положение.

Настроить древовидные запросы

Открытие / закрытие пробелов в дереве - важная подфункция, используемая методами создания / обновления / удаления, поэтому я включаю ее сюда.

Нам нужны два параметра - флаг, показывающий, уменьшаем мы или нет, и индекс tw узла. Так, например, tw = 18 (размер ветки равен 5). Предположим, что мы уменьшаем размер (удаляем tw) - это означает, что мы используем «-» вместо «+» в обновлениях следующего примера.

Сначала мы используем (слегка измененную) функцию-предок, чтобы обновить значение sz.

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

Затем нам нужно настроить tw для тех, чей tw больше, чем ветвь, которую нужно удалить.

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

Затем нам нужно настроить родительский элемент для тех, чье pa больше, чем удаляемая ветвь.

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;