Привет, Habr! Меня зовут Оля Плюта, я продуктовый аналитик маркетплейса Uzum Market. Недавно моим коллегам понадобилось освоить такую структуру данных, как иерархическое дерево ltree в PostgreSQL. Я агрегировала для них то, что знала и что решало их задачи, а потом решила написать статью о базовых приёмах извлечения данных из таких деревьев – вдруг вы тоже хотите в этом разобраться.

Что такое дерево ltree

Рассмотрим на примере категорий товаров: такая иерархическая структура данных, в которой хранятся адреса, или пути, от более старших и общих категорий (скажем, "Одежда") к более конкретным, например, "Женская ветровка": "Одежда" -> "Женская одежда" -> "Женская верхняя одежда" -> "Женская ветровка".

Для примера, пусть наши данные записаны в таблице category, поле path и выглядят так: 11.22.33.44 (здесь и далее из соображений безопасности данных используются выдуманные числа). Каждое из чисел 11, 22, 33 и 44 – это ID категорий и подкатегорий, составляющие наш путь. То есть 11 – самая старшая (крупная) категория ("Одежда"), а 44 – самая мелкая ("Женская ветровка"). Путь 11.22.33.44 указывает нам, что наш товар относится к категории "Женская ветровка", которая, в свою очередь, входит в категорию 33 – "Женская верхняя одежда", та является подкатегорией категории 22 – "Женская одежда", а она, наконец, входит в состав "Одежды".

В общем случае в адресах ltree можно использовать символы A-Za-z0-9_, причём длина звена ограничена 1000 символами, а максимальное число звеньев – 65535 (документация на английском).

Важный момент

Количество звеньев в path может разниться. Категория первого уровня (самая крупная), конечно, есть у всех товаров, а вот дальше у одних товаров path может состоять из двух звеньев, а у других, скажем, из пяти. 

Поэтому при определении категорий второго, третьего и т.д. уровней нужно проверять, есть ли они вообще.

Основные операции с деревом path, которые чаще всего используются в аналитике: 

  1. Узнать "родительские" (более крупные) категории данной категории – например, найти, к какому разделу относится "Женская ветровка",

  2. Узнать "дочерние" (более мелкие) категории данной категории – например, определить, какие категории товаров входят в категорию "Женская одежда",

  3. Вывести категорию первого, второго, ..., n-го уровней – например, для группировки/фильтрации товаров на дашборде – категория "Одежда", более мелкая категория "Женская одежда", ещё более мелкая категория "Женская верхняя одежда" и т.д.

Общие принципы – как искать категории-”родители” и категории-”потомки”

Мы строим конструкции вида WHERE path ~ ‘…’, в которых указываем, как выглядит искомый адрес. Очень похоже на синтаксис регулярных выражений “some_text like some_string_expression”: так, '*' означает от 0 до нескольких символов. Например, мы ищем “родителей” категории 101. Значит, полный путь этой категории выглядит как “something.101”. Вот это something обозначается звёздочкой:

path ~ '*.101'

А если ищем потомков, значит, в их “пути” будет “something1.101.sometring2” (something1 – возможные родительские категории нашей 101, sometring2 – ее дочерние категории).

path ~ '*.101.*'

Однако согласно документации, для таких сравнений есть специальные операторы – “@>” и “<@”. Они оба на входе принимают два ltree, а выходе дают boolean. Оператор “@>” проверяет, является ли левое ltree “родителем” правого, а “<@” – является ли левое ltree “потомком” правого, например:

‘10.121.33’ @> ‘10.121.33.001’ -> True

‘10.121.33’ <@ ‘10.121’ -> True

‘10.121.33’ @> ‘10.121.99’ -> False

Так что для нашей задачи мы можем взять полный путь до категории 101 (если он известен) и с помощью операторов “@>” и “<@” и self join таблицы category найти “дочерние” и “родительские” категории. 

Вот несколько примеров скриптов на SQL

1. Как узнать все “родительские” категории данной категории

Например, ищем "родителей" категории 139. Для этого применяем оператор “@>”:

with

a as (
    select 
  	path as child_path
    from category
    where id = 139 -- в этой строке лежит наша дочерняя категория 139
)

select path
from category
    cross join a
