Tree/Mp

Материал из PhpWiki.

Перейти к: навигация, поиск
 Деревья в базах данных =>  Материализованные пути

Содержание

Материализованные пути (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/ http://sub.rambler.ru/read/rambler.computer.soft.webdevelopment/?date=2005-02-16&time=13:05 http://sub.rambler.ru/

С примерами для postgresql.

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

  • Trees in SQL: Nested Sets and Materialized Path (by Vadim Tropashko)
    • http://www.dbazine.com/oracle/or-articles/tropashko4
Ссылки
Реклама