Как правильно хранить структуры данных типа деревьев?

У меня записей порядка 200к+ глубина вложенности - вопрос спорный. Наверное на данный момент максимум примерно 12 но нет гарантий что в будущем не увеличится. Средняя длина веток - 5-6, ветвление на одном узле разное. И такое где 2 ветки с узла - много, и такое где 20 веток с узла - много. Такое где одна ветка с узла - нет вообще.

Но мне нужно чтобы выборка работала реально быстро. То есть формулировка "достаточно быстро", кэши всякие, памяти и т.п. не подходят. Нужно научно обоснованное понимание, какой вариант будет самым быстрым, а не достаточно быстрым.

Пока я больше склоняюсь к Materialized Path но протестирую два варианта - когда пути хранятся в виде текстовой строки и когда пути хранятся в виде отдельной таблицы.

LEOnidUKG, поверь, твой метод проиграет даже 8 последовательным запросам по итоговой скорости построения, по ресурсам тем более. Нужно различать общий размер таблицы и размер выборки. Или на футбольных сайтах бывает полмиллиона комментариев к одной новости? Если вопрос в нескольких десятках/сотнях записей, тогда конечно, нет смысла насиловать мозг.

---------- Добавлено 30.01.2016 в 11:05 ----------

Личное мнение - я солидарен с edogs, поставлю на МР. Количество данных не критично для обновления, поиск будет максимально быстрым, работа достаточно удобной.

Об этом я и говорил, что тут нужно детали разбирать ТЗ.

Конечно если, как у Solmyr это базис всего, то конечно тут нужно подход более основательный.

н-да, хорошую идею всегда можно угробить - статья и реализация жесть...

В статье предлагают такую структуру данных:

CREATE my_tree (

	id INT(10) NOT NULL AUTO_INCREMENT,

	name VARCHAR(150) NOT NULL,

	left_key INT(10) NOT NULL DEFAULT 0,

	right_key INT(10) NOT NULL DEFAULT 0,

	level INT(10) NOT NULL DEFAULT 0,

PRIMARY KEY id,

INDEX left_key (left_key, right_key, level)

)

1. parent - не хранится, при малейшем сбое/глюке - дерево посыпится. Операции вставки/удаления/перемещения - "высший" и бесполезный пилотаж. Вся мольба на поля left_key и right_key... Бред.

2. level - бесполезное поле, т.к. выборка может идти не от корня. Удобнее формировать его на лету, это не ресурсоемкая операция.

Более удобная и надежная такая структура данных:

CREATE my_tree (

	id INT(10) NOT NULL AUTO_INCREMENT,

	name VARCHAR(150) NOT NULL,

	left_key INT(10) NOT NULL DEFAULT 0,

	right_key INT(10) NOT NULL DEFAULT 0,

	parent INT(10) NOT NULL DEFAULT 0,

PRIMARY KEY id,

INDEX left_key (left_key)

)

В этой структуре значимые поля: id и parent.

left_key и right_key - просто "технические" поля, они заполняются при ребилде дерева. Удобно перед ребилдом их вообще обнулять, чтобы автоматом находить и исправлять возможные "потерянные" ветки.

Все операции по модификации дерева сводятся к изменению одного поля - parent.

Добавление/перемещение/массовая вставка - баналоно просто, ставим нужный parent и все.

Удаление всей ветки - легко, удаляем строки - это все.

После модификации дерева - запускаем ребилд, который заполняет поля left_key и right_key. Эти поля нужны для очень быстрого чтения любого куска дерева.

Сам процесс получения всего дерева или любого куска дерева сводится к двум sql запросам, упрощенно:

1. select left_key, right_key from table where id='$id' // получаем left_key и right_key нужного(корневого) элемента.

(выборка быстрая, т.к. идет по примари или уникальному ключу)

2. select .... where left_key between $left_key and $right_key order by left_key asc // получаем само дерево или нужную ветвь

(выборка быстрая, т.к. идет по индексу left_key)

Все, дерево у нас уже есть. На пхп один раз(один цикл) пробегаемся по нему - заполняем level и children.

admak, Мне не нужно читать ветвь, мне нужны для конкретных элементов все родители. То есть читать дерево надо в обратную сторону, не от корня к ветвям, а от какого-то места к корню. Причем неплохо если эту операцию можно выполнять пакетно, т.е. найти всех родителей для вот этих 50 штук элементов. Для этого ИМХО лучше всего подходит MP

Тоже два запроса:

1. select left_key, right_key from table where id='$target'

2. select .... where left_key <= $left_key and right_key >= $right_key order by left_key asc // получить всех родителей для элемента

Можно поробовать объединить эти два запроса в один, тогда будет "пакетный" режим.

не скажу, почитать про него нужно

admak, а как с удобством переноса веток дерева обстоит дело? Удобно ли?

Solmyr, посмотри, м.б. подойдет http://www.sql.ru/articles/mssql/01091502treesinsql.shtml

Теории это думать что 50мб данных в пхп займут мало. На практике (в зависимости от версии) от 100 до 200мб. Это на сервере разработчика памяти навалом и никому кроме пхп не нужна, в реальности память даже по нынешним меркам неплохо бы не разбрасывать.

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

Приведенный Вами способ при всего 32 одновременных пхп процессах сожрет не меньше 3гб памяти (при 50мб данных). Приведенный нами - пару мегабайт. А это тоже отразится на скорости.

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

Выборки быстрее чем MP у Вас никто не сделает. Но там Вы можете упереться в апдейты, при большой таблице. Хотя при 200к записей проблема вряд ли возникнет. Главное апдейты тоже делайте на mysql запросом, replace like допустим

Научно обоснованное понимание этого в том, что MP это один простой запрос для выборки всех ИД родителей, чем-то это похоже на ситуационно обоснованный встроенный кэш - где вне зависимости от структуры - один запрос и оппа - у Вас данные.

По поводу id-parentid и join-ов. Они хорошо работают до 16 уровня вложенности. Для бОльшего уровня вложенности придется немного колхозить и прелесть идеи уже меньше. Так что если у Вас уже максимум 12, лучше MP, а то вдруг вырастет до 16+

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