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

123
Solmyr
На сайте с 10.09.2007
Offline
501
#11

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

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

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

VHS
На сайте с 28.09.2007
Offline
142
VHS
#12

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

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

Solmyr:
чтобы быстро можно было выполнять для конкретного объекта операцию поиска цепочки всех родителей
Solmyr:
Есть еще момент модифицировать данные.

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

LEOnidUKG
На сайте с 25.11.2006
Offline
1678
#13
Если вопрос в нескольких десятках/сотнях записей, тогда конечно, нет смысла насиловать мозг.

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

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

✅ Трастовых площадок под размещение статей и ссылок. Опыт 15 лет! ( https://searchengines.guru/ru/forum/675690 ) ⭐ Купить вечные трастовые ссылки для сайта ( https://getmanylinks.ru/?srh ) ⭐ Новый аналог AllSubbmitter https://getmanylinks.ru/getmanysubmits.html (Бесплатное демо)
A
На сайте с 19.07.2010
Offline
130
#14
_AXE_:
Используйте Nested Sets (вложенные множества) для хранения деревьев сложной структуры.

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

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

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.

.............
Solmyr
На сайте с 10.09.2007
Offline
501
#15

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

A
На сайте с 19.07.2010
Offline
130
#16
Solmyr:
мне нужны для конкретных элементов все родители. То есть читать дерево надо в обратную сторону, не от корня к ветвям, а от какого-то места к корню. Причем неплохо если эту операцию можно выполнять пакетно, т.е. найти всех родителей для вот этих 50 штук элементов.

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

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 // получить всех родителей для элемента

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

Для этого ИМХО лучше всего подходит MP

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

VHS
На сайте с 28.09.2007
Offline
142
VHS
#17

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

bums
На сайте с 03.07.2006
Offline
430
#18

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

Недорогая регистрация и продление доменов RU/SU/РФ/COM/NET/ORG/и т.д. ( https://www.regnic.name/?sesign ) в РЕГРУ, РЕГТАЙМ, Р01, РУЦЕНТР. А так же хостинг и SSL сертификаты.
edogs software
На сайте с 15.12.2005
Offline
771
#19
LEOnidUKG:
Это уже теории.

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

LEOnidUKG:
Я пишу как делаю на практике и вещь, которая работает достаточно быстро.
Я привожу реальные примеры кода, которые работают. А не какие-то там join, где-то когда будут и как они там будут ХЗ.

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

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

LEOnidUKG:
Я join вообще терпеть не могу, юзаю их очень редко т.к. они достаточно мощно грузят БД если объёмы данных большие.

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

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

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

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

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

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

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

Разработка крупных и средних проектов. Можно с криптой. Разумные цены. Хорошее качество. Адекватный подход. Продаем lenovo legion в спб, дешевле магазинов, новые, запечатанные. Есть разные. skype: edogssoft
VHS
На сайте с 28.09.2007
Offline
142
VHS
#20

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

123

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий