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

Виджет для вывода списка рубрик Nested Set

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

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

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

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


Простые действия над деревом Nested Set

Что нужно учесть для CRUD

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

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


Представления для операций с Nested Set

Что нужно учесть в представлениях при редактировании Nested Set

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

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


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

Определение данных и необходимых методов в модели

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

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


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

Как сделать рубрикатор

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

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



Поиск



Как устроена структура данных 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

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

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