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

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

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

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

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

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/ ^[2]. Идея — использовать не десятичные 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 взята отсюда ^[3].

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

Автор: devaka

Источник ^[4]