Создать дерево с условием?

Question

[Андрей Бойченко]

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

Предположим есть следующая структура в таблице БД.
Users
1.id
2.name
3.affiliated_by

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

Если запись найдена, то мы берем идентификатор этой записи и снова проверяем, существует ли записи, где affiliated_id будет равна предыдущей записи. Соответственно таким образом я получу корректную цепочку пользователей. Укажите на мои и шибки и правильный путь для решения задачи, если можно с примерами, буду крайне признателен. Спасибо!

$users = [
            0 => ['id' => 1, 'name' => 'Name', 'affiliated_by' => null],
            1 => ['id' => 2, 'name' => 'Name', 'affiliated_by' => 1],
            2 => ['id' => 3, 'name' => 'Name', 'affiliated_by' => 1],
            3 => ['id' => 4, 'name' => 'Name', 'affiliated_by' => 2],
            4 => ['id' => 5, 'name' => 'Name', 'affiliated_by' => 3],
            5 => ['id' => 6, 'name' => 'Name', 'affiliated_by' => null],
            6 => ['id' => 7, 'name' => 'Name', 'affiliated_by' => null],
            7 => ['id' => 8, 'name' => 'Name', 'affiliated_by' => 7],
        ];

        $refs = [];
        $uid = 1;

        foreach($users as $user)
        {
            if ($user['id'] == next($users)['affiliated_by'])
                $refs[] = $user;
        }

На выходе, хотелось бы получить следующий массив

$refs = [
            0 => ['id' => 2, 'name' => 'Name', 'affiliated_by' => 1],
            1 => ['id' => 3, 'name' => 'Name', 'affiliated_by' => 1],
            2 => ['id' => 4, 'name' => 'Name', 'affiliated_by' => 3],
            3 => ['id' => 5, 'name' => 'Name', 'affiliated_by' => 4],
        ];

Comments

[alex-1917]

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

[Андрей Бойченко]

alex-1917,Чем плоха такая структура БД?

[alex-1917]

Андрей Бойченко, не расширяемая

[Андрей Бойченко]

alex-1917, Почему именно 2? Растолкуйте пожалуйста, буду крайне признателен.

[Андрей Бойченко]

alex-1917,

users
1.id
2.name

refs
1.id
2.uid
3.affiliated_by

Примерно такую структуру вы предлагает?

[alex-1917]

Андрей Бойченко, да, типа того.

Answer 1

[Immortal_pony]

Уверен, что задача простая, но я никак не соображу.

Абсолютно напрасно, задачи с деревьями довольно сложны.

Предположим есть следующая структура в таблице БД.
Users
1.id
2.name
3.affiliated_by

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

Для вашей структуры придется вытащить всех пользователей из БД и потом вручную с помощью рекурсии построить цепочку. Примерно так:

function buildAffiliateChain($for, $users) {
    $chain = [];
    
    $affiliatedUsers = array_values(array_filter($users, function($user) use ($for) {
        return $user['affiliated_by'] === $for;
    }));
    
    foreach ($affiliatedUsers as $affiliatedUser) {
        $subscequentChain = buildAffiliateChain($affiliatedUser['id'], $users);
        $chain = array_merge($chain, [$affiliatedUser], $subscequentChain);
    }
    
    usort($chain, function($someUser, $otherUser) { 
        return $someUser['affiliated_by'] > $otherUser['affiliated_by'] ? 1 : -1;
    });
    
    return $chain;
}

Если количество пользователей будет измеряться тысячами, то подобный алгоритм будет крайне неэффективен. На малых объемах проблем не будет.

PS Рекурсию можно использовать и в поcледних версиях MySQL, так что аналогичным способом можно решить вопрос и на уровне БД. Однако производительность от этого не вырастест.

Comments

[Андрей Бойченко]

Большое спасибо за содержательный ответ. Статью обязательно изучу, всегда хорошо понимать суть. Один вопрос, а что собственно ожидается первым аргументом для вашей функции?
Допустим сайт на довольно дешевом шаред хостинге, нагрузка в 3-4к пользователей уже будет критичной для подобного алгоритма?

[Immortal_pony]

