Модифицированный обход дерева предварительных заказов в Django

Автор оригинала: Adam McQuistan.

Вступление

Эта статья является продолжением предыдущей статьи под названием “Рекурсивные модельные отношения в Django”, в которой демонстрировался способ использования голых возможностей Django для определения классов с поддержкой баз данных , моделирующих общий вариант использования рекурсивных отношений. Прецедент, который я намерен удовлетворить, – это общие отношения между сотрудниками и менеджерами сотрудников, которые также являются самими сотрудниками.

Оценка предшествующей реализации

В предыдущей статье был определен класс Employee , который переводится в таблицу базы данных структуры “employee(id, first_name, last_name, role, manager_id)”, где manager_id-это внешний ключ, ссылающийся на идентификатор сотрудника, представляющий менеджера текущего сотрудника. Этот тип реализации хранения рекурсивных данных в базе данных известен как метод смежного списка .

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

SELECT id, first_name, last_name, role, manager_id FROM employee ORDER BY id;

Таблица сотрудников

Глядя на таблицу сотрудников, приведенную выше, вы можете определить иерархическую природу данных. Например, вы можете сказать, что Джейн Доу является президентом (вершина иерархии), потому что ее запись manager_id пуста, и вы также можете сказать, что два сотрудника отчитываются перед ней, Джон Доу и Адам Смит, потому что их записи manager_id равны идентификатору сотрудника Джейн, равному 1.

Ниже я демонстрирую использование экземпляра класса Employee из предыдущей статьи, представляющего Джейн Доу, для извлечения сотрудников, которые отчитываются непосредственно перед ней.

(venv) $ python manage.py shell
Python 3.6.2 (default, Jul 17 2017, 16:44:45)
>>> from hrmgmt.models import Employee
>>> jane_doe = Employee.objects.get(pk=1)
>>> managers = jane_doe.employee.all()
>>> for m in managers:
...     print(m.first_name, m.last_name, m.role, m.manager_id, m.manager_id)
... 
John Doe MGR 1
Adam Smith MGR 1
>>>

Под капотом Django ORM выдает запрос, подобный следующему, чтобы получить сотрудников непосредственно под Джейн Доу, когда свойство employee вызывается на экземпляре класса Employee .

SELECT * FROM htmgmt_employee WHERE manager_id = 1  

Аналогично, чтобы получить сотрудников, которые отчитываются перед Джоном Доу, вы должны вызвать поле employee relationship в экземпляре класса Employee , представляющем Джона Доу, и под капотом ORM выдаст запрос, подобный этому:

SELECT * FROM hrmgmt_employee WHERE manager_id = 2

Таким образом, мы можем определить иерархию компании, начиная с вершины (Джейн Доу) и продвигаясь вниз по цепочке отчетности. Однако для каждого нового менеджера, которого вы идентифицируете, вам снова придется вызывать свойство employee relationship, и Django ORM выдаст еще один запрос для получения нового набора сотрудников, отчитывающихся перед предыдущим менеджером.

Хотя этот подход, безусловно, будет работать – давая информацию, которую мы хотим получить, когда мы хотим пройти свой путь вниз по списку компаний, – есть проблема производительности. Каждый новый уровень управления, с которым мы сталкиваемся, требует еще одного обращения к базе данных, и эти запросы накапливаются, потребляя все больше и больше ресурсов, что приводит к увеличению времени ожидания клиента, вызывающего программу. Пользователи быстро станут раздражаться, глядя на прялку терпения во вкладке браузера.

Та же проблема возникает, когда мы пытаемся пройти вверх по списку сотрудников от обычного сотрудника вверх по уровням управления и заканчивая президентом. Например, рассмотрим, когда вы хотите определить восходящую линию управления, начиная с Джона Брауна.

Вы бы идентифицировали идентификатор менеджера для Джона Брауна, который равен 2, а затем сделали бы звонок в базу данных, чтобы определить менеджера сотрудника с идентификатором 2.

/* Get John Brown and determine his associated manager_id */
SELECT * FROM htmgmt_employee WHERE first_name = 'John' AND last_name = 'Brown';

/* Get the employee with id of 2 */
SELECT * FROM htmgmt_employee WHERE id = 2;

Это возвращает Джона Доу, менеджера Джона Брауна, и мы видим, что его manager_id равен 1, что указывает на то, что есть по крайней мере еще один уровень управления выше него. Еще раз мы делаем еще один запрос, чтобы определить, является ли сотрудник с идентификатором 1 вершиной управленческой иерархии или существует еще один уровень управления.

/* Get the employee with id of 1 */
SELECT * FROM htmgmt_employee WHERE id = 1;

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

Модифицированный Обход Дерева предварительных заказов

