CosmoCode
  • Great software.

  • Bright people.

  • Happy customers!

CosmoCode GmbH
  • Start
  • Geschäftsfelder
  • Über uns
  • Referenzen
  • Blog
  • Open Source
←
Alle Blogposts
→

Effiziente Baumstrukturen mit dem Django-MPTT Tree Traversal Algorithmus

Effiziente Baumstrukturen mit dem Django-MPTT Tree  Traversal Algorithmus

Wie verwaltet man Baumstrukturen in Django, so dass dynamische Such- und Auswertungsoperationen effizient durchgeführt werden können? Genau vor diesem Problem haben wir in einem akuellen Projekt gestanden, und für dieses Problem haben wir mit MPTT - Modified Preorder Tree Traversal - eine gute Lösung gefunden.

Detlef Hüttemann, 12.02.2015 09:00

Zugehörige Dienstleistungen:
  • Python/ Django

Bei einem aktuellen Projekt haben wir eine interessante Fragestellung, die einem eigentlich immer bei hierarchischen Strukturen begegnet. Konkret geht es darum, numerische Daten zu hierarchisch organisierten Orten zu aggregieren (Summenbildung). Beispiel: Werte zu Städten sollen hierarchisch aggregiert (∑-Bildung) werden:

  • Europa (∑ 11.000 - zu berechnen)
    • Deutschland (∑ 10.000 - zu berechnen)
      • Berlin (5.000)
      • München (3.000)
      • Hamburg (2.000)
    • Frankreich (∑ 1.000 - zu berechnen)
      • Paris (1.000)
  • Asien (…)
    • China (…)
      • Peking (2.000)

In unserem Projekt haben wir die Daten zu den Blättern, und müssen Auswertungen über diese Daten an der Knoten resp. an der Wurzel berechnen. Stellen wir uns also folgende Aufgabe: das Summieren aller Nachfahren von Europa. Dazu müssten zunächst alle Kinder von Europa selektiert werden und anschließend alle Kinder dieser Kinder. Schon an der Formulierung wird deutlich: hierbei handelt es sich um ein rekursives Problem. Solch ein Problem lässt sich mittels SQL allerdings weder leicht noch effizient lösen. Wir müssen unsere Entitäten also um weitere Attribute ergänzen, die eine solche Selektion effizienter machen.

Für die Umsetzung des Projekts haben wir auf das in python geschriebene WebFramework django1) gesetzt. Hierzu existiert eine Erweiterung, die sich django-mptt2) nennt. MPTT steht für Modified Preorder Tree Traversal, auch als Nested Sets bekannt. Diese Technik ermöglicht es Pfade oder Teilbäume innerhalb eines Baumes effizient auszulesen. Der Nachteil ist, dass Modifikationen an den Bäumen teuer sind; d.h. wir erkaufen uns effiziente Lesezugriffe durch aufwändige Schreibzugriffe. Für Anwendungen, bei denen sich die Bäume häufig ändern, kann das zu einem Problem werden; unser Use-Case sieht das zum Glück nicht vor.

Wie arbeitet diese Erweiterung nun im Detail? Theoretisch braucht man für eine Baumstruktur nur ein parent-Attribut, dass an allen Knoten hängt. So ist dies auch bei mptt, wobei mptt dieses um die folgenden Attribute erweitert: tree id, right und left.

Alle Entitäten, die die gleiche Wurzel haben, erhalten die gleiche tree id. Im Prinzip bedeutet das, alle Nachfahren einer Entität, deren parent-Attribut nicht gesetzt ist, gehören zu einem Baum. Diese Entität ist somit Wurzel. Im obigen Beispiel wären das Europa und Asien. Die beiden weiteren Attribute sind etwas schwieriger zu verstehen. Um diese Werte zu ermitteln wird ein, der Tiefensuche ähnlicher, Algorithmus verwendet. Dazu schauen wir uns noch einmal die Grafik dieses Beitrages an: 



