Решение проблемы сортировки деревьев с помощью бинарного 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://ift.tt/1lFo3LK. Идея — использовать не десятичные 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 взята отсюда.

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

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.