Вступление

Эта статья является расширением предыдущей статьи, озаглавленной « Отношения рекурсивных моделей в 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

1 Джейн Лань PRES
2 Джон Лань MGR 1 3 Джо Schmo ЗППП 2 4 Джон коричневый ЗППП 2 5 Адам Смит MGR 1 6 Milt Фридман ЗППП 5

Глядя на приведенную выше таблицу сотрудников, вы можете определить иерархический характер данных. Например, вы можете сказать, что Джейн Доу является президентом (верхняя часть иерархии), потому что ее запись 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 выдает запрос, аналогичный приведенному ниже, чтобы получить сотрудников непосредственно под Jane Doe, когда employee вызывается в экземпляре класса Employee

 SELECT * FROM htmgmt_employee WHERE manager_id = 1 

я бы имя Фамилия роль manager_id

1 Джон Лань MGR 1 5 Адам Смит MGR 1

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

 SELECT * FROM hrmgmt_employee WHERE manager_id = 2 

я бы имя Фамилия роль manager_id

3 Джо Schmo ЗППП 2 4 Джон коричневый ЗППП 2

Таким образом, мы можем определить иерархию компании, начиная с верхушки (Джейн Доу) и продвигаясь вниз по цепочке отчетности. Однако для каждого нового менеджера, которого вы определяете, вам снова придется вызывать employee и 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'; 

я бы имя Фамилия роль manager_id

4 Джон коричневый ЗППП 2

Â

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

я бы имя Фамилия роль manager_id

2 Джон Лань MGR 1

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

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

я бы имя Фамилия роль manager_id

1 Джейн Лань PRES НОЛЬ

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

Измененный обход дерева предварительного заказа

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

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

{.ezlazyload .img-responsive}

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

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

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

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

employee_mptt

я бы имя Фамилия роль manager_id lft rgt

1 Джейн Лань PRES 1 12 2 Джон Лань MGR 1 2 7 3 Джо Schmo ЗППП 2 3 4 4 Джон коричневый ЗППП 2 5 6 5 Адам Смит MGR 1 8 11 6 Milt Фридман ЗППП 5 9 10

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

Используя приведенную выше таблицу со структурой MPTT, вы можете перечислить сотрудников, которые подчиняются менеджеру Джону Доу, используя следующий запрос 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; 

я бы имя Фамилия роль manager_id lft rgt

2 Джон Лань MGR 1 2 7 1 Джейн Лань PRES 1 12

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

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

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

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

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

Джанго-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 "<EmployeeMptt: {} {}>".format(self.first_name, self.last_name) 
 
 def __repr__(self): 
 return self.__str__() 

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

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

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

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

• get_ancestors (ascending = False, include_self = 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 = Ложь)
• insert_at (target, position = 'first-child', save = False)
• is_child_node ()
• is_leaf_node ()
• is_root_node ()
• move_to (цель, позиция = 'первый ребенок')

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

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

 (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 для заполнения новой таблицы "hrmgmt_employeemptt", одновременно знакомясь с Django-MPTT API:

 (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) 

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

htmgmt_employeemptt

я бы имя Фамилия роль lft прямо tree_id уровень parent_id

1 Джейн Лань PRES 1 12 1 0 НОЛЬ 2 Джон Лань MGR 2 7 1 1 1 3 Джо Schmo ЗППП 3 4 1 2 2 4 Джон коричневый ЗППП 5 6 1 2 2 5 Адам Смит MGR 8 11 1 1 1 6 Milt Фридман ЗППП 9 10 1 2 5

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

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

 >>> jane_doe.get_children() 
 <TreeQuerySet [<EmployeeMptt: John Doe>, <EmployeeMptt: Adam Smith>]> 

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

 >>> jane_doe.get_descendants() 
 <TreeQuerySet [<EmployeeMptt: John Doe>, <EmployeeMptt: Joe Schmo>, <EmployeeMptt: John Brown>, <EmployeeMptt: Adam Smith>, <EmployeeMptt: Milt Friedman>]> 

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

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

 >>> john_brown.get_siblings() 
 <TreeQuerySet [<EmployeeMptt: Joe Schmo>]> 

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

 >>> john_brown.get_ancestors() 
 <TreeQuerySet [<EmployeeMptt: Jane Doe>, <EmployeeMptt: John Doe>]> 

Довольно просто, правда? И снова только одно посещение базы.

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

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

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

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

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

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

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

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

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

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