Как устроена структура Nested Set - vorst.ru

Рубрикатор


как устроена структура данных 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. Количество под-рубрик и уровней не ограничено.

комментарии

  • Алексей 03 Фев 2017

    Sergey Morozov 06 Окт 2017

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