К счастью, существует еще один метод хранения и извлечения иерархических данных в базе данных, известный как Модифицированный обход дерева предварительных заказов (MPTT). Этот второй способ использует древовидную структуру данных для моделирования данных, а также некоторую интуитивную маркировку связанных узлов дерева, что позволяет обходить их на основе меток.

Ниже приведено древовидное представление данных в предыдущей таблице списка сотрудников.

Схема маркировки начинается с размещения 1 слева от корневого узла, президент Джейн Доу в этом примере, затем вы спускаетесь на один узел слева от корня. В этом узле сразу ниже и слева увеличьте количество и обозначьте этот новый узел цифрой 2. Этот процесс продолжается вплоть до самого нижнего дочернего (листового) узла, Джо Шмо в этом примере. Затем вы помечаете правую сторону дочернего узла следующим шагом и перемещаетесь боком через братьев и сестер вправо, помечая левую и правую стороны, увеличиваясь по мере продвижения.

Как только вы достигнете края поддерева, Джон Браун, вы пройдете вверх по дереву, пока не достигнете уровня, на котором есть братья и сестры, затем вы снова переместитесь в сторону и вернетесь вверх по дереву, аналогично предыдущему поддереву, встреченному до достижения корня снова.

Следующее, что нужно сделать, – это перевести это вложенное дерево в плоскую структуру таблицы. Это достигается путем определения двух дополнительных столбцов значений “left” и “right”. Однако, поскольку left и right являются зарезервированными ключевыми словами в языке SQL, фактические реализации используют аббревиатуры, такие как “lft” и “rgt”.

Ниже приведен пример таблицы минимальной реализации структурированной таблицы MPTT для списка сотрудников.

employee_mptt

Теперь, когда данные организованы и аннотированы значениями в столбцах lft и rgt, мы получили большую гибкость, контроль и эффективность в том, как мы извлекаем данные.

Используя приведенную выше таблицу MPTT-structured, вы можете перечислить сотрудников, которые отчитываются перед менеджером John Doe, используя следующий SQL-запрос.

SELECT * FROM employee_mptt WHERE lft > 2 and rgt < 7 ORDER BY lft;

Однако, чтобы продемонстрировать эффективность структуры MPTT, я еще раз прослежу процесс присоединения менеджмента, начиная с Джона Брауна. Я могу сделать это, включив несколько предикатов в раздел WHERE запроса, указав, что lft меньше 6, а rgt больше 6, а затем ORDER -ing by rgt перечислит иерархию управления в порядке возрастания, все за один заход в базу данных.

SELECT * FROM employee_mptt WHERE lft < 5 AND rgt > 6 ORDER BY rgt;

Аннотирование записей сотрудников столбцами lft и rgt в соответствии со структурой MPTT предоставляет нам улучшенный способ просмотра данных и сбора полезной информации с более эффективным и меньшим количеством взаимодействий с базой данных. Например, если мы хотим знать, сколько сотрудников находится под управлением Джона Доу в структуре, предполагая, что у нас уже есть информация для Джона, мы можем применить эту простую формулу:

abs((rgt - lft - 1)) / 2 = # of managed employees

Подключив значения rgt и lft Джона, мы получим:

abs((2 - 7 - 1)) / 2 = 2

Это дает нам ответ и вообще не требует каких-либо дополнительных взаимодействий с базой данных.

Django-mptt

Удивительное сообщество, использующее и разрабатывающее веб-фреймворк Django, создало проект Django-MPTT , который расширяет базовые функциональные возможности Django и реализует MPTT. Проект Django-MPTT предлагает ряд удобств, которые делают взаимодействие с иерархическими данными в структуре MPTT очень удобным при достижении эффективности, связанной с извлечением данных MPTT.

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

Если вы хотите следовать дальше, вы можете скачать код из моей учетной записи GitHub здесь , начиная с тега для начала этого урока под названием “mptt-start”.

Откройте командный терминал, создайте новую виртуальную среду и установите следующие требования:

(venv) $ pip install django django-mptt

После запуска начальных миграций, как описано в предыдущей статье, загрузите проект в свою любимую интегрированную среду разработки или текстовый редактор, откройте скрипт Python модели в каталоге “hrmgmt” и добавьте следующий код.

# hrmgmt/models.py

from django.db import models

from mptt.models import MPTTModel, TreeForeignKey

class EmployeeMptt(MPTTModel):
   STANDARD = 'STD'
   MANAGER = 'MGR'
   SR_MANAGER = 'SRMGR'
   PRESIDENT = 'PRES'

   EMPLOYEE_TYPES = (
       (STANDARD, 'base employee'),
       (MANAGER, 'manager'),
       (SR_MANAGER, 'senior manager'),
       (PRESIDENT, 'president'))

   role = models.CharField(max_length=25, choices=EMPLOYEE_TYPES)
   first_name = models.CharField(max_length=100)
   last_name = models.CharField(max_length=100)
   parent = TreeForeignKey('self', null=True, related_name='employee')

   def __str__(self):
       return "".format(self.first_name, self.last_name)

   def __repr__(self):
       return self.__str__()

