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

В данной ситуации можно использовать отличные решения, которые опираются на внутреннее представление b-деревьев 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) слева направо, где корень = 1.
• pa: Ссылка (по tw) на родительскую ноду, для корня значение NULL.
• sz: Размер ветви узла, включая сам узел.
• nc: Используется как синоним и представляет собой tw + sz, указывая на 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.nc 
ORDER BY anc.tw;

Соседи и дети - это просто: нужно использовать поле 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;

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

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

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

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

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

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

Запросы для корректировки дерева

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

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

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

UPDATE node me, node anc 
SET anc.sz = anc.sz - me.sz 
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 
WHERE me.tw = 18 AND anc.tw >= me.tw;

И, наконец, необходимо корректировать pa для тех, у кого pa больше, чем у удаляемой ветви.

UPDATE node me, node anc 
SET anc.pa = anc.pa - me.sz 
WHERE me.tw = 18 AND anc.pa >= me.tw;

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

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

Возможно, он нарушает некоторые правила, так как я создаю собственные объекты, но, эй, я делаю это в качестве отвлечения от настоящей работы 😃

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

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

        // отображает идентификатор узла на его объект Node
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // отображает идентификатор узла на идентификатор его родителя
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // создаем специальный 'корневой' узел с id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // проходим по входным данным
        for (Map<String, String> map : input) {

            // ожидаем, что каждая Map будет иметь ключи для "id", "name", "parent" ... 
            // реальная реализация будет читать из SQL объекта или 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);
        }

        // теперь, когда каждый узел создан, устанавливаем отношения родитель-ребенок
        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);
        // рекурсивный вызов
        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) {

        // настройка тестовых данных
        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);
    }

    // вспомогательный метод для создания тестовых данных
    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;
    }
}

Если у вас есть вопросы или вам нужны улучшения по коду, не стесняйтесь спрашивать!

Предположим, что корневые элементы имеют идентификатор родителя равный нулю. Вот псевдокод для вывода этих элементов в текстовом формате:

function PrintLevel (int curr, int level)
    //выводим отступы
    for (i=1; i<=level; i++)
        print табуляцию
    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)

В этом коде функция PrintLevel принимает два параметра: curr (идентификатор текущего элемента) и level (уровень вложенности). Сначала мы выводим нужное количество отступов, соответствующее текущему уровню, а затем печатаем идентификатор элемента. После этого рекурсивно вызываем PrintLevel для всех дочерних элементов, увеличивая уровень на единицу.

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

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

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

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