where path @> child_path

Результат может выглядеть, скажем, так: 

path

100.29.139

2. Как узнать все дочерние категории данной категории

Например, ищем дочерние категории категории 121.

select path
from category
where path ~ '*.121.*'

Получаем результат наподобие такого:

path

10.121.33.001

10.121.33.002

10.121.44.101

10.121.55.505

3. Как доставать категории 1, 2, … уровней

Здесь нам понадобятся функции ltree2text и subltree, а также функция для строк btrim PostgreSQL.

В таблице categories поле category_id совпадает с последней (самой мелкой) подкатегорией данного path вот так:

category_id

path

123

11.22.33.123

456

01.02.03.456

Первым шагом мы берём все категории (category_id). Для них мы определяем ID "родительских" категорий – самой крупной (первого уровня) и второй по крупности (второго уровня). Эти ID мы будем дальше джойнить, чтобы по ним вытащить названия категорий первого и второго уровней.

with 

last_category as ( 
    SELECT 
		category_id, -- самая "мелкая" категория
		title,
        path,
		ltree2text(subltree(path, 0, 1))::int as level_1_category,
		ltree2text(subltree(path, 1, 2))::int as level_2_category
    FROM category
)

SELECT 
    lc.category_id AS category_id,
    btrim(lc.title::text) as last_level_category_title,
    btrim(c1.title::text) as level_1_category_title,
    btrim(c2.title::text) as level_2_category_title
FROM last_category lc
    JOIN category c1 ON lc.level_1_category = c1.category_id
    JOIN category c2 ON lc.level_2_category = c2.category_id

Результат в подзапросе last_category выглядит примерно так:

category_id

title

path

level_1_category

level_2_category

123

"Женская ветровка"

11.22.33.123

11

22

234

"Блокнот"

44.55.66.234

44

55

345

"Футбольный мяч"

77.88.99.345

77

88

456

"Ноутбук HP"

101.202.456

101

202

Вторым шагом мы джойним результат из last_categoryс таблицей category столько раз, сколько уровней категорий мы ищем (в нашем примере два). Таким образом мы по ID категорий первого и второго уровня определяем их названия.

Финальный результат в нашем примере будет следующим:

category_id

last_level_category_title

level_1_category_title

level_2_category_title

123

"Женская ветровка"

"Одежда"

"Женская одежда"

234

"Блокнот"

"Канцелярские товары"

"Бумажная продукция"

345

"Футбольный мяч"

"Спортивные товары"

"Товары для футбола"

456

"Ноутбук HP"

"Электроника"

"Ноутбуки"

Можно дальше аналогично искать категории третьего, четвёртого и т.д. уровней, важно лишь убедиться, что они есть у каждого конкретного товара.

Заключение

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

Это моя первая публикация на Habr. Надеюсь, она оказалась для вас понятной и полезной.

Если хотите разбираться дальше: мне очень помогла вот эта статья на Habr.

Комментарии (4)


  1. dyadyaSerezha
    16.11.2023 14:03

    1. Странно, что для таких базовых запросов по дереву надо писать довольно сложные запросы вместо встроенных функций БД.

    2. В реальной жизни те же товары могут иметь несколько путей, то есть, та же ветровка может быть и спортивным, и туристичеким товаром. Можно ли так делать? - 11.22.33.88 и 11.55.88.


  1. Akina
    16.11.2023 14:03
    +1

    Обычный материализованный путь. Ничего нового. Прочитал статью (как по мне - одна вода), прочитал документацию. По сравнению со стандартным FQPN - в чём профит-то? Этот тип хотя бы существование в таблице записи родительского узла - отслеживает? А два дерева в одной таблице хранить - можно?

    Надеюсь, хотя бы хранится всё это добро не в виде строки...


    1. ptr128
      16.11.2023 14:03

      А это и есть стандартный FQPN. Просто обвешенный синтаксическим сахаром и несколько оптимизированной для данного применения GIST индексацией


  1. ptr128
    16.11.2023 14:03

    В свое время от этого отказались из-за чрезвычайно медленной модификации GIST индекса. Расширение ltree оказалось применимо только в случаях редких модификаций незначительного количества записей в иерархии. Как решали эту проблему?