Как мне выполнить обход дерева в заданной структуре? - PullRequest
0 голосов
/ 02 ноября 2009

Миссия

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

Структура стола

users
-----
user_id  
parent_id


user_meta
---------
user_id
registration_date


user_levels
-----------
user_id
level

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

Вариант использования

select
  users.user_id
from
  users
inner join
  user_meta
  on users.user_id = user_meta.user_id
inner join
  user_levels
  on users.user_id = user_levels.user_id
where
  parent_id = *x*
  and
  registration_date > *certain date*
  and
  level < *certain level*

Условия

  • Потомок пользователя считается как таковой, только если его уровень ниже заданного *certain level*. Если уровень потомка не ниже, узел является листом, но его следует исключить из подсчета.
  • Учитывая, *certain level* и *certain date* одинаковы для каждого запроса / набора запросов.

Я пытался использовать это в цикле, но количество запросов быстро возрастает. Это решение, вероятно, можно было бы использовать и хранить в задании cron, но я бы предпочел решение «как в реальном времени, как только получит».

Ответы [ 3 ]

1 голос
/ 03 ноября 2009

С вашей текущей моделью данных нет более эффективного способа сделать это, чем рекурсивный запрос к базе данных. Если вы можете изменить способ хранения данных, чтобы включить в него дополнительную информацию, вы можете использовать Модифицированный обход дерева предварительного заказа (также называемый моделью вложенного набора). Эта модель обсуждается в статье на веб-сайте MySQL . На этом веб-сайте также много примеров, просто выполните поиск по «Измененному обходу дерева предварительных заказов».

0 голосов
/ 02 ноября 2009

Существует особенность SQL99, называемая «Common Table Expression», которая позволяет создавать рекурсивные функции и эффективно обрабатывать иерархические данные, хранящиеся в реляционной базе данных.

Похоже, что MySql (пока) не реализует его, но вы можете увидеть, что можно сделать с этим: http://msdn.microsoft.com/en-us/library/ms190766.aspx

0 голосов
/ 02 ноября 2009

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

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