LINUX.ORG.RU
Форум — Development  

with recursive в PostgreSQL

 ,


0

3

Есть банальная таблица для хранения древовидной структуры:

CREATE TABLE test (
   tid serial PRIMARY KEY,
   pid INTEGER,
   name VARCHAR NOT NULL
   -- на самом деле тип name это домен с проверкой, но в данном случае это не важно КМК
   -- да и constraint'ы опустим.
);

И есть две задачи:

  • Найти запись в соответствии с заданным путём n1.n2.n3.n4
  • Найти ближайший элемент к заданному пути. Т.е. например для n1.n2.n3.n4 вернуть запись с путём n1.n2 т.к. у n1.n2 нет потомков.

Покопавшись с WITH RECURSIVE для первой задачи получилось такое себе решение:

WITH RECURSIVE r1 as (
  SELECT t1.tid, t1.pid, t1.name, cast( t1.name as text ) as path
  FROM test t1 WHERE pid is null and t1.name = split_part('n1.n2.n3.n4', '.', 1)
    UNION
  SELECT t2.tid, t2.pid, t2.name, r1.path || '.'|| t2.name as path
  FROM test t2
  join r1 on t2.pid = r1.id
)
select * from r1 where path = 'n1.n2.n3.n4';

Хотя меня несколько напрягает сравнение строк, но я не уверен как сделать быстрее.

И по второму вопросу не могу докумекать, как всё это реализовать. Может кто-нибудь чего подскажет?

★★★★★
← Использование С-шных стуктур нефиксированной длинны в C++
Подарите старый NetBeans 8 с поддержкой C++ →
Ответ на: комментарий от anonymous

Может кто-нибудь чего подскажет?

Организуй действительно древовидное хранение доменов в отдельной таблице, чтобы не заниматься дрочевом со строками

anonymous
()
Ответ на: комментарий от anonymous

Анон как всегда, говорит ни о чём. Ты не вы…ясь можешь пример показать? Или как всегда - «анон хуже тридвараса»?

WatchCat ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Как ни анон, так последователь ЛГБТК+

WatchCat ★★★★★
() автор топика
Ответ на: комментарий от no-such-file

Это не очень удобный вариант. Гугли nested sets.

Насколько я гуглил, nested sets зависят от последовательности ключа.

WatchCat ★★★★★
() автор топика
Ответ на: комментарий от WatchCat

зависят от последовательности ключа

И как бы в чём проблема?

no-such-file ★★★★★
()

Я хз чего и как (пятница и я, как нормальный? пацан пьян), но пяток лет назад я деревья хранил в постгре через ltree. Там можно было делать поиск через * типа *.n2.*.n10 и т.п. погуглди может это то что тебе надо.

пс. https://habr.com/ru/post/130371/

vtVitus ★★★★★
()
Последнее исправление: vtVitus (всего исправлений: 2)

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

kmeaw=# create or replace function path(id integer) returns varchar language plpgsql as $$
declare
  _name varchar;
  _pid integer;
begin
  select into _name, _pid test.name, test.pid from test where test.tid = id;
  if _pid is null then return _name; else return path(_pid) || '.' || _name; end if;
end;
$$
;
CREATE FUNCTION
kmeaw=# select path(tid), * from test;
   path   | tid | pid | name 
----------+-----+-----+------
 n1       |   1 |     | n1
 n1.n2    |   2 |   1 | n2
 n1.n2.n3 |   3 |   2 | n3
(3 rows)

Вторую можно решить перебором, который благодаря индексу займёт мало времени:

kmeaw=# create or replace function rpath(path varchar) returns integer language plpgsql as $$
declare
  _path varchar;
  _cand integer; _best integer;
  _part varchar;
begin
  foreach _part in array string_to_array(path, '.')
  loop
    if _path is null
    then
      _path := _part;
    else
      _path := _path || '.' || _part;
    end if;
    select into _cand tid from test where path(tid) = _path;
    _best := coalesce(_cand, _best);
    if _cand is null then return _best; end if;
  end loop;
  return _best;
end;
$$
;

Если путь чаще присутствует, чем отсутствует, можно попробовать развернуть перебор в обратную сторону - от полного пути к первому компоненту.

kmeaw ★★★
()
Ответ на: комментарий от anonymous

Сделай вселенную чище - уйди из интернетов.

WatchCat ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Использование С-шных стуктур нефиксированной длинны в C++
Development
Подарите старый NetBeans 8 с поддержкой C++ →