Статья: "SQLite. Деревья. Добавление материализованного пути к паре id—parent

Статья

SQLite. Деревья. Добавление материализованного пути к паре id—parent_id.

Для представления деревьев (направленных графов) в реляционных база данных обычно используют одну их трех структур, имеющих свои плюсы и минусы:

список смежности (adjacency list) — классическая пара id и parent_id;
вложенные множества (nested sets);
материализованный путь (materialized path — в различных вариантах).

Иногда применяют сразу две структуры. Это позволяет воспользоваться плюсами обеих структур, правда, заплатив и за минусы обеих, и за необходимость синхронно поддерживать целостность обеих структур. Я расскажу, как в SQLite дополнить список смежности материализованным путем, автоматизировать поддержание целостности обеих структур и организовать автоматическую генерацию материализованного пути.

Идея

Таблица предполагается такая:

Код: (SQL)

CREATE TABLE tree
(
id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT,
parent_id INTEGER REFERENCES tree (id),
path TEXT NOT NULL UNIQUE DEFAULT '',
content TEXT NOT NULL DEFAULT ''
);

Внешний ключ поможет поддерживать целостность связки parent_id — id. В принципе, его наличие не принципиально, но в триггерах проверку наличия предка я не делал и внешний ключ здесь будет не лишним. Узел с parent_id равным NULL является корнем дерева. Причем, значений NULL может быть несколько, а значит в одной таблице можно хранить несколько деревьев. Материализованный путь в данной таблице нужен только для выборки поддерева по заданному узлу. Поддержанием целостности материализованного пути будут заниматься триггеры.

Вычислять материализованный путь будет следующее выражение:

Код: (SQL)

CASE
WHEN parent_id IS NULL THEN '/' || NEW.id || '/'
ELSE (
SELECT path || NEW.id || '/'
FROM tree
WHERE id = NEW.parent_id
)
END

Логика простая: если parent_id равен NULL, то узел является корневым; в противном случае достаточно найти предка, взять его путь и дополнить нужной информацией. Данная реализация выдает материализованный путь следующего формата:

/id1/id2/id3/id4/

Здесь: id1 — корень, id2 и id3 — предки, id4 — сам узел.

Особенность данной реализации материализованного пути — не предусмотрена возможность хранить сортировку смежных узлов одного уровня. Зато есть возможности хранения нескольких деревьев и перемещения узлов между ними.

Для добавления и перемещения узлов используется пара полей — id и parent_id. Для удаления узлов, изменения их полезной нагрузки и выборки (одиночного узла или по списку) используется поле id. Для выборки поддерева используется поле path в выражении LIKE. Для перемещения узла и всех его потомков в другую ветку достаточно изменить только parent_id этого узла, все остальные необходимые изменения сделают триггеры.

Реализация.

Для тестов я сделал несколько файлов.

Скрипт создания базы, таблиц, триггеров и загрузки части тестовых данных.

Код: (Bash) create_db.sh

#!/bin/sh

DBNAME=test.sqlite

rm -f $DBNAME

echo '
.read init.sql
.read ddl.sql
.read test_data.sql
.quit
' | sqlite3 $DBNAME

Общие для всех тестов настройки. Поддержка внешних ключей по умолчанию отключена и ее необходимо активировать после подключения к базе.

Код: (MySQL) init.sql

PRAGMA cache_size = 8192;
PRAGMA foreign_keys = 1;

Определение базы, журнала, таблицы и триггеров. Оптимальнее всего использовать страницы базы в SQLite размером 4 или 8 кБ. Также рекомендую использовать журнал транзакций (WAL) — с ним возможно существование конкурентных транзакций и даже в однопользовательском режиме он работает быстрее традиционного журнала отката.

Триггер вставки «tree__ai_path_set» обеспечит генерацию материализованного пути.

Возможности каскадного удаления и обновления через внешний ключ я не использовал. В SQLite используемой мной версии (3.7.0.1) внешний ключ как-то неадекватно работает с триггерами. Проще было, запретить изменение идентификаторов и сделать триггер «tree__bd_tree_remove» для удаления поддерева.

Также потребовались два триггера обновления:

В триггере BEFORE UPDATE («tree__bu_integrity_check») я использовал для основной проверки целостности системы: неизменности идентификатора, запрещенных значений parent_id, отсутствие циклов в графе и корректность материализованного пути.
В триггере AFTER UPDATE («tree__au_path_update») выполняется проверка только на запрещенные значения parent_id и производится изменение материализованного пути для всего поддерева.

Код: (MySQL) ddl.sql

PRAGMA page_size = 8192;
PRAGMA journal_mode = WAL;

CREATE TABLE tree
(
id INTEGER NOT NULL PRIMARY KEY AUTOINCREMENT,
parent_id INTEGER REFERENCES tree (id),
path TEXT NOT NULL UNIQUE DEFAULT '',
content TEXT NOT NULL DEFAULT ''
);

CREATE TRIGGER tree__ai_path_set AFTER INSERT ON tree
BEGIN
-- Вычисление материализованного пути.
UPDATE tree
SET path =
CASE
WHEN parent_id IS NULL THEN '/' || NEW.id || '/'
ELSE (
SELECT path || NEW.id || '/'
FROM tree
WHERE id = NEW.parent_id
)
END
WHERE id = NEW.id;
END;

CREATE TRIGGER tree__bd_tree_remove BEFORE DELETE ON tree
BEGIN
-- Удалить всех потомков.
DELETE FROM tree
WHERE path LIKE OLD.path || '_%';
END;

CREATE TRIGGER tree__bu_integrity_check BEFORE UPDATE OF id, path ON tree
BEGIN
SELECT
CASE
WHEN OLD.id != NEW.id -- Смена id?
OR NEW.parent_id IS OLD.id -- Сссылка на самого себя как на предка?
OR NEW.path !=
CASE
WHEN NEW.parent_id IS NULL THEN '/' || OLD.id || '/'
ELSE (
SELECT path || OLD.id || '/'
FROM tree
WHERE id = NEW.parent_id
)
END -- Материализованный путь не соответствует рассчетному?
OR NEW.path LIKE '%/' || OLD.id || '/_%' -- Закольцовка пути?
THEN RAISE(ABORT, 'An attempt to damage the integrity of the tree.')
END;
END;

CREATE TRIGGER tree__au_path_update AFTER UPDATE OF parent_id ON tree
BEGIN
SELECT
CASE
WHEN NEW.parent_id IS OLD.id -- Ссылка на самого себя?
THEN RAISE(ABORT, 'An attempt to damage the integrity of the tree.')
END;
-- Массовое обновление материализованного пути у текущей строки и у всех потомков.
UPDATE tree
SET path = REPLACE(
path,
OLD.path,
CASE
WHEN NEW.parent_id IS NULL THEN '/' || OLD.id || '/'
ELSE (
SELECT path || OLD.id || '/'
FROM tree
WHERE id = NEW.parent_id
)
END
)
WHERE path LIKE OLD.path || '%';
END;

Минимальные тестовые данные: корни двух деревьев.

Код: (MySQL) test_data.sql

INSERT INTO tree (id) VALUES (1);
INSERT INTO tree (id) VALUES (2);

Скрипт создания взвешенного дерева от корня с id равным 1. Принимает два параметра: уровень ветвления и сколько веток имеет каждый ветвящийся узел.

Код: (Perl) fill_test_tree.pl

#!/usr/bin/perl -W

use DBI;
use strict;

$| = 1;

(scalar(@ARGV) != 2) and die('Invalid parameters!');

my ($levels, $branches) = @ARGV;
my ($db, $stm1, $cnt, $trans, $start_time);

$trans = 10000; # Транзакций на COMMIT.

$db = DBI->connect('dbi:SQLite:dbname=test.sqlite', '', '') or die('DB not connected!');
$db->do('PRAGMA cache_size = 8192');
$db->do('PRAGMA locking_mode = EXCLUSIVE');

$stm1 = $db->prepare('INSERT INTO tree (parent_id) VALUES (?)');

$start_time = time();

my (@curr, @next);

@next = (1);
$cnt = 0;

for (1..$levels)
{
@curr = @next;
@next = ();

for my $parent_id (@curr)
{
for (1..$branches)
{
$cnt++;
$db->begin_work() if $cnt % $trans == 1;
$stm1->bind_param(1, $parent_id, { 'TYPE' => DBI::SQL_INTEGER });
$stm1->execute();
push(@next, $db->func('last_insert_rowid'));
$db->commit() if $cnt % $trans == 0;
}
}
}

$db->commit() if $cnt % $trans;

# Результат: число уровней, число ветвей на узел, время выполнения скрипта.
print ("$levels $branches " . (time() - $start_time) . "\n");

$stm1->finish();
undef $stm1; # Драйвер SQLite требует удаления всех ссылок до отключения.
$db->disconnect();

Тесты

Создание базы и заполнение тестовыми данными.

$ ./create_db.sh
$ ./fill_test_tree.pl 3 10
3 10 0

Тест на перемещение всего дерева от корня с идентификатором «1» в подчинение узлу с идентификатором «2».

$ time \
   sqlite3 \
   -init init.sql \
   test.sqlite \
   'UPDATE tree SET parent_id = 2 WHERE id = 1;'
-- Loading resources from init.sql

real 0m0.147s
user 0m0.018s
sys 0m0.000s

Пример выборки поддерева по идентификатору узла с помощью материализованного пути. Также ведется подсчет количества узлов в поддереве и нахождение максимальной длины материализованного пути.

$ time \
   sqlite3 \
   -init init.sql \
   test.sqlite \
   'SELECT COUNT(*), MAX(LENGTH(path)) FROM tree
   WHERE path LIKE (SELECT path || '\'%\'' FROM tree WHERE id = 1) ORDER BY path;'
-- Loading resources from init.sql
1111|17

real 0m0.003s
user 0m0.002s
sys 0m0.001s

Как видите, выполнение почти мгновенное — всего 3 миллисекунды.

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

$ time \
   sqlite3 \
   -init init.sql \
   test.sqlite \
   'SELECT * FROM tree
   WHERE path LIKE (SELECT path || '\'%\'' FROM tree WHERE id = 1) ORDER BY path;'
-- Loading resources from init.sql
1|2|/2/1/|
10|1|/2/1/10/|
83|10|/2/1/10/83/|
813|83|/2/1/10/83/813/|
814|83|/2/1/10/83/814/|
815|83|/2/1/10/83/815/|
816|83|/2/1/10/83/816/|
817|83|/2/1/10/83/817/|
818|83|/2/1/10/83/818/|
819|83|/2/1/10/83/819/|
820|83|/2/1/10/83/820/|
... (всего 1112 строк)
82|9|/2/1/9/82/|
803|82|/2/1/9/82/803/|
804|82|/2/1/9/82/804/|
805|82|/2/1/9/82/805/|
806|82|/2/1/9/82/806/|
807|82|/2/1/9/82/807/|
808|82|/2/1/9/82/808/|
809|82|/2/1/9/82/809/|
810|82|/2/1/9/82/810/|
811|82|/2/1/9/82/811/|
812|82|/2/1/9/82/812/|

real 0m0.018s
user 0m0.006s
sys 0m0.002s

На небольших деревьях производительность прекрасная. Как видно, максимальная длина ключа (path) достигает 17 байт. Но при увеличении всего на четыре байта время выборки увеличивается в сорок раз. Видимо SQLite плохо работает с длинными ключами. Вывод: данный метод будет оптимальным для деревьев небольшой глубины вложенности.

Как я уже писал выше, у приведенное модели есть существенный недостаток: нет возможности зафиксировать порядок следования смежных узлов с общим предком. Может кто-нибудь хочет предложить лучшее решение?

Версия для печати

Обсудить на форуме (6)