Die Vergabe der left- und right Attribute funktioniert so: Der Algorithmus durchläuft alle Knoten im Baum beginnend bei der Wurzel und führt dabei einen Zähler mit. Beim betreten eines Knotens wird der left-Wert auf den aktuellen Zählerwert gesetzt und der Zähler erhöht. Hat der Knoten Kinder so werden diese nun durchlaufen. Sind alle Kinder eines Knotens durchlaufen oder hat der Knoten keine Kinder wird er wieder verlassen. Beim Verlassen des Knotens wird der right-Wert wiederum auf den aktuellen Zählerstand gesetzt und dieser anschließend inkrementiert. Dies wird fortgeführt bis alle Knoten besucht wurden und wieder die Wurzel erreicht ist.

Wenn wir uns nun die Zahlen betrachten stellen wir folgendes fest:

  • der left-Wert eines Knotens ist immer größer als der seiner Vorgänger
  • der right-Wert ist immer kleiner als der seiner Vorgänger

Welche Queries lassen sich mit diesem Wissen realisieren? (Jeder Query der sich auf die Baum-Attribute bezieht ist immer im Context einer tree id. Diese muss also in jeden Query aufgenommen werden und wird hier der Einfachheit halber nicht mit aufgeführt.):

  • alle Nachfahren von this: left > this.left and right < this.right
  • alle Vorfahren von this: left < this.left and right > this.right

Außerdem gibt es natürlich auch die trivialen Queries:

  • alle Kinder von this: parent = this
  • alle Geschwister von this: parent = this.parent

Hier nun ein Beispiel eines Selects, der der Aufgabenstellung entspricht, also die Summe über die Werte alle Nachfahren.

SELECT SUM(`value`.`amount`)
FROM `node` AS `parent`
  JOIN `node` AS `descendant`
    ON (`descendant`.`tree_id` = `parent`.`tree_id`
    AND `descendant`.`left` > `parent`.`left`
    AND `descendant`.`right` < `parent`.`right`)
  JOIN `value`
    ON (`value`.`node_id` = `descendant`.`id`)
WHERE `parent`.`name` = 'Europa'

Wollen wir alle Knoten in der Reihenfolge ausgeben, in der sie oben gezeigt ist, müssen wir nur nach tree id und left sortieren. Wichtig ist, dass alle Baum-Attribute von der Datenbank indiziert werden, da sie bei jedem Query benötigt werden.

In unserem Projekt ist das ganze natürlich etwas komplizierter als hier beschrieben - so sind die Teilbäume dynamsich (abhängig von Filterregeln); und Daten können auch in Zwischenebenen existieren.

Quellen

  • http://de.wikipedia.org/wiki/Nested_Sets
  • http://django-mptt.github.io/django-mptt/overview.html#what-is-modified-preorder-tree-traversal
  • http://www.klempert.de/nested_sets/
1) https://www.djangoproject.com/
2) http://django-mptt.github.io/django-mptt/

Mehr zum Thema

  • CosmoCode entwickelt Speziallösung zur Archivierung von Social Media Plattformen
  • CosmoCodes neue Webseite ist fertig!
  • eLearning Portal für Continental
  • Digitale Gastronomie am Hackeschen Markt - DataKitchen
  • Python/Django basierte Medienverwaltungs-Infrastruktur
  • Automatisierung von Excel Berechnungen unter Linux mit Apache POI

Kontakt

Wir freuen uns sehr über Ihr Interesse!
Sie erreichen uns hier:

CosmoCode GmbH

Prenzlauer Allee 36G
10405 Berlin

Telefon: +49 30 814 50 40 70

Telefax: +49 30 2809 7093


mail: info@cosmocode.de

CosmoCode GmbH  
   

© CosmoCode 2021 | Impressum | Datenschutz | Cookies verwalten

Schließen
Deutsch Englisch
  • Jobs