Выборка усеченного дерева из базы...

[leosun]

Столкнулись с коллегами с интересной задачей - нужно выбрать из базы структуры вида:

Корень 1
-- ветка 1
-- ветка 2
-- подветка 2.1
-- подветка 2.2
-- подподветка 2.2.1
-- подподветка 2.2.2
-- подподветка 2.2.3
(еще 3 подподветки)
-- подветка 2.3
(еще 8 подветок)
-- ветка 3
(еще 5 веток)

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

 

[Lirik]

>>На сайте с: 15.10.2006 и не слышали про Nested Sets...хм...
http://en.wikipedia.org/wiki/Nested_set_model

 

[~WR~]

В PostgreSQL будет как-то так:

SELECT *
FROM (
  SELECT path, ROW_NUMBER() OVER (PARTITION BY CASE WHEN nlevel(path) > 1 THEN subpath(path, -2, 1)::text::int ELSE -id END) AS row_number
  FROM genre_path
) a
WHERE row_number < 4

Выберет по три потомка для каждого узла дерева, кроме корневых.

Про тип данных ltree:
http://www.postgresql.org/docs/current/static/ltree.html

 

[~WR~]

>>На сайте с: 15.10.2006 и не слышали про Nested Sets...хм...

Угу, конечно) Сможешь написать запрос для nested sets на MySQL, который выполнит требуемую операцию? =)

 

[leosun]

В PostgreSQL будет как-то так:

SELECT *
FROM (
  SELECT path, ROW_NUMBER() OVER (PARTITION BY CASE WHEN nlevel(path) > 1 THEN subpath(path, -2, 1)::text::int ELSE -id END) AS row_number
  FROM genre_path
) a
WHERE row_number < 4

Выберет по три потомка для каждого узла дерева, кроме корневых.

Про тип данных ltree:
http://www.postgresql.org/docs/current/static/ltree.html

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

 

[~WR~]

>__<