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

Как создать индекс ElasticSearch

Полнотекстовый поиск

Один парень написал: "Нужно сделать поиск слов в таблице "articles" по столбцу "content". В результатах поиска сначала выводить те, которые содержат наибольшее количество слов в статье и далее по мере уменьшения."

Мысль летит) Но ясно, что нужен полнотекстовый поиск.


WordPress плагин для недвижимости

Без изменения структуры данных

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

Чтобы разобраться, как это возможно, я решил написать плагин для агенств недвижимости. Расширять структуру данных не хотелось - это уже будет не WordPress. Решил сохранять JSON-определения объектов недвижимости в поле post_content и преобразовывать эти определения "на лету" - Demo, GitHub


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

Comments

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

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

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