Деревья ltree в PostgreSQL – простым языком16.11.2023 13:15

Привет, 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

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

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

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

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

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

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

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

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

Первым шагом мы берём все категории (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 выглядит примерно так:

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

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

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

Заключение

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

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

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

© Habrahabr.ru