Решение проблемы сортировки деревьев с помощью бинарного Materialized Path

[megahertz]

Интересное решение. Я при решении такой задачи использовал программную сортировку

[aparamonov]

Я не назову это решение ни красивым, ни интересным. Оно переусложненное в рамках поставленных целей.
Программная сортировка займет меньше кода и тупо проще.

[boolive]

Если с LIMIT выбирать, то не получите цельное дерево (ветку)

[aparamonov]

А тут пункт задачи

Выборка всего дерева одним запросом, с отсортированными в нужном порядке ветвями

:)

А если нужна пагинация, то данное решение не поможет его осуществить на первый взгляд.

[movsb]

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

000001
000001.000002
000001.000002.000003
000001.000002.000007
000001.000002.000010
000004
000004.000008
000004.000008.000009
000005
000005.000006

Если использовать под каждое значение 6 позиций, можно в каждой ветке хранить 1 млн комментариев, а максимальная вложенность будет 256 / 6 = 42 подуровня. При этом десятичная система нагляднее и не требует кодирования.

[devaka]

Если использовать под каждое значение 6 позиций, можно в каждой ветке хранить 1 млн комментариев

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

Поясню. Допустим, через год у вас появляется комментарий с ID = 1 000 000 к комментарию с ID = 1. Как в вашем случае будет выглядеть путь?

[devaka]

То есть, смотря что за числа у вас между точками — если это порядок комментария в ветке, то да, решение подходит (но как рассчитывать этот порядок?). Если это порядок комментария в системе в целом, то их может быть больше чем 1 млн. за несколько лет
(как например, на хабре ваш комментарий имеет ID = 7 697 455

[movsb]

Хорошо, пусть идет сквозная нумерация независимо от вложения. Если отвести под одно значение 10 цифр, получится 255 / 10 = 25 уровней вложения. Этого достаточно? Просто в описании задачи не сказано о требуемом максимальном количестве комментариев и уровней вложенности.

[devaka]

25 уровней для меня вполне достаточно ) спасибо, в рамках моей задачи идея годная.

[ptitca_zu]

Решал похожую задачу. Нужно было исполнять на БД скрипты из файлов, в названии которых содержалась версия в таком же формате. Соответственно выполнять их было нужно в порядке возрастания версий.

Сделал так:

1. Привел все версии к единому числовому формату — a*10**n + b*10**(n-1)… (кол-во разрядов в версии было фиксировано)
2. Отсортировал получившиеся числа

[Funcraft]

Для наглядности можно было бы привести пути, которые у вас получились в результате для рассматриваемого дерева. А то «проблема» есть, а «результата решения» — нет.

[devaka]

В моем случае получилось так (отсортировано по bpath):



Если сортировать по mpath, то 43,46 как строки будут меньше чем 9 в ветках /1/3/4/5/8/43 и рядом. Пример:

SELECT * 
FROM  `messages` 
WHERE mpath LIKE  '/1/3/4/5/8/%'
ORDER BY mpath ASC

Получается строка bpath выглядит не очень читаемо :) и нужна чисто для сотрировки.

[TIEugene]

> Если для каждого значения в пути мы будем использовать фиксированную длину

А теперь всё тоже самое — для _не_фиксированной длины (КЛАДР, ага).

[movsb]

В КЛАДР-е нет неограниченного уровня вложенности, так что там все просто.

[blackmaster]

К слову, в PostgreSQL есть расширение ltree, которое подходит для Вашей задачи. Можно посмотреть в его исходниках, как там реализовано.

[pro100tak]

Эммм. ORDER BY LENGTH(path), path…

INSERT INTO test (path) VALUES ('1'), ('2'), ('3'), ('1.1'), ('1.2'), ('1.10'), ('1.10.1'), ('1.10.2'), ('1.3'); 
SELECT * FROM test LIMIT 0, 1000; 
-- 1.3 внизу как и ожидалось
SELECT * FROM test ORDER BY path, LENGTH(path) LIMIT 0, 1000; 
-- Всё гут

Может будут тратится ресурсы на подсчёт длины строки, но не такие существенные, как коверкание пути. Он ведь служит для наглядности

[pro100tak]

Сорри, вначале неправильно (в коде — правильно).
ORDER BY path, LENGTH(path)

[devaka]

А как на счет такого варианта?

path    LENGTH(path)
5.6.40  6
43.45   5

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

[pro100tak]

И то правда… Ок, откидываем как нерабочее :)

[Benderlidze]

а как решить проблему: вывод комментариев по дате — новые сверху. если идет просто order by path ASC то выводит все ок но новые внизу, мне хотелось бы новы вверху страницы, но как не пробовал ордерами и прочим не получается вывести правильно. все вверх ногами выходит. есть идеи?