Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > MySQL > Выборка только родителей текущего node дерева

Автор: fridkaratel 18.11.2010, 05:06

Собственно, сабж...  Есть некое дерево в БД Код ITEM-1     ITEM-1-1     ITEM-1-2         ITEM-1-2-1         ITEM-1-2-2     ITEM-1-3         ITEM-1-3-1     ITEM-1-4 ITEM-2 ITEM-3 Необходимо выбрать всех родителей элемента, например, ITEM-1-3-1, вплоть до самого верхнего уровня, в том числе и ITEM-1. Как построить простой запрос - нормального ничего не приходит... Возникла идея просто добавить доп. столбец в БД, в котором будут перечислены все родители через запятую, например, в этом случае будет "1,6". Ну а потом уже SELECT ... IN (1,6). Что посоветуете?

Автор: Akina 18.11.2010, 08:40

Цитата(fridkaratel @  18.11.2010,  06:06 ) Что посоветуете?  Почитать что-нить по хранению и обработке деревьев в базах данных. Можно - тут, на форуме. Тем предостаточно, в т.ч. и свеженьких. Посмотри в подвале страницы, раздел "А здесь смотрели?".

Автор: fridkaratel 18.11.2010, 11:17

@Akina: По темам "А здесь смотрели?" пробежался ещё перед созданием темы... Наиболее подходящая - "Выборка из одной таблицы несколько раз одновременно"... Но не хотелось бы использовать JOIN по несколько раз в запросе, тем более, количество использований напрямую зависит от вложенности дерева. И я думал об этом ещё до создания темы... Мог бы почитать и другие темы, но не знаю, как правильней задать вопрос в поиск... К тому же, хотелось бы найти наиболее рациональное и производительное решение, поэтому родилась идея, которую я описал в 1м посте.

Автор: skyboy 18.11.2010, 11:40

есть три принципа хранения иерархическихдревовидных данных: materialized path, nested sets и adjacency list(в переводе, соответственно, "материализованный путь", "вложенные множества" и "список смежности"). для вытягивания предков одним запросом подходит первая и вторая структура. для быстрого вытягивания предков(кстати, и потомков) одним запросом подходит вторая структура. если ты вытягиваешь родителей имеено по имени, как ты показал(т.е. ориентируемся на "item-1-3-1" и должны выбрать "item-1-3" и "item-1"), то у тебя metrialized path и вытянуть всех родителей можно всего одним запросом where "item-1-3-1" like concat(name_item, "-", "%")

Автор: fridkaratel 18.11.2010, 12:04

@skyboy: Я неудачно привёл пример  Имена указывал, чтобы легче было понять, что мне надо  Вообще, названия элементов не зависят от родителей, то есть может быть и "SomeItem", и "ItemOfChild" и т.п. - в имени нет иерархии... Сейчас у меня такая таблица: Код Id    Parent    Title 1     0         Caption1 2       1       Caption2 3         2     Caption3 4         2     Caption4 5       1       Caption5 6       1       Caption6 7     0         Caption7 8       7       Caption8 9         8     Caption9

Автор: skyboy 18.11.2010, 12:32

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

Автор: fridkaratel 18.11.2010, 12:34

@skyboy: А как тебе вариант с доп. столбцом, который я привёл в своём 1м посте? А то у меня как-то душа к нему лежит - всего одним запросом без JOIN'ов

Автор: skyboy 18.11.2010, 12:47

materialized path один запрос, без join'в, без рекурсии. но работа с текстом, что выльется в невозможность использования ключей(никакого IN не получится; конструкция будет использовать like/locate). так что, если у тебя могут быть офигенно глубокие деревья(раз ты писал про "неопределенную вложенность"), стоит посмотреть на nested sets

Автор: gcc 18.11.2010, 13:31

fridkaratel, смотря какая таблица и сколько занимает если 100млн и неограниченное количество ступеней, то может быть с одним parent_id будет сложнова-то вот тут http://forum.vingrad.ru/act-Search/CODE/show/searchid-958e7712b639a64ac4a00ec82a9cceef/search_in-posts/result_type/topics/flag/search/highlite/%25D0%25B4%25D0%25B5%25D1%2580%25D0%25B5%25D0%25B2%25D0%25BE/index.html обсуждали еще варианты: 1) в любом случае можно прокэшировать, например, на 3 минуты, за это время все ветки будут из кеша... 2) или постаивть тип таблицы Memory в этой таблицы хранить только id и parent_id 3) для экономии рекурсии, может быть попробовать как-то так: Код                SELECT t1.id_se AS lvl1,                               t2.id_se as lvl2,                                t3.id_se as lvl3,                               t4.id_se as lvl4,                               t5.id_se as lvl5                               t6.id_se AS lvl6                                                FROM section AS t1              LEFT JOIN section AS t2 ON t2.id_se = t1.parent_se_id              LEFT JOIN section AS t3 ON t3.id_se = t2.parent_se_id              LEFT JOIN section AS t4 ON t4.id_se = t3.parent_se_id              LEFT JOIN section AS t5 ON t5.id_se = t4.parent_se_id                  LEFT JOIN section AS t6 ON t6.id_se = t6.parent_se_id                 WHERE t1.id_se = start посмотреть чему равнятеся t6.id_se, если null значит посмотреть t5.id_se и т.д. остальные и найти начало дерева если t6.id_se какая-то ветка, то сделать еще раз такой запрос и так далее ======================== в PostgeSQL  есть допоплнение для работы с деревом на уровне хранилица... не на уровне SQL можно PostgeSQL (правда я там сильно не интересовался деревом, говорят там несколько разных вариантов ) http://www.sai.msu.su/~megera/postgres/gist/ltree/ с одним parent_id: запросы insert и update будет быстрыми, а nested set будет обновлять вдоль и поперек всю ветку... это может быть ресурсоемко (по крайней мере так видно по структуре NestedSet и по тестах так пишут) лучше всего использовать транзакции, если использовать Nested sets может разваливатся дерево (т.к. INSERT, UPDATE и DETELE ресурсоемкий ) или нужно будет корректировать его вот тут вот есть самый быстрый и лучший вариант на innodb я это давно еще видел: http://www.opennet.ru/docs/RUS/hierarchical_data/ Код -- Adjacency List Tree Structure CREATE TABLE `al_tree` (  `id` bigint(20) NOT NULL auto_increment,  `parent_id` bigint(20) default NULL,  `name` varchar(50) NOT NULL,  PRIMARY KEY (`id`),  KEY `fk_tree_tree` (`parent_id`),  CONSTRAINT `fk_tree_tree` FOREIGN KEY (`parent_id`) REFERENCES `al_tree` (`id`) ON DELETE CASCADE ON UPDATE CASCADE ) ENGINE=InnoDB DEFAULT CHARSET=utf8   -- Nested Set Tree Structure CREATE TABLE `ns_tree` (  `id` bigint(20) NOT NULL auto_increment,  `name` varchar(50) NOT NULL,  `lft` bigint(20) NOT NULL,  `rgt` bigint(20) NOT NULL,  `level` bigint(20) NOT NULL,  PRIMARY KEY (`id`),  KEY `nslrl_idx` (`lft`,`rgt`,`level`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8   -- Materialized Path Tree Structure CREATE TABLE `mp_tree` (  `id` bigint(20) NOT NULL auto_increment,  `name` varchar(50) NOT NULL,  `path` varchar(100) NOT NULL,  `level` int(11) NOT NULL,  PRIMARY KEY (`id`),  KEY `mpp_idx` (`path`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 MyISAM: http://habrahabr.ru/blogs/perl/65495/ вот есть на триггерах: http://habrahabr.ru/blogs/mysql/63883/ http://habrahabr.ru/blogs/postgresql/63416/ не много старые http://doc.prototypes.ru/database/nestedsets/perl/module/ http://webscript.ru/stories/04/09/01/8197045 PS: я бы попробовал бы PostgeSQL http://habrahabr.ru/blogs/sql/27965/ PSS: я использую только parent_id + кэширование, для моих решений достаточно

Автор: fridkaratel 18.11.2010, 14:05

@skyboy: Спасибо, буду изучать... если вдруг ещё кому понадобится, то вот ссылка: http://www.getinfo.ru/article610.html @gcc: Спасибо за такой развёрнутый ответ  Думаю, пока реализую через несколько JOIN'ов, так как в ближайшее время уровень вложенности не привысит 10... По крайней, думаю, что не превысит... Посмотрел на структуру nested set - думаю, использовать её мне смысла нет - в ней есть как плюсы, так и минусы... В дальнейшем, как вариант, думаю всё же иметь доп. столбцы для своего рода кэша... Опять же склоняюсь к той идеи, как написал в 1м посте  Ну а пока... а пока буду через JOIN'ы и возьму 1й код gcc ;)

Автор: skyboy 18.11.2010, 14:53

Цитата(fridkaratel @  18.11.2010,  13:05 ) в ней есть как плюсы, так и минусы покажи мне структуру без "минусов" - ограничений, нюансов, неоднозначностей.

Автор: fridkaratel 18.11.2010, 15:37

@skyboy: Э...  Все с минусами  Но, прочитав и изучив, понял, что она слишком большая для моих задач ;)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)