Первый новый оператор добавляет импорт для классов MPTTModel и TreeForeignKey из библиотеки django-mptt. Затем определяется класс Employee Mptt .

Класс EmployeeMptt наследуется от MPTTModel , который добавляет поля класса left , right , level и tree_id в подкласс ( EmployeeMptt ). Поля работают следующим образом:

• lft : целочисленное поле, как описано в предыдущем разделе
• right : целочисленное поле, как описано в предыдущем разделе
• level : целочисленное поле, указывающее уровень иерархии для каждого экземпляра.
• tree_id : целочисленное поле, аналогичное предыдущему полю статьи Employee class field manager_id

Однако более полезной функцией, возникающей в результате наследования от MPTTModel , являются методы, которые идут вместе с ним, которые абстрагируют реализацию вышеупомянутых полей и обеспечивают предпочтительные функциональные возможности для работы с древовидной структурой.

• get_ancestors(по возрастанию=False,)
• get_children()
• get_descendants(include_self=False)
• get_descendant_count()
• get_family()
• get_next_sibling()
• get_previous_sibling()
• get_root()
• get_siblings(include_self=False)
• insert_at(target,,)
• is_child_node()
• is_leaf_node()
• is_root_node()
• move_to(цель,)

Поле TreeForeignKey ведет себя практически так же, как и обычные модели django.db.ForeignKey но он также отображает параметры иерархии дерева с вложенностью в формы Django.

Теперь , когда мы написали код для определения EmployeeMptt , давайте переведем код модели в таблицы базы данных в соответствии со структурой MPTT. В вашем терминале сделайте и запустите миграцию для класса Employee Mptt :

(venv) $ python manage.py makemigrations
Migrations for 'hrmgmt':
  hrmgmt/migrations/0002_employeemptt.py
    - Create model EmployeeMptt

Проверьте DDL SQL, который будет выдан:

(venv) $ python manage.py sqlmigrate hrmgmt 0002
BEGIN;
--
-- Create model EmployeeMptt
--
CREATE TABLE "hrmgmt_employeemptt" ("id" integer NOT NULL PRIMARY KEY AUTOINCREMENT, "role" varchar(25) NOT NULL, "first_name" varchar(100) NOT NULL, "last_name" varchar(100) NOT NULL, "lft" integer unsigned NOT NULL, "rght" integer unsigned NOT NULL, "tree_id" integer unsigned NOT NULL, "level" integer unsigned NOT NULL, "parent_id" integer NULL REFERENCES "hrmgmt_employeemptt" ("id"));
CREATE INDEX "hrmgmt_employeemptt_lft_c82902c3" ON "hrmgmt_employeemptt" ("lft");
CREATE INDEX "hrmgmt_employeemptt_rght_c6110254" ON "hrmgmt_employeemptt" ("rght");
CREATE INDEX "hrmgmt_employeemptt_tree_id_7abd1eb2" ON "hrmgmt_employeemptt" ("tree_id");
CREATE INDEX "hrmgmt_employeemptt_level_687f7b49" ON "hrmgmt_employeemptt" ("level");
CREATE INDEX "hrmgmt_employeemptt_parent_id_88909826" ON "hrmgmt_employeemptt" ("parent_id");
COMMIT;

Запустите миграцию:

(venv) $ python manage.py migrate
Operations to perform:
  Apply all migrations: admin, auth, contenttypes, hrmgmt, sessions
Running migrations:
  Applying hrmgmt.0002_employeemptt... OK

Теперь используйте оболочку Django для заполнения новой таблицы” hr mgmt_employee empty”, одновременно знакомясь с API Django-MPTT:

(venv) $ python manage.py shell
Python 3.6.2 (default, Jul 17 2017, 16:44:45) 
(InteractiveConsole)
>>> from hrmgmt.models import EmployeeMptt
>>> jane_doe = EmployeeMptt.objects.create(first_name='Jane', last_name='Doe', role=EmployeeMptt.PRESIDENT)
>>> john_doe = EmployeeMptt.objects.create(first_name='John', last_name='Doe', role=EmployeeMptt.MANAGER, parent=jane_doe)
>>> joe_schmo = EmployeeMptt.objects.create(first_name='Joe', last_name='Schmo', role=EmployeeMptt.STANDARD, parent=john_doe)
>>> john_brown = EmployeeMptt.objects.create(first_name='John', last_name='Brown', role=EmployeeMptt.STANDARD, parent=john_doe)
>>> adam_smith = EmployeeMptt.objects.create(first_name='Adam', last_name='Smith', role=EmployeeMptt.MANAGER, parent=jane_doe)
>>> milt_friedman = EmployeeMptt.objects.create(first_name='Milt', last_name='Friedman', role=EmployeeMptt.STANDARD, parent=adam_smith)

Не слишком сложно, правда? Пока единственное, что имеет отношение к API Django-MPTT, – это использование поля parent . Это необходимо для того, чтобы библиотека Django-MPTT аннотировала записи соответствующими полями lft, rght, tree_id и level, что приводит к таблице с именем “hrmgmt_employeemptt”, заполненной следующим образом.

htmgmt_employeemptt

Теперь давайте немного оценим эту прекрасную библиотеку, играя с замечательными полезными методами, которые может предложить Django-MPTT.

Скажем, мы хотим получить список сотрудников, которые непосредственно подчиняются президенту Джейн Доу (то есть Джону Доу и Адаму Смиту), корневому узлу дерева MPTT.

>>> jane_doe.get_children()
, ]>

Ладно, пока что ничего особенного, верно? Это в основном дало нам тот же результат, что и наш предыдущий jane\_doe.employee.all () , и мы уже установили, что это имеет в основном ту же производительность, что и реализация смежного списка. Однако, скажем, я хотел, чтобы все сотрудники были ниже в компании, по сравнению с Джейн Доу:

>>> jane_doe.get_descendants()
, , , , ]>

Ну, это было довольно ловко, поскольку мы получили все это за одну поездку в базу данных.

Что-то еще, что может быть интересно, – это видеть всех сотрудников на одном уровне с другими, скажем, Джоном Брауном:

>>> john_brown.get_siblings()
]>

Теперь мы рассмотрим кое-что более интересное. Давайте посмотрим, можем ли мы перечислить сотрудников, которые находятся выше Джона Брауна, поэтому мы в основном поднимаемся по иерархии управления, которую я уже описывал ранее как нечто дорогостоящее (с точки зрения поездок в базу данных), но также неизбежно требующее какой-то циклической конструкции.

>>> john_brown.get_ancestors()
, ]>

Довольно просто, правда? И опять же, только одна поездка в базу данных.

Другие служебные методы, предоставляемые Django-MPTT, довольно просты с интуитивно понятными именами. Я приглашаю вас продолжить изучение других полезных методов в официальной документации .

Компромиссы между Соседним списком и MPTT

Как и в случае со многими задачами, стоящими перед разработчиками программного обеспечения, нам часто приходится принимать важные решения в отношении стратегии реализации. В первой статье о рекурсивных связях с Django я продемонстрировал метод реализации, известный как “смежный список”. В то время как в этой последующей статье я представил еще один метод реализации, известный как “Модифицированный обход дерева предварительных заказов (MPTT)”. Оба удовлетворяют основным требованиям для нашего варианта использования. Итак, когда вы сталкиваетесь с задачей программирования, которая по своей сути является рекурсивной, как в случае использования, демонстрируемом здесь, что вы должны выбрать?

Метод смежного списка относительно прост в рассуждении и взаимодействии с точки зрения кодирования с помощью Django, а также с использованием необработанного SQL и процедурного программирования. Однако, критически глядя на уровень базы данных (регулярные SELECT запросы), это, как правило, немного повторяется и дорого обходится при многих обращениях к базе данных.

С другой стороны, MPTT-это немного более сложная реализация в своей теоретической перспективе, но благодаря Django-MPTT у нас есть хороший уровень абстракции, чтобы освободить нас от необходимости думать в терминах древовидных структур данных. Мы ясно видели, что извлечение данных из таблицы базы данных, реализующей структуру MPTT, значительно более эффективно, чем метод смежного списка.

Тем не менее, есть один важный gotcha , о котором нужно знать и учитывать, прежде чем вы продолжите внедрять MPTT во все ваши приложения Django:

MPTT лучше всего подходит для случаев использования, когда у вас есть относительно статические иерархические данные, к которым часто обращаются через ВЫБИРАТЬ заявления.

Обновление записей в структурированной таблице MPTT стоит дорого, потому что вам приходится менять левое и правое значения почти каждой записи, но это также довольно сложный процесс. К счастью, Django-MPTT поставляется с некоторыми хорошими методами, которые заботятся о сложности, но это не облегчает проблему необходимости обновлять почти все значения слева, справа и уровня записи.

Подводя итог, я предлагаю реализовать смежный список в тех случаях, когда вы ожидаете, что данные будут обновляться получасто или чаще, и вытащить Django-MPTT, когда данные, как ожидается, останутся довольно статичными, чтобы вы могли наслаждаться большим повышением производительности поиска.

Я надеюсь, что вам понравилась эта статья, и, как всегда, пожалуйста, не стесняйтесь комментировать или критиковать ее там, где это необходимо.