Welcome to php club

Деревья в базах данных => Материализованные пути

Материализованные пути (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.

На английском языке



 
Комментариев нет. [Показать комментарии/форму]