Materialized Path – создаём своё первое дерево

Всем привет! Меня зовут Хусрав, я бэкенд разработчик в компании Bimeister. В этой статье я бы хотел бы поговорить о способе поиска родительских и дочерних элементов структуры посредством PostgreSQL Materialized Path.

Цель

Упорядочить собственное понимание темы и на простых практических примерах продемонстрировать работу Materialized Path. Эти примеры могут оказаться полезными для работы с иерархическими данными посредством реляционной СУБД.

Статья является вводной и рассчитана на людей, незнакомых с темой.

Дисклеймер

Сразу оговорюсь, что существует несколько способов хранения деревьев в реляционной базе. Для ознакомления со всеми ними рекомендую к прочтению статью моего коллеги на эту тему. Ниже я рассмотрю лишь один из них, и упор будет сделан, прежде всего, на лёгкость воспроизведения примеров.

Немного предыстории

До настоящего времени моим основным стеком была связка C# и MSSQL, и мне не приходилось сталкиваться с деревьями. Я привык думать, что когда речь заходит о сложных структурных данных, то решение однозначно упирается в графовую БД, однако здесь я был ограничен реляционной БД. В этих ограничениях единственно логичным для работы с деревьями решением было использование возможности хранения дерева в PostgreSQL посредством Materialized Path. Этим подходом я и спешу поделиться с вами.

Итак, начнем!

Представим, что у нас есть некое дерево классификации транспортных средств, и наша задача — эффективно получить дочерние и родительские элементы относительно заданного элемента.

В таком случае мы можем организовать дерево посредством Materialized Path… 

Для начала настроим наше окружение

Начнем с установки базы данных PostgreSQL в docker-контейнер.

1. Устанавливаем docker desktop.

2. Открываем любимый терминал, в моем случае, это git bash.

3. Скачиваем образ postgres c docker hub.

   docker pull postgres

4. Создаем docker-контейнер с нашей базой данных.

   docker run --name myPostgresDb -p 5455:5432 -e POSTGRES_USER=postgresUser -e POSTGRES_PASSWORD=postgresPW -e POSTGRES_DB=postgres -d postgres

    Описание:

   • myPostgresDb — имя контейнера

   • 5455:5432 — порт для внешнего подключения к контейнеру

   • postgresUser — пользователь

   • postgresPW — пароль

   • postgres — имя базы данных

5. Устанавливаем любимый редактор для работы с базой данных PostgreSQL. В моем случае это PgAdmin.

6. Настраиваем подключение в редакторе:

   Name: MyPostresDB.

   Вкладка Connection:

   Host: localhost

   Port: 5455

   Maintenance Database: postgres

   UserName: postgresUser

   Password: postgresPW

Дополнительная информация по установке PostgreSQL в docker.

Наполним демонстрационными данными наш стенд

1. Создаем таблицу и индекс GIST:

   create table transport (name text, path ltree);

   create index path_gist_idx on transport using GIST (path);

   Индекс GIST дает возможность выполнять такие выражения (более подробное описание):

    <, <=, =, >=, >, @>, <@, @, ~, ?

   Примечание: если у вас при создании таблицы выдает ошибку, что нет такого типа, как ltree, то выполните следующую команду:

   create extension ltree

2. Наполняем тестовыми данными:

   insert into transport values ('Transport', 'Transport'); insert into transport values ('Car', 'Transport.Car'); insert into transport values ('Truck', 'Transport.Car.Truck'); insert into transport values ('Van', 'Transport.Car.Van'); insert into transport values ('Sedan', 'Transport.Car.Sedan'); insert into transport values ('Boat', 'Transport.Boat'); insert into transport values ('Yacht', 'Transport.Boat.Yacht'); insert into transport values ('SailBoat', 'Transport.Boat.SailBoat'); insert into transport values ('Aircraft', 'Transport.AirCraft'); insert into transport values ('Helicopter', 'Transport.AirCraft.Helicopter'); insert into transport values ('Jet', 'Transport.AirCraft.Jet'); insert into transport values ('AirBus', 'Transport.AirCraft.AirBus');

3. Получаем необходимые данные:

   Получение дочерних элементов ‘Transport.Car’:

   select * from transport  where "path" <@ 'Transport.Car'

    Получение родительских элементов ‘Transport.AirCraft.AirBus’:

   select * from transport where "path" @> 'Transport.AirCraft.AirBus'

   Как видно из примера, получить все необходимые элементы достаточно просто, выполнив несложные запросы к базе данных.

   Об остальных возможностях Ltree Materialized Path можно прочитать в официальной документации.

Давайте теперь перейдем к созданию нашего веб-приложения, в котором мы будем работать с деревом посредством API и Entity Framework Core. 

Создаем проект ASP.NET Core Web API

Создаем проект с типом ASP.NET Core Web API и назовем наш проект MaterializedPathAPI.

Конфигурируем наш проект в соответствии со следующим изображением:

Устанавливаем nuget пакеты:

1. Npgsql.EntityFrameworkCore.PostgreSQL.

2. Microsoft.EntityFrameworkCore.Design.

3. Microsoft.EntityFrameworkCore.Tools.

Далее нам нужно создать определенную структуру проекта, основными элементами которой будут:

• TreeController – контроллер для взаимодействия извне с нашим API;

• TreeService – сервис с основной логикой;

• TreeContext – контекст базы данных, использующий EntityFrame Work Core;

• TreeRepository – репозиторий для работы с контекст базы данных. 

Заполняем проект нужными папками и файлами

Создаем папку DB и добавляем папку Models, а в нее основные сущности для дерева:

1. Tree.cs.

   public class Tree {     [Key]     [StringLength(50, MinimumLength = 3)]     public Guid Id { get; set; }      [Required]     [StringLength(50)]     public string Name { get; set; }      [Required]     [StringLength(5)]     public string Sorting { get; set; } }

2. TreeItem.cs. Класс для создания таблицы TreeItems для хранения элементов дерева.

   [Index(nameof(EntityId))] [Index(nameof(ParentEntityId))] [Index(nameof(TreeKey))] [Index(nameof(MaterializedPath))] public class TreeItem {     [Key]     [DatabaseGenerated(DatabaseGeneratedOption.Identity)]     public Guid Id { get; set; }      [Required]     public Guid EntityId { get; set; }       public Guid? ParentEntityId { get; set; }      [Required]     public string EntityValue { get; set; }      [Column(TypeName = "ltree")]     public LTree MaterializedPath { get; set; }      public Guid TreeKey { get; set; }      [NotMapped]     public int Level { get; set; } //для сохранение уровня из свойства MaterializedPath.Nlevel }

Создаем контекст базы данных TreeContext.cs в папке DB. В этом классе в методе OnModelCreating() добавляем индекс «gist» к таблице TreeItem для более удобной работы с LTree. Мы сможем пользоваться методами и свойствами LTree, аналогами которых на PostgreSQL являются ниже указанные операторы:

<, <=, =, >=, >, @>, <@, @, ~, ? (более подробно в оф. документации)

public class TreeContext : DbContext {     public TreeContext(DbContextOptions<TreeContext> options) : base(options) { }     public DbSet<Tree> Trees { get; set; }     public DbSet<TreeItem> TreeItems { get; set; }      protected override void OnModelCreating(ModelBuilder modelBuilder)     {         modelBuilder.HasPostgresExtension("ltree");         base.OnModelCreating(modelBuilder);         modelBuilder.Entity<TreeItem>()         .HasIndex(treeItem => treeItem.MaterializedPath)           .HasMethod("gist"); //тут указываем индекс gist для более удобной работы с Ltree     } }

Логика создания элементов дерева

При создании нового элемента, первым делом мы должны получить значение свойства MaterializedPath его родителя. Далее мы должны конкатенировать свойство MaterializedPath со значение нового элемента (EntityValue) через точку, чтобы получить полный путь от вышестоящих по иерархии родительских элементов.

В итоге если у родительского элемента значение равно “first” и значения нового дочернего элемента “second”, в итоге в свойстве MaterialledPath мы должны поместить значение “fist.second” 

//получаем родителя элемента для извлечения Materialized Path var parentTreeItem = await _context.TreeItems   .Where(x => x.EntityId == treeItem.ParentEntityId) .FirstOrDefaultAsync();  //Обновляем Materialized Path в соответствии наличия родителя элемента treeItem.MaterializedPath =    new LTree(parentTreeItem == null ?      GetPath(treeItem.EntityValue) :      ConcatPath(parentTreeItem.MaterializedPath, treeItem.EntityValue));

Для получения дочерних и родительских элементов мы можем воспользоваться методами класса Ltree:

1. Метод IsAncestorOf() соответствует в postgreSql оператору @> и возвращает все родительские элементы.

   var treeItem = await GetTreeItem(treeItemId);  return await _context.TreeItems   .Where(x => x.MaterializedPath.IsAncestorOf(treeItem.MaterializedPath));

2. Метод IsDescendantOf() соответствует в postgreSql оператору <@ и возвращает все дочерние элементы.

   var treeItem = await GetTreeItem(treeItemId);  return await _context.TreeItems   .Where(x => x.MaterializedPath.IsDescendantOf(treeItem.MaterializedPath));

Примечание: при работе со свойством класса TreeItem MaterializedPath (тип Ltree) необходимо учитывать, что его методы и свойства доступны до материализации запроса с базы данных.  

Итак, продолжим. Создаем TreeRepository.cs для работы с контекстом базы данных в папке DB. Для создания дерева нам потребуются:

• метод для создания корня дерева (стр. 16);

• метод для создания дочерних элементов в таблице TreeItem (стр. 32);

• метод для получения информации о дереве (стр. 59);

• методы для получения дочерних и родительских элементов определенного элемента (стр. 116 и стр.139).

Создаем TreeService.cs для работы с основной логикой приложения в корневой папке. Данный сервис будет для нас промежуточным звеном, с которым будет непосредственно работать контроллер.

Добавляем настройки строки подключения к нашей базе данных в appsettings.json:

"ConnectionStrings": {     "TreeConnection": "User ID=postgresUser;Password=postgresPW;Server=localhost;Port=5455;Database=postgres;Integrated Security=true;Pooling=true;" }

Конфигурируем класс Program.

Чтобы не заморачиваться с авторизацией и созданием дополнительных интерфейсов для  dependency injection, удалим app.UseAuthorization(), добавим конфигурацию для подключения к нашей базе данных из appsettings.json и добавим в сервисы TreeRepository и TreeService:

var builder = WebApplication.CreateBuilder(args); builder.Services.AddControllers(); builder.Services.AddEndpointsApiExplorer(); builder.Services.AddEntityFrameworkNpgsql()   .AddDbContext<TreeContext>(opt =>     opt.UseNpgsql(builder.Configuration.GetConnectionString("TreeConection"))); builder.Services.AddScoped<TreeRepository>(); builder.Services.AddScoped<TreeService>(); var app = builder.Build(); app.MapControllers(); app.Run();

Конфигурируем launchsettings.json:

{     "$schema":   "https://json.schemastore.org/launchsettings.json",     "profiles":   {         "MaterializedPathTreeAPI":   {             "commandName":   "Project",             "applicationUrl":   "http://localhost:5186",             "environmentVariables":   {                   "ASPNETCORE_ENVIRONMENT": "Development"             }         }     } }

Нам осталось только определить модели для работы с нашим приложением извне.

Создаем папку Models в корне проекта, создаем папку Info и заносим в нее сущности:

1.  CreateTreeInfo.cs – модель для создания нового дерева.

   public class CreateTreeInfo {     public Guid TreeKey { get; set; }     public string Name { get; set; } }

2. GetTreeItemsByTreeInfo.cs – модель для получения иерархии элементов.

   • FromIndex – индекс элемента, с которого мы получаем дерево.

   • ToIndex -максимальное количество элементов для получения.

   • ExpandedTreeItemIds – список id элементов, если мы хотим получить раскрытие элемента и получить его дочерние элементы на первом уровне.

   • TreeKey – id дерева из таблицы Trees.

     public class GetTreeItemsByTreeInfo {     public Guid TreeKey { get; set; }     public IReadOnlyCollection<Guid>? ExpandedTreeItemIds { get; set; }     public int FromIndex { get; set; }     public int ToIndex { get; set; } }

3. TreeItemInfo.cs – модель для создания нового элемента в таблице TreeItems. 

   public class TreeItemInfo {     [Required]     public Guid Id { get; set; }       public Guid? ParentId { get; set; }     [Required]     public string Value { get; set; } }

K папке Models также создаем папку View (это модели для ответа на запрос через контроллер) и создаем класс TreeItemView.

• EntityId — id элемента в дереве;

• ParentEntityId — id родительского элемента;

• EntityValue — значение элемента;

• Path — путь к элементу с начала иерархии. Как говорилось в примере выше, тут будет хранится значение “first.second”;

• Level — уровень, на котором находится элемент. 1 уровень — это корневой элемент. Чем больше значение уровня, тем выше уровень вложенности элемента в иерархии.

public class TreeItemView {     public Guid EntityId { get; set; }     public Guid? ParentEntityId { get; set; }     public string EntityValue { get; set; }     public string Path { get; set; }     public int Level { get; set; } }

И, наконец, создаем простой контроллер TreeController.cs для работы с нашим веб-приложением извне в папке Controllers в корне проекта.

Далее нам нужно создать наши таблицы в базе данных. Для этого открываем Package manager Console и создаем Code-First базу данных:

PM> enable-migrations

PM> add-migration initial

PM> update-database

Теперь у нас есть все необходимые сущности в нашей базе данных, а также готовое API. Осталось наполнить данными наши таблицы посредством API и получить корректные результаты. Обращение к нашему API я оставлю вам в виде готовых cUrl запросов на создание и поиск сущностей.  Можно воспользоваться инструкцией, как их импортировать в PostMan для более удобного взаимодействия с ними.

Создание дерева:

curl --location --request POST 'http://localhost:5186/tree/tree' \ --header 'Content-Type: application/json' \ --data-raw '{     "treekey": "6f806b0f-bdd9-461b-b109-dfa94871e55c",     "sorttype": "asc",     "name": "TransportTree" }'

Создание корневых элементов:

curl --location --request POST 'http://localhost:5186/tree/6f806b0f-bdd9-461b-b109-dfa94871e55c/treeitem' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",     "parentid": null,     "value": "Car" }'  curl --location --request POST 'http://localhost:5186/tree/6f806b0f-bdd9-461b-b109-dfa94871e55c/treeitem' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "3af8fc64-08c2-4e7d-a80a-5636f689dc15",     "parentid": null,     "value": "Boat" }'

Я не буду расписывать все запросы для создание разветвлённого дерева. Думаю, это будет отличной тренировкой для вас самих. Добавим побольше дочерних элементов для Car.

curl --location --request POST 'http://localhost:5186/tree/6f806b0f-bdd9-461b-b109-dfa94871e55c/treeitem' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "3b5e9928-85c6-4316-ba46-1b223d6c0222",     "parentid": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",     "value": "Van" }'  curl --location --request POST 'http://localhost:5186/tree/6f806b0f-bdd9-461b-b109-dfa94871e55c/treeitem' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "73e49e05-5ce2-4bca-aef4-d2f030848162",     "parentid": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",     "value": "Truck" }'

И теперь к Truck добавим дочерние элементы:

curl --location --request POST 'http://localhost:5186/tree/6f806b0f-bdd9-461b-b109-dfa94871e55c/treeitem' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "a037cef7-3f96-4637-b26c-1da56086b293",     "parentid": "73e49e05-5ce2-4bca-aef4-d2f030848162",     "value": "BigTruck" }'  curl --location --request POST 'http://localhost:5186/tree/6f806b0f-bdd9-461b-b109-dfa94871e55c/treeitem' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "c0a8b81c-fde9-4691-af8d-3afff13fb1b7",     "parentid": "73e49e05-5ce2-4bca-aef4-d2f030848162",     "value": "MiniTruck" }'

И еще для наглядности добавим элемент MicroTruck для MiniTruck:

curl --location --request POST 'http://localhost:5186/tree/6f806b0f-bdd9-461b-b109-dfa94871e55c/treeitem' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "7b091725-feb4-4acd-9077-bdfd4c08c31a",     "parentid": "c0a8b81c-fde9-4691-af8d-3afff13fb1b7",     "value": "MicroTruck" }'

Теперь у нас есть иерархия элементов по элементу Car. Давайте попробуем получить данные.

Получение родителей элемента MiniTruck:

curl --location --request GET 'http://localhost:5186/tree/treeitem/7b091725-feb4-4acd-9077-bdfd4c08c31a/parents' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "c0a8b81c-fde9-4691-af8d-3afff13fb1b7",     "parentid": "73e49e05-5ce2-4bca-aef4-d2f030848162",     "value": "MiniTruck" }'

Результат:

[     {         "entityId": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",         "parentEntityId": null,         "entityValue": "Car",         "path": "Car",         "level": 1     },     {         "entityId": "73e49e05-5ce2-4bca-aef4-d2f030848162",         "parentEntityId": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",         "entityValue": "Truck",         "path": "Car.Truck",         "level": 2     },     {         "entityId": "c0a8b81c-fde9-4691-af8d-3afff13fb1b7",         "parentEntityId": "73e49e05-5ce2-4bca-aef4-d2f030848162",         "entityValue": "MiniTruck",         "path": "Car.Truck.MiniTruck",         "level": 3     } ]

Как видно из ответа, у нас есть уровень вложенности элемента в поле level. 1 уровень — это уровень корневых элементов и, соответственно, чем больше уровень, тем ниже по дереву находится элемент.

Теперь получим дочерние элементы от Car:

curl --location --request GET 'http://localhost:5186/tree/treeitem/c02d283f-70e5-43a2-8f5b-69f4ee93492e/children' \ --header 'Content-Type: application/json' \ --data-raw '{     "id": "c0a8b81c-fde9-4691-af8d-3afff13fb1b7",     "parentid": "73e49e05-5ce2-4bca-aef4-d2f030848162",     "value": "MiniTruck" }'

Результат:

[     {         "entityId": "3b5e9928-85c6-4316-ba46-1b223d6c0222",         "parentEntityId": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",         "entityValue": "Van",         "path": "Car.Van",         "level": 2     },     {         "entityId": "73e49e05-5ce2-4bca-aef4-d2f030848162",         "parentEntityId": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",         "entityValue": "Truck",         "path": "Car.Truck",         "level": 2     },     {         "entityId": "a037cef7-3f96-4637-b26c-1da56086b293",         "parentEntityId": "73e49e05-5ce2-4bca-aef4-d2f030848162",         "entityValue": "BigTruck",         "path": "Car.Truck.BigTruck",         "level": 3     },     {         "entityId": "c0a8b81c-fde9-4691-af8d-3afff13fb1b7",         "parentEntityId": "73e49e05-5ce2-4bca-aef4-d2f030848162",         "entityValue": "MiniTruck",         "path": "Car.Truck.MiniTruck",         "level": 3     },     {         "entityId": "7b091725-feb4-4acd-9077-bdfd4c08c31a",         "parentEntityId": "c0a8b81c-fde9-4691-af8d-3afff13fb1b7",         "entityValue": "MicroTruck",         "path": "Car.Truck.MiniTruck.MicroTruck",         "level": 4     } ]

Также я дополнительно оставил метод в контроллере GetTreeItemsFlatTree, который возвращает корневые элементы дерева, и также вы можете получить элементы нижнего уровня этих элементов, если укажите в свойстве ExpandedTreeItemIds идентификатор раскрываемого объекта. Вот пример, где раскроем дополнительно элемент Car из списка:

curl --location --request POST 'http://localhost:5186/tree/flattree' \ --header 'Content-Type: application/json' \ --data-raw '{     "treekey": "6f806b0f-bdd9-461b-b109-dfa94871e55c",     "fromindex": 0,     "toindex": "10",     "ExpandedTreeItemIds": [        "c02d283f-70e5-43a2-8f5b-69f4ee93492e"      ] }'

Результат:

[     {         "entityId": "3af8fc64-08c2-4e7d-a80a-5636f689dc15",         "parentEntityId": null,         "entityValue": "Boat",         "path": "Boat",         "level": 1     },     {         "entityId": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",         "parentEntityId": null,         "entityValue": "Car",         "path": "Car",         "level": 1     },     {         "entityId": "73e49e05-5ce2-4bca-aef4-d2f030848162",         "parentEntityId": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",         "entityValue": "Truck",         "path": "Car.Truck",         "level": 2     },     {         "entityId": "3b5e9928-85c6-4316-ba46-1b223d6c0222",         "parentEntityId": "c02d283f-70e5-43a2-8f5b-69f4ee93492e",         "entityValue": "Van",         "path": "Car.Van",         "level": 2     } ]

Заключение

В этой статье мы коснулись темы работы с деревом, используя PostgreSQL Materialized Path, подготовили демонстрационный стенд с деревом и API для работы с ним, а также сделали несколько тестовых запросов. Прошу прощения, если в некоторых местах я слишком скрупулёзно описывал элементарные вещи. Однако, я уверен, на базе этого проекта, вы сможете исследовать глубже как текущий, так и другие способы работы с деревьями, и, возможно, улучшить представленное решение.

Мне не хотелось сильно уходить в теорию, главной моей задачей было показать рабочий пример и позволить разработчику прочувствовать механизмы работы Materialized Path, по шагам выполняя практические упражнения.

Данная статья в какой-то мере адресована мне самому из прошлого. Мне она позволила структурировать моё понимание этого механизма работы с деревьями. Надеюсь, она и вам была полезна или, как минимум, интересна!

P. S. Хочу отметить, что выбор способа работы с деревьями очень варьируется в зависимости от требований. Если тема вам интересна, очень рекомендую ознакомиться со следующими материалами:

• Обзор паттернов хранения деревьев в реляционных БД / Хабр (habr.com)

• PostgreSQL : Документация: 9.6: F.21. ltree : Компания Postgres Professional

• Struct LTree | Npgsql Documentation

• PostgreSQL : Документация: 9.6: F.21. ltree : Компания Postgres Professional

Репозиторий с кодом, который рассматривали выше: KhusravBim/MaterializedPathTreeApi (github.com).