 |
|
Деревья в базах данных => Материализованные пути
Материализованные пути (Materialized Path)
Содержание
- Готовые библиотеки для работы с материализованными путями?
- Часто задаваемые вопросы?
- Идеи – как устроен Materialized Path
- Смотрите так же
Что такое Materialized Path?
popoff, ForJest
Для каждой вершины дерева можно хранить полный путь от корня к этой вершине. Допустим, есть такая древовидная структура:
1 .
2 1.
3 1.2.
4 1.2.
5 1.2.
6 1.2.5.
7 1.
8 1.
9 1.8.
10 1.8.
11 1.
12 1.11.
13 .
14 .
15 14.
Узлы 1, 13 и 14 являются корневыми. У узла 1 есть четыре ребенка: 2, 7, 8 и 11, а у узла 11 есть только один ребенок – 12.
В приведенном выше примере значение в левом столбце является идентификатором элемента, а значение в правом столбце – «материализованным путем». Таблица для хранения такого дерева строится «в лоб»:
create table t_tree (
k_node int not null,
unique index idx_node(k_node),
s_path tinyblob not null,
unique index idx_path(s_path(255))
)
Выбрать всех потомков (как прямых так и косвенных, «внуков и правнуков»), например, для вершины с путем “1.2.” можно таким запросом:
select
k_node
from
t_tree
where
s_path like '1.2.%'Для приведенного выше примера в результат войдут вершины 3, 4, 5 и 6.
Описанный здесь способ лишь показывает общую идею, на которой основывается способ хранения деревьев с материализованными путями: для каждой вершины мы храним весь путь, от корня к этой вершине.
Описанный мной способ хранения пути – в виде строки идентификаторов, разделенных точкой – не является самым оптимальным. Очень плохо, например, что в нем используется индекс по длинному текстовому полю. Есть много других способов хранения материализованного пути, в том числе без использования строк.
Смотрите также
На русском языке
- Гурец Максим. Проблема хранения деревьев в SQL.
http://sub.rambler.ru/
С примерами для postgresql.
На английском языке
- Trees in SQL: Nested Sets and Materialized Path (by Vadim Tropashko)