Степени — ключ к быстрой иерархии (пример на Django)

Есть множество способов организации иерархического хранения данных. В последнее время меня заинтересовал вопрос по структуре каталога, например, интернет-магазина. А именно, когда Группы и Товары хранятся в разных таблицах.
При навигации посетителя по Группам, должны выводиться Товары из всех Подгрупп.

Хотелось бы, имея код Группы, получить быстрый запрос к таблице Товаров, результатом которого были бы Товары из текущей Группы и всех ее Подгрупп.

Традиционно иерархическая таблица Групп выглядит так:
1. ID — код
2. PARENT — код родителя
3. NAME


Тогда, чтобы получить Товар из всех Подгрупп, потребуется обойти поддерево, собрать все коды Детей и вставить их в запрос к таблице Товаров. Способ, самый медленный для чтения.

Можно еще добавить в таблицу Групп строковое поле:
4. ID_STR

В нем кодируется иерархия Групп. Получается примерно так:

1. А;
1.1. АА; 1.2. АВ;
2. В;
2.1. ВА; 2.2. ВВ;


Это поле является ключом Группы в таблице Товаров.
Чтение при такой организации быстрее, но изменение иерархии требует дополнительные затраты. Так как правок априори меньше чем чтений, то можно с этим смириться.

Таким образом, мы можем не совершать обход дерева Групп для вывода Товаров из всех Подгрупп, а сделать все одним запросом.

Минусы:
— Необходимо вручную вычислять новый строковый код.
— При переносе/удалении группы, перестраивать и таблицу товаров (менять строковый ключ).
— Ограниченность вариантов строкового ключа (во многом, конечно, зависит от выбранной системы кодирования, и в большинстве случаев этим — недостатком можно пренебречь).
— Так же к минусам такого подхода можно отнести необходимость работы со строковыми данными, что влечет за собой дополнительную нагрузку на сервер.

Можно избавиться от последнего недостатка сделав данное поле числовым.
Немного поразмыслив набросал тестовые таблички (Дети — внизу и справа от Родителя):

image
Рис.1

Таблица Групп будет выглядеть так:
1. ID — целочисленный код
2. PARENT — код родителя


Таблица Товаров:
1. ID — код
2. GROUP — код Группы


Тогда все товары из Группы и всех Подгрупп можно будет получать одним запросом указав диапазон кодов.

Например, для Товаров из Группы 16 и всех ее Подргупп (Рис.1, Таблица.2), нужно будет выбрать диапазон (GROUP >=16) AND (GROUP<32)

Следующий недостаток такого подхода — ограниченность вариантов. Но так ли он принципиален?

Максимальное 32-х битное беззнаковое целое = 4 294 967 296.

Если использовать ключ такого типа, то, например, при 6 Уровнях можно получить 39 Детей для каждого Родителя, при 7 уровнях — 23, при 5 — 83 и т.д…

Максимальное необходимое значение ключа можно найти по формуле:
(КоличествоДетей+1)^КоличествоУровней

Если БД не имеет возможность хранить беззнаковое целое, мы можем использовать и отрицательный диапазон, просто задаем самый “верхний” элемент (корень дерева) отрицательным числом. Для максимального использования 32-х разрядного целого, при 6 уровнях и 39-и Детях это будет — 2 048 000 000.

image
Рис. 2

Для примера с иллюстрации выше (Рис.2), максимальное беззнаковое целое равно 64, если задействовать отрицательный диапазон, то root надо будет поставить = -32

Для большинства задач 4 294 967 296 более чем достаточно (по крайней мере мне). Нужно больше Уровней — уменьшаем количество Детей, и наоборот. Если же такие “рамки” для кого-то окажутся все же тесны, можно взять 64-х битное целое. Скорость работы с такими значениями будет почти такой же.

Чтобы проверить все это в работе я сделал простейшее Django приложение. В модель ввел 2 дополнительных поля — Уровень и КоличествоУжеИмеющихсяДетей. Так же реализовал добавление нового элемента Группы и его удаление. Настройки для дерева сейчас там стоят такие: КоличествоДетей = 39, КоличествоУровней = 6. Ключ — 32-х разрядное целое. Конечно же их можно поменять (при изменении настроек в таблице должна быть только одна запись — root).
Еще нужно не забыть вручную добавить root элемент в таблицу.

