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

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

на 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
|  |________________________________|  |________________________________|  |
|__________________________________________________________________________|

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

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

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

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

• деревья в SQL
• хранение иерархических данных в базе данных
• управление Иерархические данные в MySQL

начиная с 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'

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

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

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

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

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

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

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

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

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

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

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

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

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

PrintLine(0, 0)

Edit: это похоже на a пару других записей, но я думаю, что это немного чище. Одна вещь, которую я добавлю: это чрезвычайно интенсивный 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) {

        // 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;
    }
}

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

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)

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

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

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

есть действительно хорошие решения, которые используют внутреннее представление 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) на родительский узел, корень имеет значение 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 = 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 и SZ (размер ветви) должны быть обновлены на всех узлах после точки вставки и для всех предков соответственно.

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

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

Настроить Дерево Запросов

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

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

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

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

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

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

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

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

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

print "  " * len(stack)

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

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

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

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

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

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

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

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

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

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

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

но используйте nosql только для запросов уровня Data-mart, а не для хранения / обслуживания транзакций