Как лучше хранить дерево в mySQL?

Question

[Сергей Петров]

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

Comments

[Дмитрий]

Если ограничено количество потомков, то вообще не проблема - просто добавляете два реквизита child1 и child2.

[Сергей Петров]

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

[Дмитрий]

Сергей Петров, Вам нужно показывать количество вообще всех потомков текущего узла? Не только прямых?

[Сергей Петров]

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

[Дмитрий]

Сергей Петров, Тогда вам в любом случае как бы вы ни хранили данные, придется пересчитывать их для каждого родительского узла без вариантов просто по логике вещей. Но вы можете это делать например не каждый раз, а периодически и показывать на странице не 10731 а '10700'', То есть округляя до сотен или десятков. Вряд ли пользователю каждый раз нужна точная цифра.

Answer 1

[Владимир Коротенко]

Поищите nested set это универсально

Comments

[Сергей Петров]

Сейчас так и делаем. Но интересны другие варианты. update left и right узлов уже занимает 2 секунды при вставке, это время будет только расти.

[Владимир Коротенко]

Сергей Петров, Как временный вариант добавьте поле isReal и пересчитайте все дерево за раз, а потом только вставляйте флажки при заполнении.

[Сергей Петров]

Владимир Коротенко, так оно непредсказуемо растет и ветвится. заранее его не построить. а если делать сразу "заготовку" пот 10 000 уровней, то никакой памяти не хватит с ним работать... :(

Answer 2

[ThunderCat]

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

Comments

[Сергей Петров]

Можно пример псевдокода как выбрать всех потомков в этом случае? У меня только рекурсия в голову приходит.

[Владимир Коротенко]

select * from tree where level > 4;

Или же с рекурсией
https://wiki.gis-lab.info/w/%D0%A4%D0%98%D0%90%D0%A1

WITH RECURSIVE child_to_parents AS (
  SELECT addrobj.* FROM addrobj
      WHERE aoid = '51f21baa-c804-4737-9d5f-9da7a3bb1598'
  UNION ALL
  SELECT addrobj.* FROM addrobj, child_to_parents
      WHERE addrobj.aoguid = child_to_parents.parentguid
        AND addrobj.currstatus = 0
)
SELECT * FROM child_to_parents ORDER BY aolevel;

[Сергей Петров]

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

[ThunderCat]

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

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

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

[Сергей Петров]

ThunderCat, всех сразу показывать не нужно. ближайшие к узлу 3-5 уровней. а вот общее количество потомков нужно.

[ThunderCat]

Сергей Петров, то есть select count(*) from tree where level > 4; и select * from tree where level > 4 and level < 8; неочевидно?

[Сергей Петров]

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

[ThunderCat]

Сергей Петров, вроде как count(*) и есть выбор числа всех записей, чего уж тут думать то... А в плане удобства - задача слишком абстрактно описана, чтобы судить о верных методах и подходах. По мне так вряд ли вы что-то более оптимальное придумаете в описанных условиях.