Как сформировать деревья в json используя golang?

Question

[Станислав]

Добрый день! Для хранения деревьев использую ltree в postgres 14.
В результате sql запроса получаю данные

path это по сути хлебные крошки (ветвь дерева) состящая из id

Нужно отдать их в виде дерева в формате json

[
    {
        "id": 1,
        "name": "Беларусь",
        "childrens": [
            {
                "id": 3,
                "name": "Минск",
                "childrens": []
            }
        ]
    },
    {
        "id": 2,
        "name": "Россия",
        "childrens": [
            {
                "id": 4,
                "name": "Москва",
                "childrens": []
            }, 
            {
                "id": 5,
                "name": "Санкт-Петербург",
                "childrens": [
                    {
                        "id": 6,
                        "name": "Невский р-н",
                        "childrens": []
                    }
                ]
            }
        ]
    }
]

Вытащить данные бд в слайс структур не проблема, а вот как сформировать деревья?

Шаблон по запросу из комментариев

spoiler

package main

import (
	"context"
	"fmt"
	"os"

	"github.com/jackc/pgx/v4"
)

// Структура бд
//CREATE EXTENSION ltree;
//CREATE TABLE IF NOT EXISTS "objects" (
//   id SERIAL PRIMARY KEY,
//   name TEXT NOT NULL,
//   path ltree
//);

type DBData struct {
	ID        int64    `json:"id"`
	Name      string   `json:"name" validate:"required,max=50"`
	Path      string   `json:"path"`
}

type Tree struct {
	ID        int64    `json:"id"`
	Name      string   `json:"name" validate:"required,max=50"`
	Path      string   `json:"path"`
	Childrens []Folder `json:"childrens"`
}

func GetDBData() []DBData {
	conn, _ := pgx.Connect(context.Background(), os.Getenv("DATABASE_URL"))
	defer conn.Close(context.Background())

	// например получаю деревья с 3 уровнями вложенности, но может быть больше
	query := `select * from objects where path ~ '*{1,3}'`  

	rows, _ := conn.Query(ctx, query, userID)
	defer rows.Close()

	var data []DBData 
	for rows.Next() {
		var d DBData

		_ = rows.Scan(&d.ID, &d.Name, &d.Path);

		data = append(data, d)
	}

	return data
}

func main() {
	// data := GetDBData() 
	// В результате этого запроса получаю
	data := []DBData{
		{ID: 1, Name: "Беларусь", Path: "1"},
		{ID: 2, Name: "Россия", Path: "2"},
		{ID: 3, Name: "Минск", Path: "1.3"},
		{ID: 4, Name: "Москва", Path: "2.4"},
		{ID: 5, Name: "Санкт-Петербург", Path: "2.5"},
		{ID: 6, Name: "Приморский р-н", Path: "2.5.6"},
	}

}

Comments

[12rbah]

Есть ограничение на вложенность списка? Например, что вложенность будет не больше 7.

[Станислав]

12rbah, нет

[12rbah]

Станислав, а json всегда имеет структуру {id,name, childrens} ?

[12rbah]

Станислав, в общем если структура не меняется, то в целом можно делать так.

package main

import (
	"encoding/json"
	"fmt"
	"log"
)

type Entry struct {
	ID        string    `json:"id"`
	Name      string `json:"name"`
}

type City struct {
	ID        string    `json:"id"`
	Name      string `json:"name"`
	Childrens []City `json:"childrens"`
}

func main(){
	var parent = Entry{ID:"1",Name:"test"}
	var child1 = Entry{ID:"1.1",Name:"test1"}
	var child2 = Entry{ID:"1.2",Name:"test2"}


	var AllCity []City

	var NewCity City

	NewCity.ID = parent.ID
	NewCity.Name = parent.Name

	var NewCityChild1 City
	NewCityChild1.ID = child1.ID
	NewCityChild1.Name = child1.Name
	var NewCityChild2 City
	NewCityChild2.ID = child2.ID
	NewCityChild2.Name = child2.Name

	NewCity.Childrens = append(NewCity.Childrens,NewCityChild1)
	NewCity.Childrens = append(NewCity.Childrens,NewCityChild2)

	AllCity = append(AllCity,NewCity)
	AllCity = append(AllCity,NewCity)


	b,err := json.MarshalIndent(AllCity,"","  ")
	if err != nil {
		log.Fatal(err)
	}

	fmt.Println(string(b))



}

[Станислав]

12rbah, спасибо, но в вашем варианте получается ограничение 3 урвонями. А мне необходимо без ограничений (произвольный уровень вложенности).

[12rbah]

Станислав, если в таком виде использовать, то конечно, нужно ;t дописать цикл или рекурсию и там уже добавлять. Вот ниже пример, хоть 50 уровней вложенности сделайте

package main

import (
	"encoding/json"
	"fmt"
	"log"
)

type Entry struct {
	ID        string    `json:"id"`
	Name      string `json:"name"`
}

type City struct {
	ID        string    `json:"id"`
	Name      string `json:"name"`
	Childrens []City `json:"childrens"`
}


func main(){
	var parent = Entry{ID:"1",Name:"test"}
	var child1 = Entry{ID:"1.1",Name:"test1"}
	var child2 = Entry{ID:"1.2",Name:"test2"}


	var AllCity []City

	var NewCity City

	NewCity.ID = parent.ID
	NewCity.Name = parent.Name

	var NewCityChild1 City
	NewCityChild1.ID = child1.ID
	NewCityChild1.Name = child1.Name
	var NewCityChild2 City
	NewCityChild2.ID = child2.ID
	NewCityChild2.Name = child2.Name
	NewCityChild2.Childrens = []City{{ID: "t", Name: "r", Childrens: []City{{ID: "1", Name: "1", Childrens: nil}}}}

	NewCity.Childrens = append(NewCity.Childrens,NewCityChild1)
	NewCity.Childrens = append(NewCity.Childrens,NewCityChild2)

	AllCity = append(AllCity,NewCity)
	AllCity = append(AllCity,NewCity)


	b,err := json.MarshalIndent(AllCity,"","  ")
	if err != nil {
		log.Fatal(err)
	}

	fmt.Println(string(b))

}

Answer 1

[mayton2019]

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

id name     path  parent
-----------------------
1  Беларусь 1     null
2  Россия   2     null
3  Минск    1.3   1
4  Москва   2.4   2
5  СПБ      2.5   2
6  Невский  2.5.6 5

Ну а дальше - select... connect prior и получим ранжированый курсор по дереву. Там-же будет
доступно виртуальное поле level. И обходом этого курсора можно сделать JSON документ.
Если level растет - то увеличиваем indentation и открываем вложенный элемент соотв.

Если go-lang поддерживает stremable json writers то даже лучше.

Comments

[Станислав]

Спасибо, я думал об этом варианте. Но он не очень хороший, т.к. придется доставать дерево через рекурсию, а каждый дополнительный уровень вложенности это +1 select. К тому же в ltree варианте гораздо дешевле и проще делать различные выборки.
И у меня проблема не вытащить эти данные из бд, а сформировать дерево на go (т.к. будет еще доп. обработка данных) и отдать это все как json.

[Voland69]

Станислав, а почему бы не достать плоскую таблицу за один селект а потом на go рекурсивно обойти и сложить ноды в дерево на основании id/parent id?
С древовидными структурами и сериализацией их насколько я помню в go проблем нет.

[mayton2019]

Станислав, накидай шаблон твоего приложения. Чтоб был коннект к БД и Select.
Остальное - не большая проблема.

[Станислав]

mayton2019, добавил под спойлер. Но по сути, от запроса к бд получаю этот слайс структур
https://go.dev/play/p/FdQGJasuM4P

[12rbah]

Станислав,

К тому же в ltree варианте гораздо дешевле и проще делать различные выборки.

Если такое нужно то можно вполне сделать что-то на таком дереве https://gist.github.com/mchirico/5941451, в целом поиск можно по префиксу сделать, но сильно зависит от того какие выбрки нужно делать, если небольшие до 1к объектов, то скорее всего будет достаточно быстро работать, если больше то нужно тестить и скорее всего использовать более специализорованный алгоритм.

[Станислав]

12rbah, спасибо, видел этот вариант, но если я правильно понял, это для бинарного дерева и для данного примера не подходит.

[mayton2019]

Станислав, это не то что я хотел. Я хотел взять курсор из БД и на уровне SQL решить 50% проблемы. И потом на уровне GoLang + JSON/Serializer/Marshaller решить вторые 50%.

Ты опубликовал то что мне никак не помогает. Я - не специалист в Go. Прошу извинить. Но я собаку съел на базах данных и на экспорте в бигдату и JSON-конверсиях.

[Станислав]

mayton2019, спасибо за помощь, но нужно решение на го.

[mayton2019]

Станислав, ну давай. Но до того как ты найдешь решение на Go, надо найти принцип.
Будешь ли ты строить дерево на ходу. Или отсортировав как я предложил просто
стримить в json поток.

Answer 2

[falconandy]

1. Достаете из БД все записи.
2. Для каждой записи строковый path конвертируете в массив (слайс) числовых индексов (1.2.3 -> [1, 2, 3])
3. Сортируете записи по этому массиву в лексикографическом порядке: [1], [1,3], [2], [2,4], [2,5], [2,5,6]
4. За один проход по отсортированному списку записей вручную формируете итоговый json. Можно реализовать рекурсивно или итеративно.

Comments

[Станислав]

Спасибо, надо подумать. Но на первый взгляд звучит как мем нарисуйте сову. Вроде бы и просто, а вот как нарисовать)

[falconandy]

Что можно использовать:
2. функции strings.Split, strconv.Atoi
3. функцию sort.Slice
4. тип strings.Builder

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

[Станислав]

falconandy, с первыми 3 пунктами разобраться не сложно, немного смутил четвертый. На выходных попробую разобраться. Спасибо, за наводку!