vorst.ru - Как устроена структура Nested Set
Статьи из рубрики nested-set

Виджет

выбор всех статей по рубрике

В конце предыдущей статьи были указаны две вещи, которых не хватает для начала использования рубрикатора.

Первая из них - необходимо добавить поле rubric в таблицу post. С этой операцией связано и изменения в модели common/models/Post, которые очевидно касаются методов rules() и attributeLabels().

Кроме этого нужно добавить обработку выбранной пользователем рубрики в actionIndex() контроллера frontend/controllers/PostController.


Контроллер

элементарные, но достаточные действия над деревом Nested Set

Все необходимые методы, для управления деревом Nested Set уже определены в расширении.

Поэтому изменения в стандартном контроллере совсем небольшие. Нужно, например, вместо стандартного метода save() модели использовать метод prependTo() расширения, а вместо delete(), deleteWithChildren().

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

Но, по порядку.


Ввод рубрики

Редактирование, удаление узлов в дереве Nested Set

Мы, в общих чертах, разобрались с деревьями Nested Set и создали модель для хранения дерева. В модели определили пару простых методов.

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

Для добавления рубрики нужно определить, в какую родительскую рубрику будет входить новая рубрика. Этой цели служит поле $parent_node модели.

Посмотрим, как будет выглядеть добавление.


Nested Set

Подключение расширения

Мы получили общее представление о древовидной структуре данных называемой Nested Set. Теперь пришло время подключить к блогу соответствующее расширение выполненное в виде поведения.

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

Наши задачи проще и сводятся к следующему:

  1. Управление рубрикатором - добавление и удаление рубрик, редактирование, отображение списка рубрик для визуального контроля.
  2. Закрепление статьи за рубрикой.
  3. Вывод списка рубрик для выбора нужной рубрики.

Для их решения, как обычно, нужна модель, контроллер, представления и еще виджет.


Рубрикатор

как устроена структура данных Nested Set

Рубрикатор, как средство поиска интересных статей, имеет свои недостатки - трудно придумать иерархию, названия рубрик, трудно потом решить к какой конкретно рубрике относится статья. "Но, так принято" - скажите вы и будете правы.

Поэтому, давайте делать рубрикатор.

У нас есть рубрики записанные в правой колонке:

id lft rgt level name
1 1 12 1 Root
2 2 5 2 --- Data structures
3 3 4 3 ------ Nested Set
4 6 9 2 --- Searching
5 7 8 3 ------ Posts chains
6 10 11 2 --- About sites

И нужна структура данных, которая помогла бы нам:

  1. Выводить список в заданном порядке.
  2. Делать отступ при выводе названия рубрик.
  3. Находить все под-рубрики выбранной рубрики, чтобы выводить соответствующие статьи.


Поиск



Рубрикатор

как устроена структура данных Nested Set

Рубрикатор, как средство поиска интересных статей, имеет свои недостатки - трудно придумать иерархию, названия рубрик, трудно потом решить к какой конкретно рубрике относится статья. "Но, так принято" - скажите вы и будете правы.

Поэтому, давайте делать рубрикатор.

У нас есть рубрики записанные в правой колонке:

id lft rgt level name
1 1 12 1 Root
2 2 5 2 --- Data structures
3 3 4 3 ------ Nested Set
4 6 9 2 --- Searching
5 7 8 3 ------ Posts chains
6 10 11 2 --- About sites

И нужна структура данных, которая помогла бы нам:

  1. Выводить список в заданном порядке.
  2. Делать отступ при выводе названия рубрик.
  3. Находить все под-рубрики выбранной рубрики, чтобы выводить соответствующие статьи.

    Поделиться

Первое требование, глядя на таблицу, можно выполнить только используя колонку lft. Других кандидатов просто нет.

Второе выполнить легко - используем значение level.

Для выполнения третьего заметим, что если мы, например, выбрали пункт "Структуры данных", то для поиска под-рубрик нужно выбрать все строки у которых lft (выбор) < lft(i) и rgt (выбор) > rgt (i). В примере этому условию отвечает только строка Nested Sets.

Для дополнительной проверки выберем рубрику "Root". Очевидно правило работает.

Как же построить такую структуру?

Предположим, что у нас пока только одна рубрика.

id lft rgt level name
1 1 2 1 Root

И добавим следующую - "Data structures". Как изменятся поля lft, rgt?

id lft rgt level name
1 1 4 1 Root
2 2 3 2 --- Data structures

Правое значение всегда должно быть больше левого и верхний уровень должен включать нижний. Новые значения отвечают этим условиям.

Добавим следующую по порядку рубрику - Nested Set.

id lft rgt level name
1 1 6 1 Root
2 2 5 2 --- Data structures
3 3 4 3 ------ Nested Set

Становится очевидным, что при добавлении берется значение rgt родителя и присваивается lft добавляемой рубрики. Значение rgt добавляемой рубрики получается прибавлением 1 к ее lft. И у всей ветки rgt увеличивается на 2.

Добавим еще одну рубрику - "Searching". Она является под-рубрикой корневой рубрики.

id lft rgt level name
1 1 8 1 Root
2 2 5 2 --- Data structures
3 3 4 3 ------ Nested Set
4 6 7 2 --- Searching

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

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

Пора выбрать расширение, которое работает с вложенными множествами или Nested Sets и подключить его к проекту. Но об этом в следующей статье).

Заключение

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

Комментарии

  • Комментарии на сайтах тоже также делаются? через Nested Sets Алексей
  • -- Можно проще. Каждый комментарий получает уникальное значение thread. Каждому ответу, тоже являющемуся комментарием, присваивается тот же thread. Вся "цепочка" вытаскивается рекурсивно. SergeyMorozov

Оставить комментарий

Только авторизованные пользователи могут оставлять комментарии. Пожалуйста авторизуйтесь или пройдите регистрацию.