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

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