#coding: utf-8

# Родительский элемент надо внести в БД вручную!!!
#
# Максимльное целое, которое может понадобится, считается по формуле:
# (КоличествоДетей+1)^КоличествоУровней
#
# Если целое знаковое (а это так почти всегда), то полученное число делим на 2
#
# 32-х разрадное целое позволяет хранить от -2,147,483,647 до 2,147,483,648
#
# Для примера, хотим 6 Уровней при 39 Детях у каждого элемента
# Тогда получаем начальный id=-((39+1)^6)/2, и вручную в БД вносим Группу со следующими значениями:
#   id = -2,048,000,000
#   parent = -2,048,000,000 
#   level = 0
#   count_childs= 0 
#   name = 'root' # тут можно любое понятное имя
# 
# Некоторые допустимые для int32 значения Уровень/Дети:
# 3/1624
# 4/255
# 5/83
# 6/39
# 7/23
# 8/15
# Если рамки слишком малы, в определении модели используем int64, т.е. BigIntegerField()

LV = 6   # Определяем количество Уровней...
CH = 39  #                  ...и Детей

from django.db import models

from django.db.models.signals import post_delete # Сигнал при удалении...
from django.dispatch import receiver             # ... и декоратор для функции его обработки


class Group(models.Model):
    
    id = models.IntegerField(primary_key=True)
    parent = models.ForeignKey('self')
    level = models.SmallIntegerField(blank=False, null=False)
    count_childs= models.SmallIntegerField(blank=False, null=False)
    name = models.CharField(max_length=150, blank=False, null=False)
    # ...
    
    def save(self, *args, **kwargs):
        # если создаем новую Группу каталога...
        if self.id==None: 
                        
            # получим запись о Родителе 
            parent_obj=self.parent
            
            # если количество Детей и Уровней не превышено
            if (parent_obj.count_childs < CH) and (parent_obj.level < LV):
                
                # вычислим новый Код Группы
                self.id = ((CH+1)**(LV-parent_obj.level-1)) \
                                * (parent_obj.count_childs+1) + parent_obj.id
                
                # Уровень Группы делаем на 1 больше от Уровня Родителя
                self.level = parent_obj.level+1
                
                # Детей у Группы пока нет
                self.count_childs = 0
                
                # увеличим количество Детей у Родителя
                parent_obj.count_childs+=1
                parent_obj.save()
                                            
            else:
            # ... иначе, Группу сделать не можем, выходим
                raise ValueError("Превышен допустимый Уровень или количество Потомков")
        
        # запишем изменения
        super(Group, self).save(*args, **kwargs)
        
    
    def __unicode__(self):
        return u'%s (lv=%s ch=%s id=%s)' % (self.name, self.level, self.count_childs, self.id)
    
# END class Group
  
# При удалении Группы уменьшаем количество детей у Родителя    
@receiver(post_delete, sender=Group)
def my_post_delete(sender, **kwargs):
    parent = (kwargs.get("instance")).parent
    if parent.count_childs > 0:
            parent.count_childs-=1
            parent.save()


Чтобы быстро проверить работу, можно сделать тест для получения дерева как на Рис.1 Таблица 2. Для этого надо внести в таблицу root-элемент со значениями:
id = 0
parent = 0
level = 0
count_childs= 0
name = 'root'
… и изменить константы в коде, представленном выше, на LV = 3 CH = 3

Конечно, чтобы все работало полноценно, в код надо будет еще добавить:
— При переносе Группы, необходимо пересчитывать коды всех Детей. Делается одним запросом (UPDATE). Необходимо контролировать перенос «вниз», дерево же не резиновое :)
— При удалении, если Группа не “последняя справа” в Подгруппе Родителя, надо заполнять освободившееся место крайней правой Группой этого же уровня. Делается одним запросом (UPDATE).

Этого пока не сделал (программирование, в течении 15 последних лет — только мое хобби), но не вижу препятствий для реализаций данных алгоритмов (реализация «на бумаге» уже есть).

Таким образом, получилась структура, работающая гораздо быстрее чем при использовании закодированного символьного ключа, ну и занимающая меньше места.

