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.
С примерами для postgresql.
На английском языке
- Trees in SQL: Nested Sets and Materialized Path (by Vadim Tropashko)
