Yii2 Festgelegtes Verhalten zum Speichern und Freigeben von Bäumen in der Datenbank


    Hallo habr

    In einem meiner Yii2-Projekte wollte ich die Adjacency List und die Nested Sets kombinieren. Und damit im Falle der Deaktivierung des Verhaltens von verschachtelten Sätzen die Funktionalität voll funktionsfähig bleibt. Dann wurde mir klar, dass ich keine verschachtelten Sets benötigte, da ich immer noch den vollständigen Pfad in der Datenbank speichern musste. Daher entschied ich mich, den materialisierten Pfad als Ersatz zu verwenden. Das auf GitHub verfügbare Verhalten ( matperez / yii2-materialized-path ) war nicht funktionsfähig genug, sodass ich mein eigenes schreiben musste und seit kurzem mein eigenes Verhalten für die Adjacency-Liste und die verschachtelten Intervalle schriebIch entschied, warum nicht eine Reihe solcher Verhalten mit einer einzigen API und der Möglichkeit, sie gleichzeitig willkürlich mit dem Modell zu verbinden, unter Ausnutzung der jeweiligen Vorteile, zu erstellen.


    Verhaltensliste


    Angrenzungsliste


    + Selbsttragende Integritätsstruktur
    + Schnelle Änderungen, da keine Nachzählungen und Aktualisierungen von Nachkommen erforderlich sind
    + Schneller Empfang von unmittelbaren Eltern und Kindern
    - Die Komplexität und Langsamkeit des Empfangs aller Vorfahren und Nachkommen

    Die einfachste Form der Kommunikation, in den meisten Fällen verbinden sie kein Verhalten. Sie schreiben lediglich Beziehungen zu Eltern und Kindern vor. Es lohnt sich jedoch, die Adjacency-Liste durch ein Sortierfeld für Knoten ( insertBefore()/ insertAfter()) zu ergänzen , da dies ohne vorgefertigtes Verhalten schwierig wird. Ja, und alle Vorfahren / Nachkommen einer Beziehung zu bekommen, ist schon schwierig.
    All diese Probleme werden durch Verhalten gelöst. Darüber hinaus hat es einige Chips - es ermöglicht Ihnen, eine benutzerdefinierte Anzahl von Verknüpfungen der Tabelle mit sich selbst zu erstellen, um Anforderungen für Vorfahren / Nachkommen zu reduzieren und zu beschleunigen.
    Schau auf Github

    Materialisierter Pfad


    Die Technik zum Speichern des vollständigen Pfads in jedem Element (genau wie der Pfad im Dateisystem).
    + schnelles Abrufen aller Vorfahren und Nachkommen
    + schnelles Einfügen neuer Elemente
    - nicht optimale Speicherung des Pfades, mögliche Längenbeschränkungen
    - im Allgemeinen ist ein zusätzliches Tiefenfeld erforderlich, um unmittelbare untergeordnete Elemente zu erhalten (bei Implementierungen für eine bestimmte Basis ist diese Anforderung nicht erforderlich)
    - beim Ändern des Pfades Element, Aktualisierung aller Nachkommen ist erforderlich.

    Welcher matperez / yii2-materialized-Pfad passte nicht zu mirAbgesehen von der Notwendigkeit einer einzigen API und dem Fehlen einiger Methoden? Zuallererst ist die Tatsache, dass das Aktualisieren von Kindern beim Ändern des Pfads PHP-rekursiv ist, was eine Reihe von Anfragen an die Datenbank erzeugt, was sehr schlecht ist. In dem von mir implementierten Verhalten wird dies mit einer Anfrage durchgeführt, obwohl ich einige Kompatibilität mit Datenbanken opfern musste - ich benötige Unterstützung für Funktionen CONCAT()und LENGTH()(in den meisten Datenbanken sind dies mysql, pqsql, mssql). Ein weiterer Vorteil - in meinem Verhalten gibt es zwei Möglichkeiten, den Pfad zu erstellen - ist der Primärschlüssel oder ein anderes Feld, das nicht unbedingt eindeutig ist.
    Schau auf Github

    Verschachtelte Mengen


    + schnelle Auswahl von Vorfahren, Nachkommen, benachbarten und leeren Knoten
    + sofortige Ermittlung der Anzahl der Nachkommen im Knoten
    + nicht rekursive Baumkonstruktion
    - sehr langsame Änderungen am Baum, insbesondere am Anfang großer Datenbanken (das Einfügen eines Elements kann in einer großen Datenbank problemlos länger als 30 Sekunden

    dauern ) Für Yii2 Es gibt bereits eine großartige Erweiterung von Creocoder , aber ich musste sie neu schreiben, um eine einzige API zu unterstützen, auf die weiter unten eingegangen wird. Diese API bietet mehrere Vorteile.
    Schau auf Github

    Verschachtelte Intervalle


    + schnelle Auswahl der Vorfahren, Nachkommen
    + nicht-rekursive Baumbildung
    + schnelles Einfügen abhängig von der Optimierung der Parameter
    - langsame Knotenbewegungen

    Dieser Algorithmus ist nicht sehr beliebt, obwohl er sehr schnell ist, wenn die richtigen Parameter ausgewählt werden. Weitere Informationen zu verschachtelten Intervallen finden Sie in diesem Artikel .
    Schau auf Github

    Einzelne API


    Alle oben genannten Verhalten weisen eine gemeinsame API auf, sodass sie ersetzt werden können, ohne dass Code neu geschrieben werden muss.
    Die API hat einen großen Vorteil - doppelten Zugriff auf verwandte Objekte über den Standard-Yii2-Relations-Mechanismus:
    $parent = $model->getParent()->orderBy(['title' => SORT_DESC])->one(); // если вызвать связь методом, вернёт ActiveQuery
    $title1 = $model->parent->title; // если вызвать свойством, вернёт сам объект
    $title2 = $model->parent->title . ' (2)'; // повторный вызов НЕ генерирует второй запрос к базе
    

    Es gibt eine Besonderheit - Methoden makeRoot(), prependTo(), appendTo(), insertBefore(), insertAfter()- produzieren nicht die Aktion selbst, sondern geben nur einen Hinweis auf ihren Typ, so dass Sie nach ihnen daran denken müssen, durchzuführen save():
    $node = new Node;
    $node->title = 'root';
    $node->makeRoot()->save();
    

    Dies geschieht, um Parameter nicht mitzuziehen save($runValidation = true, $attributeNames = null).

    Eigenschaft, mehrere Verhaltensweisen gleichzeitig zu verwenden


    Das Verhalten in Yii2 wird so implementiert, dass die erste Verhaltensmethode ausgeführt wird, in der es existiert. Um mehrere Verhalten gemeinsam zu nutzen, müssen Sie die baummodifizierenden Methoden für jedes verbundene Verhalten und für die Methoden, die aus der Datenbank die schnellste auswählen, aufrufen. Zu diesem Zweck wurde Trait geschrieben, das diese Funktionen ausführt. Gleichzeitig muss PhpDoc nicht mehr jedes Mal angegeben werden.
    Auf GitHub ansehen

    Beispiel:
    use paulzi\adjacencylist\AdjacencyListBehavior;
    use paulzi\nestedsets\NestedSetsBehavior;
    use paulzi\autotree\AutoTreeTrait;
    class Node extends \yii\db\ActiveRecord
    {
        use AutoTreeTrait;
        public function behaviors() {
            return [
                ['class' => AdjacencyListBehavior::className()],
                ['class' => NestedSetsBehavior::className()],
            ];
        }
    }
    

    Jetzt:
    $node->parents;     // будет использовать nested sets
    $node->parent;      // будет использовать adjacency list
    $node->children;    // будет использовать adjacency list
    $node->descendants; // будет использовать nested sets
    $node->insertAfter($node2)->save() // выполнится для двух поведений сразу
    

    Maximale effektive Kombinationen:
    Adjacency List + Materialized Path
    Adjacency List + Nested Sets
    Adjacency List + Nested Intervals

    Leistungsvergleich


    Aus der Tabelle ergibt sich meines Erachtens, welche Vor- und Nachteile die einzelnen Verhaltensweisen haben:
    Leistungstabelle
                                                    Speicherzeit für die Ausführung von DB-Abfragen
    Test 1. Füllstand 3 für 12 Kinder
        Angrenzungsliste 5811 1.567 ms 9.591 ms 71,3 MB
        Geschachtelte Sätze 7697 6.672 ms 25.019 ms 105.9 MB
        Verschachtelte Intervalle = 24 5813 1,765 ms 10,442 ms 78,7 MB
        Anzahl geschachtelter Intervalle = 12 noPrepend noIns. 5813 1.750 ms 10.223 ms 78,7 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 7696 3,169 ms 13,726 ms 92,5 MB
        Materialisierter Pfad (Attributmodus) 5811 1.690 ms 9.504 ms 71,6 MB
    Test 2. Füllstand 6 für 3 Kinder
        Angrenzungsliste 3642 982 ms 5,812 ms 44,5 MB
        Geschachtelte Sätze 4736 5.447 ms 17.859 ms 65.0 MB
        Verschachtelte Intervalle = 10 3644 1,275 ms 5,976 ms 48,9 MB
        Anzahl verschachtelter Intervalle = 3 noPrepend noIns. 3644 1.271 ms 5.993 ms 48,9 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 4735 1.316 ms 6.920 ms 57,3 MB
        Materialisierter Pfad (Attributmodus) 3642 1.129 ms 5.507 ms 44,6 MB
    Test 3. Am Anfang <4% einfügen (20 in 19657 Knoten)
        Angrenzungsliste 100 36 ms 190 ms 4,6 MB
        PaulZi 100 15.768 ms 16.712 ms 4.7 MB
        Verschachtelte Intervalle 82 21 ms 150 ms 4,7 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 120 98 ms 355 ms 4,8 MB
        Materialisierter Pfad (Attributmodus) 100 74 ms 334 ms 4,6 MB
    Test 4. In die Mitte einfügen> 46% <50% (20 in 19657 Knoten)
        Angrenzungsliste 100 24 ms 150 ms 4,6 MB
        Verschachtelte Mengen 100 8,212 ms 8,799 ms 4,7 MB
        Verschachtelte Intervalle 82 269 ms 593 ms 4,7 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 120 35 ms 196 ms 4,9 MB
        Materialisierter Pfad (Attributmodus) 100 287 ms 494 ms 4,6 MB
    Test 5. Am Ende> 96% einfügen (20 in 19657 Knoten)
        Adjacency List 100 31 ms 214 ms 4,5 MB
        Verschachtelte Sätze 100 487 ms 899 ms 4,7 MB
        Verschachtelte Intervalle 83 46 ms 187 ms 4,7 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 120 34 ms 229 ms 4,8 MB
        Materialisierter Pfad (Attributmodus) 100 470 ms 718 ms 4,6 MB
    Test 6. Löschung von Anfang an <4% (20 von 19657 Knoten)
        Adjacency List parentJoin = 0 childrenJoin = 0 60 169 ms 257 ms 3,8 MB
        Adjazenzliste parentJoin = 3 childrenJoin = 3 60 87 ms 162 ms 3,8 MB
        Verschachtelte Mengen 100 16.480 ms 16.902 ms 4,7 MB
        Verschachtelte Intervalle 60 164 ms 250 ms 4,2 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 60 87 ms 201 ms 4,0 MB
        Materialisierter Pfad (Attributmodus) 60 122 ms 219 ms 4,0 MB
    Test 7. appendTo () an einen zufälligen Knoten (5 Ebenen, 1000 Knoten)
        Angrenzungsliste 4001 1.062 ms 5.976 ms 46,1 MB
        Geschachtelte Sätze 5003 5.428 ms 17.334 ms 64,8 MB
        Verschachtelte Intervalle = 10 8497 23 301 ms 41 060 ms 120,7 MB
        Verschachtelte Intervalle x64 = 10 7092 11.330 ms 23.618 ms 97.5 MB
        Anzahl geschachtelter Intervalle = 200,25 noPrep noIns 4009 1,431 ms 6,490 ms 50,2 MB
        Verschachtelte Intervalle x64 a = 250,30 noPrep noIns 4003 1,421 ms 6,615 ms 50,0 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 5003 1.621 ms 8.184 ms 57,8 MB
        Materialisierter Pfad (Attributmodus) 4002 1,269 ms 6,169 ms 46,2 MB
    Test 8. Beliebige Operation in einem zufälligen Knoten (5 Ebenen, 1000 Knoten)
        Angrenzungsliste 4383 1.330 ms 6.147 ms 53.0 MB
        Geschachtelte Sätze 5003 9,577 ms 24,334 ms 64,8 MB
        Verschachtelte Intervalle = 10 7733 8,123 ms 24,031 ms 107,2 MB
        Geschachtelte Intervalle x64 Standardwert = 10 5663 3.761 ms 14.084 ms 75,6 MB
        Verschachtelte Intervalle = 200,25 4175 1,548 ms 7,223 ms 52,8 MB
        Verschachtelte Intervalle x64 a = 250,30 reserve = 2 4003 1,541 ms 6,753 ms 50,0 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 5392 3,211 ms 11,771 ms 65,0 MB
        Materialisierter Pfad (Attributmodus) 4377 2.902 ms 10.132 ms 53.2 MB
    Test 9. Bewegung der Knoten am Anfang <4% (20 von 19657 Knoten)
        Angrenzungsliste 112 39 ms 261 ms 4,5 MB
        Geschachtelte Mengen 140 218 ms 566 ms 5,5 MB
        Verschachtelte Intervalle 160 180 ms 573 ms 6,0 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 128 38 ms 307 ms 4,9 MB
        Materialisierter Pfad (Attributmodus) 128 159 ms 495 ms 4,9 MB
    Test 10. Verschieben von Knoten von Ende zu Anfang <4%> 96% (20 von 19657 Knoten)
        Verschachtelte Mengen 140 16.991 ms 17.845 ms 5,5 MB
        Verschachtelte Intervalle 160 16.972 ms 17.854 ms 6,0 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 132 49 ms 319 ms 4,9 MB
        Materialisierter Pfad (Attributmodus) 132 205 ms 502 ms 4,9 MB
        Angrenzungsliste 112 33 ms 217 ms 4,5 MB
    Test 11. Die Wahl aller Knoten (19657 Stk.)
        Angrenzungsliste 1 33 ms 890 ms 179,1 MB
        Verschachtelte Mengen 1 40 ms 1.208 ms 215,2 MB
        Verschachtelte Intervalle 1 42 ms 1.247 ms 225,3 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 1 46 ms 1.240 ms 209,0 MB
        Materialisierter Pfad (Attributmodus) 1 44 ms 1,106 ms 209,0 MB
    Test 12. Auswahl von Kindern und Nachkommen (für 819 Knoten in der Mitte eines Baumes von 19657 Knoten)
        Adjacency List parentJoin = 0 childrenJoin = 0 2562 720 ms 1.969 ms 36.9 MB
        Adjacency List parentJoin = 3 childrenJoin = 3 2461 704 ms 1,966 ms 35,3 MB
        Verschachtelte Sätze 1641 522 ms 1,585 ms 25,0 MB
        Verschachtelte Intervalle 1641 579 ms 1,657 ms 25,0 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 1641 569 ms 1.626 ms 23,4 MB
        Materialisierter Pfad (Attributmodus) 1641 793 ms 6.552 ms 44.7 MB
    Test 13. Eine Auswahl von Eltern (für 819 Knoten in der Mitte eines Baumes von 19657 Knoten)
        Adjacency List parentJoin = 0 childrenJoin = 0 3180 948 ms 2.304 ms 51,2 MB
        Adjacency List parentJoin = 3 childrenJoin = 3 1641 486 ms 1,495 ms 30,8 MB
        Geschachtelte Mengen 821 3.238 ms 3.979 ms 20,7 MB
        Verschachtelte Intervalle 821 3,292 ms 4,147 ms 22,0 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 821 292 ms 902 ms 21,2 MB
        Materialisierter Pfad (Attributmodus) 821 582 ms 4,574 ms 24,7 MB
    Test 14. Auswahl benachbarter Knoten (für 819 Knoten in der Mitte eines Baumes von 19657 Knoten)
        Adjacency List parentJoin = 0 childrenJoin = 0 1641 535 ms 1.442 ms 23,7 MB
        Adjacency List parentJoin = 3 childrenJoin = 3 1641 508 ms 1,421 ms 23,6 MB
        Verschachtelte Sätze 1641 513 ms 1,428 ms 24,5 MB
        Verschachtelte Intervalle 1641 19.681 ms 21.326 ms 27.5 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 1641 730 ms 1.695 ms 24,3 MB
        Materialisierter Pfad (Attributmodus) 1641 1,892 ms 2,964 ms 24,3 MB
    Test 15. Auswahl leerer Knoten (für 819 Knoten in der Mitte eines Baumes von 19657 Knoten)
        Adjacency List parentJoin = 0 childrenJoin = 0 1833 568 ms 1,743 ms 32,6 MB
        Adjacency List parentJoin = 3 childrenJoin = 3 1732 556 ms 1.891 ms 31.3 MB
        Verschachtelte Mengen 821 305 ms 908 ms 18,4 MB
        Verschachtelte Intervalle 821 10.450 ms 11.166 ms 18,8 MB
        Materialisierter Pfad (Identität pro Schlüsselmodus) 821 7,968 ms 8,434 ms 18,5 MB
        Materialisierter Pfad (Attributmodus) 821 14,349 ms 19,105 ms 21,3 MB
    

    GitHub Links


    Verschachtelter
    materialisierter Pfad der Adjazenzliste
    Legt die Auto-Baum-Eigenschaft für
    verschachtelte Intervalle fest

    Jetzt auch beliebt: