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

    Столкнулся с проблемой реализации древовидных комментариев на одном проекте, в этой заметке выкладываю своё решение.

    Описание задачи


    • Хранение иерархических данных (древовидных комментариев) в реляционной БД MySQL
    • Простое добавление узлов/ветвей
    • Выборка всего дерева одним запросом, с отсортированными в нужном порядке ветвями

    В принципе, задача классическая, и сначала я её решил с помощью объединения Adjacency List и Materialized Path. Другими словами, в таблице добавлены колонки

    id INT(11)
    parentid INT(11)
    mpath VARCHAR(255)

    В mpath хранился полный путь ветки в дереве, например /1/3/4/5/8/9, где через знак "/" перечислялись ID комментария.

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

    SELECT *
    FROM messages
    WHERE postid=$postid
    ORDER BY mpath ASC

    Проблема возникла при росте числа комментариев. Например, имеется дерево со следующими путями:

    1
    1.2
    1.2.10
    1.2.3
    1.2.7
    4
    4.8
    4.8.9
    5
    5.6

    Здесь цифрами указаны ID, а порядок такой, какой бы он получился при использовании ORDER BY mpath ASC.
    Комментарий 1.2.10 идёт до 1.2.3 и др, хотя был добавлен позже (судя по ID).

    Решение задачи


    Решение проблемы частично было описано здесь: http://habrahabr.ru/post/125729/. Идея — использовать не десятичные ID в пути, а кодировать в другую систему счисления, чтобы иметь меньше ограничений в длине пути. При этом, разделители в виде точек или других символов не нужны, так как поле будет использоваться только для сортировки.

    Я использовал основание 95, это как раз число печатаемых символов в ASCII.

     !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
    


    Если для каждого значения в пути мы будем использовать фиксированную длину, получим следующий верхний порог ID:
    1 — 95^1 — 1 = 94
    2 — 95^2 — 1 = 9 024
    3 — 95^3 — 1 = 857 374
    4 — 95^4 — 1 = 81 450 624
    5 — 95^5 — 1 = 7 737 809 374

    5-ти символов вполне достаточно, чтобы не волноваться о максимальном количестве комментариев.
    Максимальный уровень вложенности, при этом, для VARCHAR 255/5 = 51

    Теоретически, можно брать не BASE95, а BASE256 (вместе с непечатаемыми символами), но хранить это всё бинарно в BLOB, правда тут я не уверен с производительностью при сортировке (надо проверить). Тогда уже 3 символами мы могли бы кодировать 16 777 215 вариантов, а 4 — 4 294 967 295.

    Как это выглядит в коде


    Приведу свой пример реализации всей этой теории.

    // $mpath - хранит стандартный materialized path с разделителем "/"
    
    // При добавлении нового комментария:
    $db->Execute("
    	UPDATE messages SET 
    	mpath=?, 
    	bpath=?,
    	depth=? 
    	WHERE id=?
    ", array(
    	$mpath, 
    	bpath($mpath),
    	$depth, 
    	$messid
    ));
    
    // . . . 
    
    // константа с символами для кодирования
    define('BASE95', ' !"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~');
    
    // . . . 
    
    // функция bpath
    function bpath($mpath, $sep = '/', $max_len = 5) {
    	$bpath = '';
    	$chunks = explode($sep, trim($mpath, $sep));
    	$zero = substr(BASE95, 0, 1);
        
    	foreach($chunks as $chunk) 
    		$bpath .= str_pad(dec2base($chunk, 95, BASE95), $max_len, $zero, STR_PAD_LEFT);
        
    	return $bpath;
    }
    

    И далее выборка:

    SELECT *
    FROM messages
    WHERE postid=$postid
    ORDER BY bpath ASC

    Функция dec2base взята отсюда.

    Такое вот решение, на мой взгляд очень простое. Если у вас также имеется в арсенале красивые решения, делитесь ими в комментариях.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 20

      0
      Интересное решение. Я при решении такой задачи использовал программную сортировку
        +4
        Я не назову это решение ни красивым, ни интересным. Оно переусложненное в рамках поставленных целей.
        Программная сортировка займет меньше кода и тупо проще.
          +2
          Если с LIMIT выбирать, то не получите цельное дерево (ветку)
            +1
            А тут пункт задачи
            Выборка всего дерева одним запросом, с отсортированными в нужном порядке ветвями
            :)

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

          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 подуровня. При этом десятичная система нагляднее и не требует кодирования.
            +2
            Если использовать под каждое значение 6 позиций, можно в каждой ветке хранить 1 млн комментариев

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

            Поясню. Допустим, через год у вас появляется комментарий с ID = 1 000 000 к комментарию с ID = 1. Как в вашем случае будет выглядеть путь?
              +1
              То есть, смотря что за числа у вас между точками — если это порядок комментария в ветке, то да, решение подходит (но как рассчитывать этот порядок?). Если это порядок комментария в системе в целом, то их может быть больше чем 1 млн. за несколько лет
              (как например, на хабре ваш комментарий имеет ID = 7 697 455
                +1
                Хорошо, пусть идет сквозная нумерация независимо от вложения. Если отвести под одно значение 10 цифр, получится 255 / 10 = 25 уровней вложения. Этого достаточно? Просто в описании задачи не сказано о требуемом максимальном количестве комментариев и уровней вложенности.
                  0
                  25 уровней для меня вполне достаточно ) спасибо, в рамках моей задачи идея годная.
              +1
              Решал похожую задачу. Нужно было исполнять на БД скрипты из файлов, в названии которых содержалась версия в таком же формате. Соответственно выполнять их было нужно в порядке возрастания версий.

              Сделал так:

              1. Привел все версии к единому числовому формату — a*10**n + b*10**(n-1)… (кол-во разрядов в версии было фиксировано)
              2. Отсортировал получившиеся числа
                0
                Для наглядности можно было бы привести пути, которые у вас получились в результате для рассматриваемого дерева. А то «проблема» есть, а «результата решения» — нет.
                  0
                  В моем случае получилось так (отсортировано по 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 выглядит не очень читаемо :) и нужна чисто для сотрировки.
                  0
                  > Если для каждого значения в пути мы будем использовать фиксированную длину

                  А теперь всё тоже самое — для _не_фиксированной длины (КЛАДР, ага).
                    0
                    В КЛАДР-е нет неограниченного уровня вложенности, так что там все просто.
                    0
                    К слову, в PostgreSQL есть расширение ltree, которое подходит для Вашей задачи. Можно посмотреть в его исходниках, как там реализовано.
                      0
                      Эммм. 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; 
                      -- Всё гут
                      


                      Может будут тратится ресурсы на подсчёт длины строки, но не такие существенные, как коверкание пути. Он ведь служит для наглядности
                        0
                        Сорри, вначале неправильно (в коде — правильно).
                        ORDER BY path, LENGTH(path)
                          +2
                          А как на счет такого варианта?

                          path    LENGTH(path)
                          5.6.40  6
                          43.45   5
                          

                          Вторая ветка добавлена позже, судя по ID, и порядок должен быть такой, как представлен выше. Ваше решение отсортирует результат не в том порядке.
                            0
                            И то правда… Ок, откидываем как нерабочее :)
                          0
                          а как решить проблему: вывод комментариев по дате — новые сверху. если идет просто order by path ASC то выводит все ок но новые внизу, мне хотелось бы новы вверху страницы, но как не пробовал ордерами и прочим не получается вывести правильно. все вверх ногами выходит. есть идеи?

                          Only users with full accounts can post comments. Log in, please.