Решение проблемы сортировки деревьев с помощью бинарного 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 взята отсюда.

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