Сортировка дерева с материализованным путем?

Ответ 1

Обычно я создаю для этого дополнительный столбец, называемый как SortPath. Он будет содержать данные, которые необходимо сортировать, объединять вместе. Этот столбец будет иметь тип varchar и сортироваться как строка. Что-то вроде этого:

id | parent_id | matpath |          created            |                   sortpath
---+-----------+---------+-----------------------------+--------------------------------------------------------------------------------------
 2 |         1 | 1       | 2010-05-08 15:18:37.987544  | 2010-05-08 15:18:37.987544-2
 6 |         2 | 1.2     | 2010-05-08 17:50:43.288759  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6
 8 |         6 | 1.2.6   | 2010-05-09 14:01:17.632695  | 2010-05-08 15:18:37.987544-2.2010-05-08 17:50:43.288759-6.2010-05-09 14:01:17.632695-8
 3 |         1 | 1       | 2010-05-08 17:38:14.125377  | 2010-05-08 17:38:14.125377-3
 4 |         1 | 1       | 2010-05-08 17:38:57.26743   | 2010-05-08 17:38:57.267430-4 
 5 |         1 | 1       | 2010-05-08 17:43:28.211708  | 2010-05-08 17:43:28.211708-5
 9 |         5 | 1.5     | 2010-05-09 14:02:43.818646  | 2010-05-08 17:43:28.211708-5.2010-05-09 14:02:43.818646-9
 7 |         1 | 1       | 2010-05-08 18:18:11.849735  | 2010-05-08 18:18:11.849735-7

Несколько вещей, чтобы отметить здесь:

• SortPath будет сортироваться как строка, поэтому важно, чтобы все даты имели одинаковую длину для правильной сортировки. Например, наблюдайте, как 2010-05-08 17:38:57.26743 имеет дополнительный ноль, добавленный в столбце SortPath.
• Я добавил PK каждого node к концу его даты. Это так, что если у вас будет две строки с одинаковой датой, они будут всегда возвращаться в том же порядке из-за дополнительных данных, которые мы добавляем.
• Для меня данные выглядят асимметрично, как я его написал, потому что мы показываем текущую дату node в SortPath, но она не находится в matpath. Я бы предпочел увидеть его в обоих.
• Вы можете поместить дату node ID 1 в начале каждого sortcolumn. Это так, что если вы когда-нибудь захотите запросить более одного форума за один раз (вы, вероятно, этого не сделаете), то он все равно будет правильно сортироваться.

Ответ 2

Я считаю, что ваш материализованный путь не прав.

Какую логику вы можете сортировать, например,

1
1.2
1
1.5

Почему второй 1 не вместе с первым?

Если у вас

1
1.2
2
2.5

Это было бы тривиально.

EDIT: Я посмотрел на ваш пример, и вы не сохраняете материализованный путь строки, но вы сохраняете материализованный путь родительской строки. Вот как должен выглядеть материализованный путь строки. Сортировка непосредственно на matpath будет работать, если у вас не будет более 9 ветвей, если вы сохранили ее как:

 id | parent_id | matpath   |          created
----+-----------+-----------+----------------------------
  2 |         1 | 1.2       | 2010-05-08 15:18:37.987544
  6 |         2 | 1.2.6     | 2010-05-08 17:50:43.288759
  8 |         6 | 1.2.6.8   | 2010-05-09 14:01:17.632695
  3 |         1 | 1.3       | 2010-05-08 17:38:14.125377
  4 |         1 | 1.4       | 2010-05-08 17:38:57.26743
  5 |         1 | 1.5       | 2010-05-08 17:43:28.211708
  9 |         5 | 1.5.9     | 2010-05-09 14:02:43.818646
  7 |         1 | 1.7       | 2010-05-08 18:18:11.849735

в противном случае ( > 9) вам нужно было бы превратить matpath в нечто вроде

001.002.006
001.002.006.008

который поддерживает до 999 ветвей.

Обратите внимание:

• даже подход с 4 фиксированными цифрами, например 0001.0002.0006, даст вам поле, которое короче, чем в принятом ответе
• вы можете анализировать значение matpath для сортировки продукта на лету с помощью функции пользователя
• вы можете напрямую сохранить matpath в этом формате (у него есть и другие приятные свойства)

Ответ 3

Я не уверен, что понимаю, почему принятое решение имеет какой-то смысл. Он работает, но он еще менее нормализован и менее эффективен (больше дискового пространства, больше индексов и т.д.), Чем решение @Unreason (просто вставить идентификатор в материализованном пути).

Весь сценарий, с которым сталкиваются лица OP, связан с тем, что, как правильно указывает @Unreason, реализация материализованного пути (MP) неверна. OP предоставил MP родительскому, а не текущему node. В принятом решении столбец SortPath исправляет это, предоставляя материализованный путь к текущему node (на этот раз используя даты - почему? - вместо первичного ключа).

Для справки рассмотрим следующий отрывок:

Материализованный путь

В этом подходе каждая запись хранит весь путь к корню. В нашем в предыдущем примере допустим, что KING является корнем node. Затем запись с ename = 'SCOTT' подключается к корню через путь SCOTT- > JONES- > KING. Современные базы данных позволяют представлять список узлов как одно значение, но поскольку материализованный путь был изобретенный задолго до этого, конвенция придерживалась простого характера строка узлов, объединенная с некоторым разделителем; чаще всего '.' или "/'.

Ответ 4

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

Вы ищете функцию, создающую байтовый поток, f(x)=b_1b_2..b_i (извините MatJax на SO), где b_i является байтом. Мы знаем, что два байта потока сравниваются с первым байтом. Нам нужна такая функция, что f(x)<f(y) iff x<y.

Задание на ту же длину с 0 определенно получает эту цель, легко. Вы берете два номера, смотрите на первый ненулевой байт и там вы.

Стивен Виттенс (acko.net) представил другой трюк для ядра Drupal около восьми лет назад: поместите количество цифр перед строкой в ​​качестве другой цифры. Таким образом, число 97685 становится символом 5 9 7 6 8 5. Это также работает: сначала посмотрите на байт длины, если они не совпадают, то чем больше, тем больше будет. Кроме того, вы знаете, что два числа равны по длине. Он также использовал базовые номера 36 с 0-9a-z, являющимися цифрами, так же как и шестнадцатеричные только для каждой буквы. Эта кодировка требует двух байтов для первых 36 узлов, три для следующих 1260...

Обратите внимание, что ни для заполнения, ни для этой коварной кодировки переменной длины не нужны разделители для материализованного пути, хотя для удобства чтения они часто включаются.

numconv поддерживает кодировку base85, но для этого требуется сортировка с учетом регистра. Есть 94 символа ASCII, если вы удаляете строчные буквы, которые у вас все еще есть base68.

Но если вы используете "двоичное" поле, вы можете сделать base256: вместо коварной кодировки просто напишите номер как ряд байтов, а затем префикс всей вещи с длиной байта в виде одного байта. Это позволит вам кодировать любое дерево размером менее 2 ^ 2048 или около того. Для первых 256 узлов вы используете два байта, для следующих 65280 вы смотрите три байта. Это уже довольно эффективно.

Я назначаю функцию utf8encode(x). Считают, что! Вам нужно спуститься в bitorting вместо bytesorting, но это не изменит результат: найдите самый левый нулевой бит. Если в другой строке есть 1, это будет более длинная кодировка UTF-8, поэтому определенно больше. Если они имеют первый нуль в одном и том же месте, мы имеем битовые строки той же длины, которые хорошо сравнимы для нас.

Это приятно, но как насчет разделителей. Алгоритм UTF-8, рассматривая его как чисто алгоритм, создающий бит-потоки, может обрабатывать 31-битные числа, поэтому он будет работать для деревьев, содержащих менее двух миллиардов узлов. Ваш материализованный путь будет битовым потоком кодированных номеров UTF-8, которые хорошо сравниваются: Отбросьте самые левые идентичные кодированные номера UTF-8, и мы вернемся к предыдущему абзацу. Q.E.D.

Поскольку нам не нужны разделители или префиксные байты, мы можем кодировать первые 128 узлов в один байт, затем следующий 1920 на два байта и до 65535, три байта. За четыре байта base256 победит. Для действительно больших деревьев вы можете рассматривать UTF-8 как кодировщик 0-2147483647 в поток байтов. Таким образом, вы можете использовать его в качестве base2147483647: D

Подводя итог: UTF-8 лучше всего подходит для небольших деревьев и не намного хуже, чем base256 ниже двух миллиардов узлов. Помимо этого, выигрывает до 2 ^ 2048 или около того префикса-с-base-base256. Помимо того, что префикс-длина-base2147483647 побеждает, и там ничего кроме этого.

Ответ 5

Я не могу придумать простой способ сделать это в прямом SQL. Вместо matpath, я буду использовать node_path здесь. node_path - это matpath || '.' || id

 id | parent_id | node_path |          created           
----+-----------+---------+----------------------------
  2 |         1 | 1.2       | 2010-05-08 15:18:37.987544
  3 |         1 | 1.3       | 2010-05-08 17:38:14.125377
  4 |         1 | 1.4       | 2010-05-08 17:38:57.26743
  5 |         1 | 1.5       | 2010-05-08 17:43:28.211708
  7 |         1 | 1.7       | 2010-05-08 18:18:11.849735
  6 |         2 | 1.2.6     | 2010-05-08 17:50:43.288759
  9 |         5 | 1.5.9     | 2010-05-09 14:02:43.818646
  8 |         6 | 1.2.6.8   | 2010-05-09 14:01:17.632695

Теперь вы хотите заказать дерево на основе node_path с полем сортировки, определяемым количеством раз, когда вы запустили сортировку.

Пользовательская рекурсивная функция в сортировке plpgsql на split_part (node_path, '.', recursion_depth) будет работать. Вам нужно будет проверить значения NULL из split_part (и игнорировать их).