Комментарии 24
Поздравляю, вы изобрели очень инновационный materialized path, который был придуман лет 50 назад.
Сама реализация прихрамывает.
Почему-то в части запросов не используются подготовленные выражения
Условие if ($userId == 1) { это какой-то костыль
Для действий, требующих нескольких запросов, надо бы освоить транзакции. Это несложно, а без них вы быстро получите рассинхрон.
В целом не очень понятно, зачем нужны level и col — эти данные вполне считаются налету.
От себя порекомендую переименовать статью и вступление.
MLM — это не стратегия эффективного маркетинга, а мошенническая схема. Статья прекрасно обойдется без упоминания этой сомнительной практики, достаточно просто написать про работу с деревьями.
Согласен что материализованный путь был открыт очень давно и описывался в учебниках наверное по первым FoxPro базам данным в 90 годах, я предоставил пример реализации с некоторыми нюансами которые позволяют снизить нагрузку на SQL сервер, поэтому в таблице хранится уровень и количество приглашенных (при больших объемах базы значительные нагрузки). Выбрал тематику MLM потому, что проблема возникла в этой сфере, притом в компании занимающейся косметикой, а не очередной пирамидой.
Не очень понятно, к чему эти ряженые контроллеры и автолоад, если в примерах все равно require_once 'Models/User.php';
Не очень понятно, почему две папки Models
Не очень понятно, почему примеры предлагается запускать из папки examples, если код в них предполагает запуск из корня
Не очень понятно, куда делся файл config.php.
Не очень понятно, что в репозитории делает файл config/database.php. Файл с настройками должен исключаться из кодовой базы, а на его месте должен лежать какой-нибудь database.sample.php. Ну или в самом продвинутом варианте — получение настроек из окружения/файла .env
Не очень понятно, при чем здесь PHP8. Сделали бы хотя бы объявления типов, чтобы соответствовать такому ограничению. А текущий код и на 5 будет работать.
Не очень понятно, почему дока на английском, а названия на русском — все эти rek, col. Надо выбрать что-то одно. Я рекомендую сделать ref и len.
Да, и самое смешное.
Непонятно, при чем тут рекурсия.
Ну то есть в теории понятно, но в самом-то классе нет методов, которым бы она понадобилась при использовании списков смежности. Того самого запроса с получением всех подчиненных нод. Все операции производятся только с непосредственными рефералами, но это и в списке смежности один запрос.
Спасибо за Ваши уточнения, попробую внести корректировки в Git, Вы хотите готовое решение для Вашей задачи?
Спасибо конечно, но все свои задачи я могу решить сам :)
Мы говорили о ваших.
Что я хочу — так это видеть в прилагаемом примере рабочий код, а не тяп-ляп для галочки. Зачем вообще размещать код, две трети которого либо нигде не используется, либо не работает?
Еще я хочу видеть код, который соответствует сделанным заявлениям.
Я не вижу в коде метода для выборки "всех пользователей на 23-м уровне" — того, ради чего все и затевалось. И это не "моя задача". Это ваша задача, которую вы озвучили в статье :)
Причем если вы добавите ее решение, то оно будет не с помощью вашего "инновационного подхода", а с помощью банальной денормализации. А вот изменение этого значения при удалении ноды уже будет делаться с использованием материализованного пути.
Все это должно быть написано в статье, а не в комментариях под ней.
Я понимаю, что кустарю-одиночке неоткуда узнать стандартные решения и их названия. Но если уж пишете статью, то попробуйте хотя бы поискать, как называются использованные вами решения. И написать, какие конкретно оптимизации были достигнуты с их помощью.
Еще я хочу видеть в статье обоснованные заявления. Для получения пользователей 23 уровня через списки смежности никакая рекурсия не нужна. Я даже не представляю, откуда вы это взяли. Большая часть задач по обходу дерева решается безо всякой рекурсии, простым циклом, и этот случай не исключение. В общем случае нужно те же 23 запроса: сначала получаем все корневые ноды, следующим запросом всех их детей, и так далее. На практике это количество может быть увеличено максимум на порядок, только за счет разбиения запросов на пакеты. Тоже не сахар, но никак не "201,326,592 операций".
В итоге получается, что вы так и не продемонстрировали собственно реального кейса, в котором ваше решение действительно ускоряет работу по сравнению с традиционной схемой данных (списком смежности).
Пример кода лежит на Git в папке с примерами get_users_by_level.php
Ваш вариант будет выглядеть
$level=23;
$usersByLevel = $user->getUsersByLevel($level);
echo "<pre>";
print_r($usersByLevel);
echo "</pre>";все варианты решения я не предусмотрю
Я сейчас вижу что сам ступил, и проглядел метод getUsersByLevel, прошу прощения.
Но все остальные замечания остаются в силе.
Дело не в наличии примера в папочке examples. А в том, что вы, похоже, и сами не очень понимаете, как работает ваш "инновационный метод". Или, по крайней мере, не в состоянии это объяснить.
PS. Примеры всё ещё не работают.
Если четче сформулировать проблему, то сейчас вашу статью может понять только тот, кто и так знает, как это работает. Но ему она, понятное дело, и не нужна.
Для тех, кто не знает, она тоже оказывается бесполезной. Потому что даже погуглить нельзя — вы не используете общепринятую терминологию.
Поэтому просто добавьте вот это в текст введения:
… инновационный подход к обработке больших древовидных структур, который позволяет оптимизировать анализ и управление данными за счет использования двух методик:
- денормализации, когда уровень узла просчитывается заранее
- способа хранения деревьев, который называется materialized path. Использование которого позволяет осуществить поиск всех подчиненных узлов одним запросом.
Так, во-первых, статья встроится в существующий корпус знаний, и любой человек сможет нагуглить дополнительную информацию по этим методикам. А во-вторых, в статье появится хоть какое-то объяснение использованных методик, и какая за что отвечает.
И надо либо убрать пассаж про " 201,326,592 операций", либо придумать задачу, для решения которой действительно может понадобиться рекурсия.
А чем не подошел метод nested sets? Да, он чуть более ресурсоемкий при добавлении новых записей, но зато очень эффективен на выборках. Тем более, что при работе с MLM-структурами нередко требуются специфические выборки, например, сравнение двух веток, подсчет дочерних дистрибьюторов на определенных уровнях и т.д., и такой метод хранения структуры позволяет все эти операции выполнять одним запросом. И все это без LIKE, а на числовых индексированных полях
Мой метод предоставляет интуитивную наглядность и гибкость для работы с произвольным количеством дочерних элементов, что упрощает внедрение и сотрудничество в команде. Он также позволяет выполнять специфические выборки одним запросом, как и Nested Sets, но с меньшей сложностью и более простым пониманием структуры данных, что может быть преимуществом в MLM-структурах.
Где же тут наглядность? Если нет нормального человеческого интерфейса, то наглядно лишь представление аплайна (что требуется не так уж и часто), больше никакой наглядности нет. Но если nested sets сложен для понимания, и увеличение времени запросов в разы (если не на порядки) не смущает, то можно и так, конечно.
сам в свое время делал млм с помощью Nested Sets.
но у Nested Sets дорогая вставка. при 10М записях в худшем случае при вставке будет 10М обновленных записей.
В данном случае худший случай это какой, вставка узла в корень? Во-первых, это крайне редкий случай в МЛМ. А, во-вторых, в таком кейсе у автора также будет апдейт всех записей (т.к. надо будет обновить путь для всех узлов)
да нет, не в корень, там может быть вообще 1 чел. много обновлений при вставке под человека у которого Left/Right маленькие, причем это будет даже если чел в 20 уровне.
в materialized path ничего обновлять не надо. обновлять там надо будет только при перемещении поддерева в другое место, и то только у тех кого перемещают.
Соглашусь, что в случае с Nested Sets обновлять ключи Left/Right у какого-то количества записей надо будет почти всегда. Но какие операции выполняются чаще - вставки или выборки? Насколько я знаю, выборка выполняется гораздо чаще - тут и выборка поддерева структуры, и получение списка элементов на определенном уровне конкретного дистрибьютора и пр. В случае с хранением пути это все выборки через LIKE '%x%', а в Nested Sets - выборка по индексированным числовым ключам, что однозначно быстрее будет. А уж если речь о бинарном дереве, которое очень быстро и неравномерно растет в глубину, и, стало быть, увеличивает длину пути, то выборка по путям особо тормозить будет
можно поспорить. если это реально 10М зарегистрированных, то и прирост там тоже большой, сотни и тысячи в сутки. а выборка как описано в статье 1 раз в сутки обрабатываются все.
автор немного неправильно сделал, надо было делать через LIKE 'x%' тогда и с индексами было бы (но код надо дорабатывать чтобы вписывать в запрос полный путь до выбираемого).
Пока left/right обновляются в транзакции все записи будут блокироваться. Сколько времени это займет? А если это заметят и их начнут ддосить фейк регистрациями? Это разве что обновлять их в фоне массово через опеределенный промежуток времени.
Можно рассмотреть вынос Nested Sets полей во вторую таблицу One-to-One. чтобы не блокировать важную таблицу Users во время записи.
В любом случае в лоб может и не заработать.
Nested Sets мне нравится, почитал бы реальное сравнение их работы на 10М - 100М записях, на базах mysql/postgres. Возможно для каждой БД будет свой победитель.
У postgres, например, вообще при обновлении даже числового поля, данные всей строки записываются в новое место. то есть надо будет всю таблицу Users перезаписать заново в новое место.
А еще репликация есть, и она может быть по-разному настроена...
Вот такой рекурсией разве не проще будет? Всего будет 22 запроса в вашем случае
function db_get($query) {
// для получения данных из БД
}
function get_childs($ids) {
$res = [];
$get_ids = db_get('select id from users where parent_id in (' . implode(',', $ids) . ')');
if ($get_ids) {
$res = array_merge($res, $get_ids, get_childs($get_ids));
}
return $res;
}
print_r(get_childs([1]));Нет, не проще.
Попробуйте прочитать статью и понять, что в ней написано.
У автора это делается одним запросом, а не двадцатью двумя.
(Другое дело что он там заявлял про рекурсию с 201,326,592 запросами — что, конечно же, чушь).
Кроме того, сам по себе ваш код дважды бессмысленный.
Во-первых, здесь вы просто получаете все id из таблицы. Это можно сделать и одним запросом select id from users. Тем более что автору нужно получить только последний уровень, а не все записи.
Во-вторых, ну зачем здесь рекурсия-то?
Это обычный цикл.
while ($get_ids = db_get('...') {
}Ну ок, по уровню можно чуть изменить логику, а что по ресурсозатраности? Я не очень силен в этом, но разве поиск оператором like не будет тяжёлее для бд, по сравнению поиска по индексированному id?
Если нормально делать, то не будет.
Лайк без процента слева вполне себе использует индекс.
И в этом как раз и заключается одно из достоинств материализованного пути. Всех потомков найти не проблема. И даже не будет нужна денормализация, с которой автор так носится.
Но у него криво сделано, там % ставится и слева тоже:
WHERE road LIKE '%|$userId|%'";и индекс не задействуется. Хотя путь к ноде всегда известен, и подставить его руками вместо % — не проблема.
Вообще материализованный путь — это отличная штука. Самый наглядный способ представления дерева.
Публикации
Эффективный алгоритм обработки больших баз данных MLM-структур