При использовании int64, ограничение по размерам иерархической таблицы, будут значительно ниже. Но и int32 хватит для большинства задач, все-таки в иерархии хранятся только Группы, а каталогов с параметрами, где Дети>39 и Уровни>6, я пока не встречал (ну или не замечал).

Буду благодарен за любые комментарии.

UPD 20/01/2013
Извиняюсь за правку статьи, но забыл упомянуть, про не очевидный, может быть, момент… Так как код любого элемента, при наличии данных о размерности дерева (а они у нас есть), несет в себе всю информацию о своем положении, то операции по переносу Групп в таблице, делаются одним запросом.
UPD 22/01/2013
Написал более подробную статью про данный метод. В ней есть ссылки на файлы с полной реализацией алгоритма на Django
Поделиться публикацией

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

    +1
    Это вы сейчас database tree traversal изобрели?
    // www.zaachi.com/en/items/modified-preorder-tree-traversal-algoritmus-1.html
      0
      На всякий случай, для обеспечения консистентности данных, обновление полей left/right лучше делать триггерами автоматически и хранить это в базе данных с нормальной поддержкой транзакций и ACID (как минимум, InnoDB). Иначе, когда всё это поломается при параллельном изменении, чинить эту структуру можно будет до морковкина заговения. Изменение подобной структуры кодом вне БД чревато и требует как минимум заморочек на transaction isolation level.
        0
        Про триггеры, целостность, транзакции и проч… Вы безусловно правы.
        Но, при всем моем уважении, статья не об этом.
        Перечитав сейчас еще раз, я понял, что в Вашем комментарии виноват я сам.

        Если в двух словах, статья о том, что если кто использовал строковые ключи вида «ААВВСС...» для хранения иерархии, их, почти всегда, можно заменить на цифры (со всеми вытекающими...). Один из способов, каким это можно сделать, я и описал.
        0
        Не сомневаюсь, что подход, предложенный мной, уже кем-то использовался. В «символьном» варианте это точно.
        Но все же в приведенной Вами ссылке немного другое вроде (полностью не читал т.к. не силен в англ.), по крайней мере у меня нет полей «лево»/«право».
        В любом случае, изобретать самому приятно :)
          0
          В любом случае, изобретать самому приятно :)

          С этим сложно поспорить :)
            0
            И еще, в моем варианте, зная только код элемента, количество уровней и детей в структуре дерева, так же можно узнать код родителя и код/коды соседей Не делая запросов к базе (т.е. просто вычислить, даже поле parent не нужнО).
        0
        В postgresql для этих целей есть ltree. На хабре даже статейка была про это: habrahabr.ru/post/130371/
          0
          А ещё в последних версиях PostgreSQL есть WITH RECURSIVE. А в Oracle давным давно существует CONNECT BY:
          www.adp-gmbh.ch/ora/sql/connect_by.html
            0
            Спасибо за ссылку. Я знал про это, просто не пользовался (ну и не изучал плотно данный вопрос соот-нно).
            Код на Django привел лишь чтобы показать работающую (хоть и не доделанную) реализацию.
            Я бы еще все создания/удаления в тригеры засунул.
            Но сейчас модно убирать логику из серверного движка, для веб приложений это отчасти оправдано.
            0
            Хотелось бы, имея код Группы, получить быстрый запрос к таблице Товаров, результатом которого были бы Товары из текущей Группы и всех ее Подгрупп.


            Откройте для себя Materialized Path )
              0
              Я не знал, что это так называется, но думал и про этот способ.
              Для приведенного примера…
              В таблице Товаров хоть и будут храниться целые числа, но они не будут идти подряд в рамках подгруппы.
                0
                Или приведённые мной выше nested sets aka modified preorder tree traversal :)
                  0
                  Nested sets — тоже можно использовать.
                  Но, по моему мнению, он сложнее для понимания и реализации.
                  В предложенном мной способе, есть один нюанс — ограничения по уровням/детям. Но int64 значительно расширяет диапазон (кому мало int32 :) )
                    0
                    В реализации с nested set нужно либо делать товар категорией, либо выбирать с джойном, либо нормализировать базу. И да, nested set ужасно медленный на вставку (хотя это важно тольком если вы не выбрали вариант с джойном).
                      0
                      И да, nested set ужасно медленный на вставку (хотя это важно тольком если вы не выбрали вариант с джойном).

                      При этом он терминально быстрый на чтение в силу того, что идеально индексируется. И тут уже надо под задачи подбирать. Если у стоит задача сделать дерево, которое будут часто менять — тогда, безусловно, надо использовать другие способы. Если же задача сделать, скажем, дерево типов товаров в магазине, которое будут менять раз в год, а читать при каждом втором запросе (вопрос кэширования опустим) — тут всё ровно наоборот.
                        0
                        Вопрос в том что задача стоит так:
                        имея код Группы, получить быстрый запрос к таблице Товаров

                        лично я делаю выводы что запросов в таблицу типов при этом быть не должно, поэтому и уточнение.

                        А так, конечно же, выбор инструмента зависит от поставленной задачи )
                          0
                          Плюс, если проиндексировать код Группы в таблице Товаров — они будут идти Подряд, будет выбираться только нужный Диапазон, и запрос сработает быстрее нежели если «выковыривать» понавтыканные записи, пусть и отсортированные, из всей многомиллионной (мы же не зря всё это городим) таблицы.
                          При использовании же int64, большинство интернет-магазинов, вообще смогут обойтись одной таблицей (Т.е. будет одна таблица — ГруппыТовары).
                  0
                  А чем не устроило django-mptt? Как раз реализация Modified Preorder Tree Traversal.
                    0
                    А разве у меня реализация Modified Preorder Tree Traversal? :)

                    Я хотел рассказать о самой идее.
                    Ее можно применить и с Django, и с другими web-фреймворками, в приложениях клиент-сервер, использую PostgreSQL, MySQL, др БД… Можно вынести логику и ограничения в движок БД, можно оставить часть (или все) в фреймворке (как делает Django)… и проч. и проч…

                    Django-mptt отличное приложение, но оно мне не требуется для абсолютно всех задач.
                    Пример на Django, это только потому, что пилю потихоньку один свой проект в свободное время.
                    Весь смысл же здесь, в вычислении кода очередного Ребенка:
                    self.id = ((CH+1)**(LV-parent_obj.level-1)) * (parent_obj.count_childs+1) + parent_obj.id
                    и в том, что Подгруппы можно получить одним запросом по целочисленному ключу.
                      0
                      Не знаю, есть ли название для вашего алгоритма, не встречал такого.
                      В MPTT тоже прекрасно получаются все дети одним запросом. Недостаток один — обновляется дерево долго. Но тут надо смотреть для каждого применения в отдельности. С другой стороны нет ограничений по уровням и количеству детей.
                        0
                        Названия я тоже не встречал :)
                        Реализации такого подхода есть, но там ключ кодируют символами, в статье я немного написал про это.
                        Сама идея пришла мне в голову 3 года назад, просто случая не было ее опробовать и применить. За это время читал и Хабр и другие источники, нигде не видел похожего. Наверное, программистов отпугивает ограничение по количеству Уровней/Детей, которое надо выбрать при проектировании. Но мне вполне хватает отведенных рамок даже при использовании int32.
                          0
                          Да нет, ограничения не отпугивают, но как-то слишком сложно подсчёт сделан. Если кто-то будет ещё этот код смотреть, то охренеет без комментариев. Всё-таки лучше использовать для таких вещей стандартные алгоритмы без магии, имхо.
                            0
                            Согласен с этим. Но… все остальное очень наглядно.
                            Формула вычисления написана, про нее потом вообще можно забыть. Это она здесь в теле функции, по правильному ее, конечно, надо выделить, потому что пригодится еще. Отправлять в нее ID Родителя, и получать новый ID Ребенка.

                            Думаю, еще рисунки неудачные. Многие не замечают, наверное, что Дети — Внизу_и_Справа от Родителя, до следующего элемента на уровне Родителя. Плюс с элементом root туманно объяснил. Если смотреть на приведенные рисунки, то он будет левее первого значимого элемента, а не сверху.
                            Честно говоря, понадеялся как раз на код. В будущем буду тщательнее готовить статьи.
                              0
                              Хорошо еще, что ввел избыточное поле «Уровень», его ведь просто можно вычислить на основе ID и данных о размерности дерева :)

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

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