Статьи помеченные nestedset
Как устроена структура данных 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 |
И нужна структура данных, которая помогла бы нам:
- Выводить список в заданном порядке.
- Делать отступ при выводе названия рубрик.
- Находить все под-рубрики выбранной рубрики, чтобы выводить соответствующие статьи.
Первое требование, глядя на таблицу, можно выполнить только используя колонку 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. Количество под-рубрик и уровней не ограничено.
Comments
Оставьте комментарий
Только зарегистрированные пользователи могут оставлять комментарии. Пожалуйста войдите или пройдите регистрацию.
Можно авторизоваться, используя социальную сеть-
-
-