Андрей Бойченко, первым аргументов ожидается userId для которого необходимо построить цепочку.

нагрузка в 3-4к пользователей уже будет критичной для подобного алгоритма?

Предположу, что будет заметно, но не критично. Думаю, что на 0.5-1сек уменьшится скорость загрузки страницы. Но точно можно узнать только проверив. :)
Можете имплементировать этот алгоритм, а потом , если упретесь в его призводительность, можно заменить на closureTable - он не потребует изменения существующей структуры таблиц.

[Immortal_pony]

Андрей Бойченко, Пример: sandbox.onlinephpfunctions.com/code/67b66a431401e1...

[Андрей Бойченко]

Immortal_pony, только вот, код не корректно себя ведет. Если я укажу for = 1, то получу пустой массив. Хотя пользователь с id = 1 должен иметь под собой записи 2-5. А если укажу id = 8, то получу данные с пользователей с id 5,3,1 хотя этот пользователь не приглашал никого.

Относительно скорости, я буду использовать кеширование, потому вряд ли замечу разницу в производительности. Но таки буду рад, если нагрузка выростет достаточно, для того чтобы все переделать.

[Immortal_pony]

Андрей Бойченко, моя функция строит цепочку в другую сторону. Если я правильно понял, то вам необходим такой варинт:

function buildAffiliateChain($for, $users) {
    $chain = [];
    
    $affiliatedUsers = array_values(array_filter($users, function($user) use ($for) {
        return $user['affiliated_by'] === $for;
    }));
    
    foreach ($affiliatedUsers as $affiliatedUser) {
        $subscequentChain = buildAffiliateChain($affiliatedUser['id'], $users);
        $chain = array_merge($chain, [$affiliatedUser], $subscequentChain);
    }
    
    usort($chain, function($someUser, $otherUser) { 
        return $someUser['affiliated_by'] > $otherUser['affiliated_by'] ? 1 : -1;
    });
    
    return $chain;
}

Пример: sandbox.onlinephpfunctions.com/code/adf841ce651318...

[Андрей Бойченко]

Immortal_pony, здесь вы используете рекурсию, верно? К слову, при работе с деревьями, рекурсия единственный вменяемый вариант?

[Immortal_pony]

Андрей Бойченко, да, здесь я использую рекурсию.

К слову, при работе с деревьями, рекурсия единственный вменяемый вариант?

Рекурсию всегда можно заменить на while. Вот пример. Но на мой взгляд рекурсия читабельнее в данном случае. Что касается производительности, то разница будет несущественная.
При использовании более продвинутых способов хранения деревьев в БД рекурсия вам также не понадобится (см. мой пост выше).

[Андрей Бойченко]

Immortal_pony, Спасибо за исчерпывающие ответы и помощь в решении моей проблемы!

Answer 2

[Ice]

Может брать сразу необходимые, отсортированные данные?

SELECT id, name, affiliated_by FROM Users WHERE affiliated_by !=null ORDER BY affiliated_by

Comments

[Андрей Бойченко]

Но такой запрос отдаст мне все записи в которых affiliated_by не равен null, верно?

[Ice]

Андрей Бойченко, да, все верно
Информация по операторам https://www.w3schools.com/sql/sql_where.asp
!= эквивалентен <>

[longclaps]

IS NOT NULL

[Андрей Бойченко]

IceRD, но суть в том, что мне не нужны все записи.
Допустим авторизированный пользовательимеет id = 1. Мне нужно получить все записи с affiliated_by = 1. Допустим - это будут 2 записи с id = 4,5. После этого мне необходимо получить все записи с affiliated_by = 4 и 5. И нужно возпроизвести всю цепочку.
Я не силен в БД, но думаю, что такое условие в запросе не написать.

Answer 3

[heartdevil]

Точно не могу проверить, но попробуйте такого вида запрос

SELECT u.id, u.name, u.affiliated_by FROM Users AS u 
LEFT JOIN Users AS u2 On u.id = u2.affiliated_by
ORDER BY u2.affiliated_by

(надо будет подстроить INNER/LEFT ну и сортировку)

Comments

[Immortal_pony]

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