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

Ответ 1

Теперь, когда 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;

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

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

• Список привязок ( "родительский" столбец) и
• Перечисление пути (пунктирные числа в столбце имен).

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

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

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

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)
);

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

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);

Теперь вы можете получить дерево, начинающееся с node 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 исключаются, поскольку они являются частью отдельной иерархии, а не спускаются с node 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);

Затем вы можете добавить термин в свой поиск для запроса непосредственных детей данного node. Это потомки, чей 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 | 
+----+

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

Здесь приведен пример запроса для возврата всех узлов, которые являются потомками node 1, присоединяют их к FlatTable, который содержит другие атрибуты node, такие как 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;

Re comment from @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, предположительно, чтобы убедиться, что порядок соответствует иерархии. Но это не работает, потому что после "Node 1.2" он будет заказывать "Node 1.1.1".

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

Ответ 2

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

Для django-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
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

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

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

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

Дополнительная информация о MPTT:

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

Ответ 3

С 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'

Ответ 4

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

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

Позвольте мне показать вам, как это будет работать в PostgreSQL 9.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);
  

• Напишите запрос

  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 внутри родителя. Это говорит нам, как представить их в выходной ссылке node родительскому в этом порядке.

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

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

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

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

Ответ 5

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

В любом случае я хотел поддержать древовидную структуру и свойство Order. Я включил одно свойство в каждый Node, называемый 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 на моем блоге.

Спасибо, что ваш ответ был полезен при запуске!

Ответ 6

Хорошо, учитывая выбор, я бы использовал объекты. Я бы создал объект для каждой записи, где каждый объект имеет коллекцию 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-процесс. Это неприятно. Если у вас есть выбор, перейдите по маршруту ООП.

Ответ 7

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

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

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

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 Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it 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;
    }
}

Ответ 8

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

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)

Ответ 9

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

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

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

Ответ 10

Есть действительно хорошие решения, которые используют внутреннее представление btree индексов sql. Это основано на некоторых замечательных исследованиях, проведенных в 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) на родительский node, корень имеет null.
• sz: размер ветки node, включая сам.
• nc: используется как синтаксический сахар. это tw + nc и представляет собой tw из node "следующего ребенка".

Вот пример 24 node населенности, упорядоченный по 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 |
+-----+---------+----+------+------+------+

Каждый результат дерева может быть выполнен нерекурсивно. Например, чтобы получить список предков node при 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 |
+-----+---------+----+------+------+------+

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

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

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

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

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

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

Отрегулировать запросы дерева

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

Нам нужны два параметра - флаг, представляющий, будем ли мы уменьшать или увеличивать или индексировать, и индекс node 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 tw выше, чем удаляемая ветка.

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;

Ответ 11

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

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

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

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

Ответ 12

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

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

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

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

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

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

Ответ 13

Если элементы находятся в древовидном порядке, как показано в вашем примере, вы можете использовать что-то вроде следующего примера 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), пока не найдет родительский элемент текущего элемента. Затем он выдает начало этого node и толкает его в стек.

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

print "  " * len(stack)

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

Изменить: из вашего разъяснения видно, что имена не предназначались для путей node. Это предполагает альтернативный подход:

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

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

Ответ 14

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

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