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

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

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

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

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

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

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

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

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

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

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

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

Рис.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.

Рис. 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 

Конечно, чтобы все работало полноценно, в код надо будет еще добавить:
- При удалении, если Группа не "последняя справа" в Подгруппе Родителя, надо заполнять освободившееся место крайней правой Группой.
- При переносе Групп, необходимо пересчитывать коды Подгрупп.

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

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

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

Ссылки по теме

• Купить программу C++Builder XE3
• Купить программу Delphi XE3
• Каталог программ Embarcadero (CodeGear/Borland)
• Каталог программ Microsoft: Visual Studio 2012
• Задать вопрос ONLine по покупке программ в интернет магазине ITShop
• Новогодний подарок от Учебного центра "Интерфейс"!