Traves铆a de 谩rbol de preorden modificada en Django

    Introducci贸n

    Este art铆culo es una extensi贸n de un art铆culo anterior titulado Relaciones recursivas de modelos en Django, que demostr贸 una forma de utilizar las capacidades b谩sicas de Django para definir Clases respaldadas por bases de datos que modelan un caso de uso com煤n para una relaci贸n recursiva. El caso de uso que pretendo satisfacer es la relaci贸n com煤n entre empleados y gerentes de empleados, que tambi茅n son empleados.

    Evaluaci贸n de la implementaci贸n previa

    El art铆culo anterior defini贸 una Employeeclase que se traduce en una tabla de base de datos de la estructura “employee (id, first_name, last_name, role, manager_id)” donde manager_id es una clave externa que hace referencia a la identificaci贸n del empleado que representa al gerente del empleado actual. Este tipo de implementaci贸n de almacenamiento de datos recursivos en una base de datos se conoce como m茅todo de lista adyacente .

    Para dejar esto m谩s claro, el conjunto de resultados a continuaci贸n enumera los empleados de una empresa ficticia, que se enumera en orden jer谩rquico desde el presidente en la parte superior, luego dos gerentes y los empleados que administran debajo de ellos.

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

    Tabla de empleados

    idfirst_namelast_namerolemanager_id

    1JaneHacerPRES
    2JohnHacerMONSE脩OR1
    3JoeSchmoHORAS2
    4Johnmarr贸nHORAS2
    5Ad谩nHerreroMONSE脩OR1
    6LechaFriedmanHORAS5

    Si observa la tabla de empleados que se muestra arriba, puede identificar la naturaleza jer谩rquica de los datos. Por ejemplo, puede saber que Jane Doe es la presidenta (la parte superior de la jerarqu铆a) porque su entrada manager_id est谩 vac铆a y tambi茅n puede saber que dos empleados le reportan, John Doe y Adam Smith, porque sus entradas manager_id son iguales a las de Jane ID de empleado de 1.

    A continuaci贸n, demuestro el uso de una instancia de la Employeeclase del art铆culo anterior, que representa a Jane Doe, para recuperar a los empleados que dependen directamente de ella.

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

    Bajo el cap贸, Django ORM emite una consulta similar a la siguiente para obtener a los empleados directamente debajo de Jane Doe cuando employeese llama a la propiedad en una instancia de la Employeeclase.

    SELECT * FROM htmgmt_employee WHERE manager_id = 1  
    

    idfirst_namelast_namerolemanager_id

    1JohnHacerMONSE脩OR1
    5Ad谩nHerreroMONSE脩OR1

    De manera similar, para obtener los empleados que informan a John Doe, llamar铆a al employeecampo de relaci贸n en una Employeeinstancia de clase que representa a John Doe, y bajo el cap贸, el ORM emitir铆a una consulta similar a esta:

    SELECT * FROM hrmgmt_employee WHERE manager_id = 2
    

    idfirst_namelast_namerolemanager_id

    3JoeSchmoHORAS2
    4Johnmarr贸nHORAS2

    De esta manera podemos identificar la jerarqu铆a de la empresa comenzando con la parte superior (Jane Doe) y avanzando hacia abajo en la cadena de informes. Sin embargo, por cada nuevo gerente que identifique, tendr谩 que volver a llamar a la employeepropiedad de relaci贸n y el ORM de Django emitir谩 otra consulta para recuperar el nuevo conjunto de empleados que informan al gerente anterior.

    Si bien este enfoque ciertamente funcionar谩, proporcionando la informaci贸n que deseamos cuando queremos caminar hacia abajo en la lista de la empresa, existe una preocupaci贸n por el rendimiento. Cada nuevo nivel de gesti贸n que encontramos requiere un viaje m谩s a la base de datos, y estas consultas se acumulan, consumiendo cada vez m谩s recursos, lo que lleva a tiempos de espera m谩s largos para el cliente que llama al programa. Los usuarios se enojar谩n r谩pidamente mientras miran la rueda giratoria de la paciencia en la pesta帽a del navegador.

    El mismo problema ocurre cuando intentamos subir la lista de empleados desde un empleado regular hasta los niveles de administraci贸n y terminando con el presidente. Por ejemplo, considere cu谩ndo desea determinar la l铆nea ascendente de gesti贸n a partir de John Brown.

    Identificar铆a el ID de gerente de John Brown, que es 2, luego realizar铆a una llamada a la base de datos para determinar el gerente del empleado con un ID de 2.

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

    idfirst_namelast_namerolemanager_id

    4Johnmarr贸nHORAS2
    /* Get the employee with id of 2 */
    SELECT * FROM htmgmt_employee WHERE id = 2;
    

    idfirst_namelast_namerolemanager_id

    2JohnHacerMONSE脩OR1

    Esto devuelve John Doe, el gerente de John Brown, y vemos que su manager_id es 1, lo que indica que hay al menos un nivel m谩s de administraci贸n por encima de 茅l. Una vez m谩s, emitimos otra consulta para determinar si el empleado con ID de 1 se encuentra en la parte superior de la jerarqu铆a de gesti贸n o si existe otro nivel de gesti贸n.

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

    idfirst_namelast_namerolemanager_id

    1JaneHacerPRESNULO

    Solo ahora, despu茅s de realizar varios viajes a la base de datos, puede determinar la jerarqu铆a de gesti贸n. En una empresa mucho m谩s grande, este m茅todo claramente tendr谩 algunos problemas de escala.

    Desplazamiento del 谩rbol de pedidos anticipados modificado

    Afortunadamente, existe otro m茅todo para almacenar y recuperar datos jer谩rquicos en una base de datos conocido como Modified Preorder Tree Traversal (MPTT). Esta segunda forma utiliza una estructura de datos similar a un 谩rbol para modelar los datos, junto con un etiquetado intuitivo de los nodes asociados del 谩rbol, lo que permite el desplazamiento basado en las etiquetas.

    A continuaci贸n se muestra una representaci贸n en 谩rbol de los datos de la tabla de listado de empleados anterior.

    El esquema de etiquetado comienza colocando un 1 a la izquierda del node ra铆z, presidenta Jane Doe en este ejemplo, luego baja un node a la izquierda de la ra铆z. En este node inmediatamente debajo ya la izquierda, incremente el recuento y etiquete este nuevo node con un 2. Este proceso contin煤a hasta el node secundario m谩s bajo (hoja), Joe Schmo en este ejemplo. Luego, etiqueta el lado derecho del node secundario con el siguiente incremento y se mueve lateralmente a trav茅s de los hermanos hacia la derecha etiquetando los lados izquierdo y derecho, increment谩ndose a medida que avanza.

    Una vez que llegas al borde del sub谩rbol, John Brown, atraviesas el 谩rbol hasta llegar a un nivel que tiene hermanos, luego te mueves de nuevo lateralmente y retrocedes por el 谩rbol, similar al sub谩rbol anterior encontrado hasta llegar a la ra铆z nuevamente.

    Lo siguiente que debe hacer es traducir este 谩rbol anidado en una estructura de tabla plana. Esto se logra mediante la definici贸n de dos columnas adicionales de valores “izquierda” y “derecha”. Sin embargo, dado que izquierda y derecha son palabras clave reservadas en el lenguaje SQL, las implementaciones reales utilizan abreviaturas, como “lft” y “rgt”.

    A continuaci贸n se muestra una tabla de ejemplo de una implementaci贸n m铆nima de una tabla estructurada MPTT para la lista de empleados.

    empleado_mptt

    idfirst_namelast_namerolemanager_idlftrgt

    1JaneHacerPRES112
    2JohnHacerMONSE脩OR127
    3JoeSchmoHORAS234
    4Johnmarr贸nHORAS256
    5Ad谩nHerreroMONSE脩OR1811
    6LechaFriedmanHORAS5910

    Ahora que los datos est谩n organizados y anotados con los valores en las columnas lft y rgt, hemos ganado m谩s flexibilidad, control y eficiencia en la forma en que recuperamos los datos.

    Con la tabla estructurada de MPTT anterior, puede enumerar los empleados que dependen del gerente John Doe mediante la siguiente consulta SQL.

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

    Sin embargo, para demostrar la eficiencia de la estructura MPTT, volver茅 a rastrear la adhesi贸n de la administraci贸n a partir de John Brown. Puedo lograr esto incluyendo algunos predicados en la secci贸n DONDE de la consulta, especificando que lft sea menor que 6 y rgt sea mayor que 6 y luego ORDER-ing by rgt enumerar谩 la jerarqu铆a de administraci贸n en orden ascendente, todo en un viaje a la base de datos.

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

    idfirst_namelast_namerolemanager_idlftrgt

    2JohnHacerMONSE脩OR127
    1JaneHacerPRES112

    Anotar los registros de los empleados con las columnas lft y rgt de acuerdo con la estructura MPTT nos proporciona una forma mejorada de atravesar los datos y obtener informaci贸n 煤til con menos interacciones con la base de datos y m谩s eficientes. Por ejemplo, si quisi茅ramos saber cu谩ntos empleados hay debajo de John Doe en la estructura, asumiendo que ya tenemos la informaci贸n de John, podemos aplicar esta f贸rmula simple:

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

    Conectando los valores rgt y lft de John, obtenemos:

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

    Esto nos proporciona la respuesta y no requiri贸 ninguna interacci贸n adicional con la base de datos.

    Django-mptt

    La incre铆ble comunidad que usa y desarrolla el marco web Django ha producido el proyecto Django-MPTT que ampl铆a las funcionalidades b谩sicas de Django e implementa MPTT. El proyecto Django-MPTT ofrece una serie de comodidades que hacen que la interacci贸n con datos jer谩rquicos en la estructura MPTT sea muy conveniente al tiempo que se logran las eficiencias asociadas con la recuperaci贸n de datos MPTT.

    Implementar nuestra lista de empleados de datos jer谩rquicos usando Django-MPTT es bastante simple. Para demostrar esto, usar茅 el c贸digo existente de la discusi贸n del art铆culo anterior sobre el uso de Django para modelar relaciones recursivas entre empleados.

    Si desea seguir adelante, puede descargar el c贸digo de mi cuenta de GitHub aqu铆, comenzando por la etiqueta del comienzo de este tutorial llamado “mptt-start”.

    Abra su terminal de comando, cree un nuevo entorno virtual e instale los siguientes requisitos:

    (venv) $ pip install django django-mptt
    

    Despu茅s de ejecutar las migraciones iniciales como se describe en el art铆culo anterior, cargue el proyecto en su entorno de desarrollo integrado favorito o editor de texto y abra el script Python del modelo en el directorio “hrmgmt” y agregue el siguiente c贸digo.

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

    La primera declaraci贸n nueva agrega importaciones para las clases MPTTModely TreeForeignKeyde la biblioteca django-mptt. Entonces EmployeeMpttse define la clase.

    Los EmployeeMptthereda de la clase de la MPTTModelque a帽ade los campos de clase lft, rght, level, y tree_ida la subclase ( EmployeeMptt). Los campos funcionan de la siguiente manera:

    • lft: un campo entero como se describe en la secci贸n anterior
    • rght: un campo entero como se describe en la secci贸n anterior
    • level: un campo entero que indica el nivel de jerarqu铆a de cada instancia
    • tree_id: un campo entero similar al Employeecampo de clase del art铆culo anterior manager_id

    Sin embargo, una caracter铆stica m谩s 煤til que resulta de heredar MPTTModelson los m茅todos que la acompa帽an, que abstraen la implementaci贸n de los campos antes mencionados y proporcionan las funcionalidades preferidas para trabajar con la estructura de 谩rbol.

    • get_ancestors (ascendente = Falso, 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 = False)
    • insert_at (objetivo, posici贸n = ‘primer hijo’, guardar = Falso)
    • is_child_node ()
    • is_leaf_node ()
    • is_root_node ()
    • move_to (objetivo, posici贸n = ‘primer hijo’)

    El TreeForeignKeycampo se comporta esencialmente de la misma manera que el normal, django.db.models.ForeignKeypero tambi茅n muestra las opciones de la jerarqu铆a de un 谩rbol con anidaci贸n en formas Django.

    Ahora que hemos escrito el c贸digo para definir el EmployeeMptt, traduzcamos el c贸digo del modelo en tablas de base de datos de acuerdo con la estructura MPTT. En su terminal, haga y ejecute una migraci贸n para la EmployeeMpttclase:

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

    Inspeccione el SQL DDL que se emitir谩:

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

    Ejecute la migraci贸n:

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

    Ahora utilice el shell de Django para completar la nueva tabla “hrmgmt_employeemptt” mientras se familiariza simult谩neamente con la API de 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)
    

    No es demasiado complicado, 驴verdad? Hasta ahora, lo 煤nico que es relevante para la API Django-MPTT es el uso del parentcampo. Esto es necesario para que la biblioteca Django-MPTT anote los registros con los campos lft, rght, tree_id y level apropiados, lo que lleva a una tabla llamada “hrmgmt_employeemptt”, que se completa de la siguiente manera.

    htmgmt_employeemptt

    idfirst_namelast_namerolelftrghttree_idlevelparent_id

    1JaneHacerPRES11210NULO
    2JohnHacerMONSE脩OR27111
    3JoeSchmoHORAS34122
    4Johnmarr贸nHORAS56122
    5Ad谩nHerreroMONSE脩OR811111
    6LechaFriedmanHORAS910125

    Ahora ganemos un poco de apreciaci贸n por esta excelente biblioteca jugando con los excelentes m茅todos de utilidad que Django-MPTT tiene para ofrecer.

    Supongamos que queremos obtener una lista de los empleados que dependen directamente de la presidenta Jane Doe (es decir, John Doe y Adam Smith), el node ra铆z del 谩rbol MPTT.

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

    Ok, hasta ahora no es muy especial, 驴verdad? Esto b谩sicamente nos dio el mismo resultado que el anterior jane_doe.employee.all()y ya establecimos que tiene b谩sicamente el mismo rendimiento que la implementaci贸n de la lista adyacente. Sin embargo, digamos que quer铆a que todos los empleados fueran m谩s bajos en la empresa, en relaci贸n con Jane Doe:

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

    Bueno, eso fue bastante h谩bil, ya que obtuvimos todo eso en un solo viaje a la base de datos.

    Otra cosa que podr铆a ser interesante ser铆a ver a todos los empleados en el mismo nivel que otro, dice John Brown:

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

    Ahora echaremos un vistazo a algo un poco m谩s interesante. Veamos si podemos enumerar los empleados que est谩n por encima de John Brown, por lo que b谩sicamente estamos ascendiendo en la jerarqu铆a de gesti贸n, lo que ya describ铆 antes como algo que es caro (en t茅rminos de viajes a la base de datos) pero que tambi茅n inevitablemente requerir铆a una especie de construcci贸n en bucle.

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

    Bastante simple, 驴verdad? Y nuevamente, solo un viaje a la base de datos.

    Los otros m茅todos de utilidad proporcionados por Django-MPTT son bastante sencillos con nombres intuitivos. Los invito a investigar m谩s a fondo los otros m茅todos de utilidad en la documentaci贸n oficial .

    Compensaci贸n entre la lista adyacente y MPTT

    Como es el caso de muchas tareas que enfrentan los desarrolladores de software, a menudo necesitamos tomar decisiones importantes con respecto a la estrategia de implementaci贸n. En el primer art铆culo sobre relaciones recursivas con Django, demostr茅 un m茅todo de implementaci贸n conocido como “lista adyacente”. Mientras que en este art铆culo de seguimiento present茅 otro m茅todo de implementaci贸n, conocido como “Modified Preorder Tree Traversal (MPTT)”. Ambos satisfacen los requisitos b谩sicos para nuestro caso de uso. Entonces, cuando se enfrenta a una tarea de programaci贸n que es inherentemente recursiva, como en el caso de uso que se demuestra aqu铆, 驴cu谩l deber铆a elegir?

    El m茅todo de lista adyacente es relativamente sencillo para razonar e interactuar desde una perspectiva de codificaci贸n con Django, as铆 como tambi茅n mediante el uso de SQL sin formato y programaci贸n de procedimientos. Sin embargo, mirando cr铆ticamente al nivel de la base de datos ( SELECTconsultas regulares ), esto tiende a ser un poco repetitivo y costoso con muchos viajes a la base de datos.

    Por otro lado, MPTT es una implementaci贸n un poco m谩s elaborada en su perspectiva te贸rica, pero gracias a Django-MPTT tenemos una buena capa de abstracci贸n para liberarnos de la necesidad de pensar en t茅rminos de estructuras de datos de 谩rbol. Hemos visto claramente que recuperar datos de una tabla de base de datos que implementa la estructura MPTT tiene un rendimiento significativamente mayor que el m茅todo de lista adyacente.

    Sin embargo, hay un problema importante que debe tener en cuenta y considerar antes de continuar implementando MPTT en todas sus aplicaciones de Django:

    MPTT es m谩s adecuado para casos de uso en los que tiene datos jer谩rquicos relativamente est谩ticos a los que se accede con frecuencia a trav茅s de SELECTdeclaraciones.

    Actualizar las entradas en una tabla estructurada MPTT es caro porque tiene que cambiar los valores izquierdo y derecho de casi todas las entradas, pero tambi茅n es un proceso bastante complejo. Afortunadamente, Django-MPTT viene con algunos m茅todos agradables que se encargan de la complejidad, pero esto no alivia el problema de tener que actualizar los valores de nivel, derecho e izquierdo de casi todas las entradas.

    Para resumir, sugiero implementar la lista adyacente en los casos en los que espere que los datos se actualicen con frecuencia o m谩s y sacar Django-MPTT cuando se espera que los datos permanezcan bastante est谩ticos para que pueda disfrutar de los grandes aumentos de rendimiento de recuperaci贸n.

    Espero que haya disfrutado del art铆culo y, como siempre, no dude en comentar o criticar cuando sea necesario.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *