Метод хранения материализованных путей в БД.

    Основным преимуществом данного метода является доступ к дочерним узлам любого уровня в один запрос к БД (правда с INNER JOIN).

    Пример:
    необходимо в разделе /company/ добраться до списка новостей (item1, item2)
    • /company/ О компании
      • /company/news/ Новости
        • /company/news/item2/ Вторая новость
        • /company/news/item1/ Первая новость новость

      • /company/history/ История
      • /company/contacts/ Контакты


    Данные хранятся в таблицах со следующей структурой:
    paths — дерево с путями
    id
    parent_id # хранится id родителя (paths.id)
    name # имя узла, уникальное в пределах одного уровня
    path # путь (/company/, /company/news/item1/)
    title # для наглядности


    path_have_childs — таблица ссылок, хранит список дочерних узлов с уровнями относительно родительского узла

    parent_id # id родительского узла (paths.id)
    child_id # id дочернего узла (paths.id)
    level # уровень дочернего узла относительно родительского


    Данные — таблица с путями:
    id parent_id name path title
    1   / Главная
    2 1 company /company/ О компании
    4 2 news /company/news/ Новости
    5 4 item1 /company/news/item1/ Новость 1
    6 4 item2 /company/news/item2/ Новость 2
    3 1 catalogue /catalogue/ Каталог
    7 3 category1 /catalogue/category1/ Категория 1
    8 7 category2 /catalogue/category1/category2/ Категория 2


    Дополнительная таблица — хранилище уровней дочернего узла относительно родительского:
    parent_id child_id level
    1 2 1
    1 8 3
    1 7 2
    1 6 3
    1 5 3
    1 4 2
    1 3 1
    2 5 2
    2 6 2
    2 4 1
    3 7 1
    3 8 2
    4 6 1
    4 5 1
    7 8 1

    Запрос генерирующий дополнительную таблицу для уровней — для каждого узла находятся все дочерние узлы, даже те которые не являются непосредственно дочерними, и вычисляется уровень вложенности относительно текущего узла:
    INSERT INTO path_have_childs
    SELECT
        P.id AS parent_id,
        C.id AS child_id,
        (LENGTH(C.path) - LENGTH(REPLACE(C.path,'/','')))
    - (LENGTH(P.path) - LENGTH(REPLACE(P.path,'/','')))
    FROM paths AS P
        INNER JOIN paths AS C ON (C.path LIKE CONCAT(P.path, '_%'))


    Выбор всех дочерних узлов узла X (parent_have_childs.parent_id) с уровнем Y (parent_have_childs.level):
    SELECT C.path
    FROM path_have_childs AS PHC
        INNER JOIN paths AS C ON (PHC.child_id = C.id)
    WHERE
        PHC.level = Y
        AND PHC.parent_id = X


    Конструктивные комментарии и критика приветствуются…
    Поделиться публикацией

    Комментарии 36

      +1
      зачем вам вторая таблица?
      если уж изворачиваться с вычислениями количества слэшей в поле path то это самое количество слэшей и есть уровнем вложенности
        0
        Ой, как грубо. (Like, concat, LENGTH, replace, join) %\

        Существует гораздо красивее и быстрее способ ;)

          0
          зачем тебе относительные уровни?
            +1
            Например:
            каталог товаров, у каждой категории есть фотогалерея товаров (с группировкой по альбомам), проекты (галерея выполненных работ с импользованием товаров в этой категории). когда пользователь находится на странице категории товаров, то ему нужно показать несколько фоток из «фотогалеря товаров» и пару фоток из «проекты»:

            ....category/
            ........category/gallery/
            ............category/gallery/album1/
            ................category/gallery/album1/photo1/
            ................category/gallery/album1/photo2/
            ........category/projects/
            ............category/projects/photo1
            ............category/projects/photo2

            Доступ к элементам осуществляется в 2 запроса — один для 3'го уровня, другой для 2'го.
              0
              так зачем тебе хранить _относительные_ уровни?

              что ты будешь делать, когда тебе потребуется вывести вообще все фотки с сортировкой по дате и пейджером?
                0
                Предположем что в ....category/ необходимо вывести все фотки из фотогалереи:

                SELECT C.path, C.created
                FROM path_have_childs AS PHC
                INNER JOIN paths AS C ON (PHC.child_id = C.id)
                WHERE
                PHC.level = 3
                AND PHC.parent_id = $category_id
                ORDER BY C.created
                LIMIT $from, $limit

                Если необходимо вообще все фотки — т.е. тип выбираемых объектов будет Photo, то:

                SELECT C.path, C.created
                FROM path_have_childs AS PHC
                INNER JOIN paths AS C ON (PHC.child_id = C.id)
                WHERE
                PHC.level >= 2 AND C.type_id = $object_type_id
                AND PHC.parent_id = $category_id
                ORDER BY C.created
                LIMIT $from, $limit

                C.type_id, C.created — поля в таблице paths
            0
            Я предпочитаю хранить только parent_id, а путь вычислять уже в программе
              0
              Это «обьектный» подход.

              Автор имеет ввиду совсем другое :)
              Но реализация ужасна.
                +3
                Опишите пожалйста более изящный метод.
                  –1
                  Вспоминается одна схожая тема, где вы также уверяли, что суслик есть, хоть его и не видно.
                    0
                    Кому надо в pm я обьяснил
                  +1
                  Т.е. для формирования пути элемента вы каждый раз обращаетесь к БД?
                    0
                    Нет конечно
                      0
                      > Я предпочитаю хранить только parent_id, а путь вычислять уже в программе
                      опиши кратко алг., если можно
                        0
                        В моем случае нужно выводить сразу все дерево разделов меню, поэтому я просто выбираю SELECT * FROM pages.
                        А дерево строю уже программе, попутно сохраняя для каждого узла путь к нему.
                          0
                          Понял, спасибо. В принципе это частный случай.
                  +1
                  Есть замечательная вещь — Nested Sets dev.mysql.com/tech-resources/articles/hierarchical-data.html

                  Одна таблица, только 3 дополнительных поля — уровень, левая и правая границы. Одним запросом вычисляются все дочерние, или путь наверх или еще что. Но добавление элемента обходится в 3 запроса.
                    0
                    Есть еще «коммерческие» алгоритмы MP, где на выборку 2 запроса (очень быстрые (можно заменить одним)) и на запись 2.
                    Логика почти как в NS, но гораздо «интуитевнее». И алгоритм гораздо надежнее в плане целостности данных в отличие от NS.
                      0
                      А где можно почитать про эти алгоритмы? У меня получается 3 запроса на добавление записи и 2 на чтение. Использовать Nested Sets не хочется, т.к. пересчитывать все узлы для дерева при добавлении / удалении / перемещении записи кажется накладным.
                    0
                    Слишком сложно и избыточно. Тоже использую MP, при этом остаются только поля: id, name, path, title. Поле path хранится путь родительского узла. Любые выборки делаются в один простой запрос (выбор потомков, братьев, предков ну и естественно элемента по его пути)
                      0
                      кроме LIKE и REGEXP сейчас на ум ничего не приходит…
                        0
                        Запросы примерно такие:
                        Найти узел по его адресу: SELECT * FROM tbl WHERE name = "item1" AND path = "/company/news";

                        Найти братьев узла SELECT * FROM tbl WHERE path = "/company/news" # Если нужно исключить себя, добавляем AND name != "item"

                        Находим предков SELECT * FROM tbl WHERE (path = "" AND name = "company") OR (path = "company" AND name="news")

                        При написании простенького класса все очень удобно
                          0
                          Забыл еще потомков: SELECT * FROM tbl WHERE path = "/company/news/item1" или WHERE path LIKE "/company/news/item1%" Если нужно найти всех потомков
                            +1
                            Раньше использовал такой же способ, пока количество записей базы не достигло нескольких тысяч и не начались сильные тормоза. Очень удобно, по LIKE работает с большими таблицами очень медленно.
                              0
                              Буду иметь ввиду. Хорошо то, что LIKE практически не применяется, редко нужно искать всех потомков, обычно достаточно прямых потомков.
                                0
                                тормоза LIKE и REGEXP как раз и заставили меня задуматься над другими способами доступа к дочерним узлам…
                          0
                          Для этой же самой задачи пользуюсь nested sets. Таблица, в которой хранится иерархия, состоит из собственно (id, left, right, level, foreign_key), а таблица, в которой хранятся данные, состоит из (id, ..., url_slug).

                          Данных немного (и много никогда не будет), поэтому я могу себе позволить выбрать все данные.

                          А затем строим обычное дерево (rose tree), преобразуем его в zipper (и даже zipper от zipper!), и выполняем свою грязную работу. :)
                            +1
                            td # id родительского узла (paths.id)
                            td # id дочернего узла (paths.id)
                            td # уровень дочернего узла относительно родительского


                            Поправь пожалуйста описание таблицы, а то три колонки с именем td =)
                              0
                              Спасибо, сделал… писал быстро, собственно как и сам алг. — для проверки мысли…
                              –3
                              Вот извращенцы. Я делаю так:

                              id Name Level Path
                              1 Category1 1 1
                              2 Category2 1 2
                              3 Category3 1 3
                              4 Category11 2 1,4
                              5 Category111 3 1,4,5
                              6 Category12 2 1,6
                              7 Category121 3 1,6,7
                              8 Category31 2 3,8
                              9 Category311 3 3,8,9
                              10 Category312 3 3,8,10
                              11 Category313 3 3,8,11

                              Path текстовая, делаем нужной длинны (15 символов хватает для 5 уровней. Можно делать SELECT * FROM table WHERE path IN(SELECT path FROM table WHERE catid = $id), можно двумя запросами это сделать, можно тут же получить всех предков через LIKE :) Крч удобно и шустро. Однозначно легче по нагрузке чем Nested Sets и проще в менеджменте.
                                0
                                Опять же, всё это удобно и шустро, пока записей в базе до тысячи. Данный метод очень ресурсоемкий и на «жирных» базах очень долго отрабатывает.
                                  0
                                  Мне кажется, что этот способ с использованием id как пути наиболее удобен. Но, чтобы добавить запись, нужно сделать 3 запроса: 1) получить путь родителя; 2) добавить новую запись и узнать ее id; 3) обновить новую запись, добавив полученный id к пути.

                                  Вариант с перемещением ветки не кажется страшным, т.к. в отличие от Nested Sets нужно обновить пути только для текущей ветки, а не для всего дерева.

                                  А вот какие удобства дает level — не понятно. Мне кажется, что это поле избыточно.
                                  –1
                                  А если вдруг /catalogue/category1/ превратился в /catalogue/categoryА/, то всё, всю базу переделывать?
                                    0
                                    В данном случае поменялось только имя, необходимо отредактировать путь у дочерних элементов /catalogue/categoryА/, id остался прежним — дополнительная таблица не модифицируется.

                                    При перемещени узла, необходимо будет изменить пути для дочерних узлов, а так же удалить старые записи и добавить новые в доп. таблицу.
                                    0
                                    зачем вообще нужен числовой id, когда путь уникален?
                                      +1
                                      У нестед сед есть только один существенный минус — перемещение узла с потомками. Недавно на хабре пролетал бенчмарк на хранение иерархии в БД.

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое