searchn nach dem am weitesting rechts gelegenen Knoten eines materialisierten Pfadbaums

Ist es möglich, nach dem path Textfeld eines materialisierten Pfadbaums zu sortieren, um den am weitesting rechts liegenden Knoten des treees zu finden? Betrachten Sie zum Beispiel diese Python-function, die den MP_Node von django- MP_Node :

 def get_rightmost_node(): """Returns the rightmost node in the current tree. :rtype: MyNode """ # MyNode is a subclass of django-treebeard's MP_Node. return MyNode.objects.order_by('-path').first() 

Nach all meinen Tests scheint es das zu liefern, was ich erwarte, aber ich weiß nicht, wie ich die math aufstellen soll, um es zu beweisen. Und ich habe keine Informationen über das Ausführen dieser Operation in einem materialisierten Pfadbaum gefunden.

Treebeards Implementierung hat keine Trennzeichen in Pfaden, daher sehen die Pfade wie 00010001 : 0001 , 00010001 , 000100010012 , usw.

Solutions Collecting From Web of "searchn nach dem am weitesting rechts gelegenen Knoten eines materialisierten Pfadbaums"

Kurze Antwort: Nein.

Hier ist eine SQLFiddle demonstriert das Problem, das ich in meinem Kommentar beschrieben.

Für diese einfache Einrichtung:

 id, path 1, '1' 2, '1\2' 3, '1\3' 4, '1\4' 5, '1\5' 6, '1\6' 7, '1\7' 8, '1\8' 9, '1\9' 10, '1\10' 

Der Versuch, das rechte Blatt ( id = 10 ) mit einer einfachen sorting zu erhalten, wird fehlschlagen:

 SELECT TOP 1 id, path FROM hierarchy ORDER BY path DESC 

kehrt zurück:

 id, path 9, 1\9 

Da path eine textbasierte Spalte ist, kommt 1\10 nach 1\9 in der absteigenden sorting (Siehe die Ergebnisse der zweiten Abfrage in der Geige).

Selbst wenn Sie mit der Verfolgung der Tiefe und Pfadlänge beginnen, die im Allgemeinen billig und einfach zu halten sind, wäre es durchaus möglich, solche Pfade zu erhalten:

 path depth length 12\3\11\2 4 9 5\17\10\1 4 9 

die würden immer noch nicht richtig sortieren.

Auch wenn Sie Buchstaben anstelle von Zahlen verwenden, schiebt dies den Problemhorizont nur auf das 26. Kind statt auf das 10. Kind:

SQLFiddle mit Buchstaben

Ich kenne mich mit materialisierten Pfadoperationen nicht so gut aus wie mit verschachtelten Mengen- und Adjazenzlisten und habe keine Erfahrung mit Django, also werde ich auf andere verzichten, wenn es methods gibt, von denen ich nichts weiß, aber Sie werden es mit ziemlicher security tun müssen Führen Sie eine Art von Parsing in der path , um konsistent das richtige Blatt zu erhalten.

EDIT – Nachdem wir uns der Frage gewidmet haben, ob das Sortieren eine gültige Lösung ist, hier ein paar Anmerkungen zu anderen möglichen Lösungen nach ein bisschen Diskussion und ein wenig Nachdenken über das Problem:

– "Rightmost" ist ein vager Begriff, wenn Knoten mehr als zwei Kinder haben können (dh der tree ist kein Binärbaum). Wenn ein Knoten 10 Kinder hat, die sich links vom Elternteil befinden und welche rechts? Sie müssen diese Bedingung definieren, bevor Sie eine Lösung für das Problem definieren können.

– Sobald "ganz rechts" für Ihren Problembereich richtig definiert ist, müssen Sie verstehen, dass der Knoten ganz rechts nicht unbedingt auf der untersten Ebene der Struktur liegt:

  1 / \ 1\1 1\2 <= This is the rightmost node / 1\1\1 <= This is the lowest node 

– Sobald "ganz rechts" definiert ist, kann eine einfache loop verwendet werden, um den am weitesting rechts liegenden Knoten programmatisch zu finden:

 //in pseudocode function GetRightmostNode(Node startNode) { Node currentNode = startNode; while(currentNode.RightChildren != null) { currentNode = maximum of currentNode.RightChildren; } return currentNode; } 

Diese loop sucht nach untergeordneten Elementen des aktuellen Knotens rechts vom aktuellen Knoten. Wenn sie existieren, wählt sie das rechte der rechten Kinder aus und wiederholt es. Sobald es einen Knoten ohne Kinder auf der rechten Seite erreicht, gibt es den aktuellen Knoten zurück, da es den Knoten ganz rechts des trees (oder Teilbaums) mit startNode als Wurzel gefunden hat.

Ist es möglich, nach dem Pfad-Textfeld eines materialisierten Pfadbaums zu sortieren, um den am weitesting rechts liegenden Knoten des treees zu finden?

Nein. Wenn Knotenpfade wie '/1/3/6/2' 1/3/6/2 '/1/3/6/2' gespeichert werden, beachten Sie Folgendes:

 /1 /1/3 /1/3/6/2 /1/3/6/5 /1/3/6/21 /1/40 

Beantworten Sie die Antwort von Paul für die Gründe, die das Sortieren von oben nicht funktionieren würden.

Alle Hoffnung ist jedoch nicht verloren. Wenn Sie nach dem "am weitesting rechts liegenden Knoten" suchen, bei dem Sie annehmen, dass Sie die tiefsten Knoten in einem tree meinen, können Sie einfach die Trennzeichen zählen. Zum Beispiel:

 select length(regexp_replace('/1/3/6/2', '[^/]+', '', 'g')) as depth; 

Wenn Sie nach dem Maximum suchen, verwenden Sie etwas wie:

 order by length(regexp_replace(path, '[^/]+', '', 'g')) desc 

… oder der entsprechende Python-Code. Indexoptionen umfassen das Indizieren desselben Ausdrucks oder das memoryn des Ergebnisses in einem separaten Tiefenfeld und das Indizieren dieses Ergebnisses.

Wenn Sie immer noch an dem tatsächlichen Wert der ID interessiert sind, entsprechen die oben genannten Zahlen normalerweise der ID, also bestellen Sie weiter mit dieser Spalte. Wenn sie unterschiedlich sind, extrahiere die rechte Figur mit einem anderen regulären Ausdruck und wandle sie in eine ganze Zahl, um sie auf natürliche Weise zu sortieren (1, 11, 2) statt lexikographisch (1, 11, 2):

 select regexp_replace('/1/3/6/2', '^.+/', '')::int as value; 

EDIT: Paul Griffin wies zu Recht darauf hin, dass meine Antwort unzuverlässig war, da angenommen wurde, dass die Knoten unter einem bestimmten Wert liegen würden. Hier ist ein besserer Versuch, zwei Spins auf Denis de Bernardys Tiefenfunktion einzubuild.

Verwenden Sie zwei Sortierkriterien, eins für die Tiefe und dann noch eins für den Wert des am weitesting links gelegenen Knotens, der in eine Ganzzahl konvertiert wird:

 SELECT path, length(regexp_replace(path, '[^/]+', '', 'g')) as depth, regexp_replace(path, '^.*/', '')::int as last FROM test ORDER BY depth DESC, last DESC; 

Dies bringt den tiefsten Knoten mit dem höchsten Wert an die Spitze.

SQLFiddle

Sie können die Methode @Paul mit ein paar Modifikationen verwenden. Sie können 0 vor jeder Ziffer anhängen und eine einheitliche Länge jedes Pfades haben.

Den Knoten kann Pfad wie folgt zugewiesen werden:

 id | path ----------------- 1 | '01' 2 | '01\01' 3 | '01\02' 4 | '01\03' 5 | '01\04' 6 | '01\04\01' 7 | '01\04\02' 8 | '01\04\03' 9 | '01\05\01' 10 | '01\05\02' 11 | '01\05\03' 12 | '01\05\04' 

Das obige Beispiel kann verwendet werden, wenn die Anzahl der Kindknoten des Knotens mit der maximalen Anzahl von Kindknoten weniger als 100 beträgt.

Wenn es zwischen 100 und 1000 liegt, können Sie eine zusätzliche 0 wie 001\003\002\005 hinzufügen.

Dann können Sie den rechten Knoten 12 als

 SELECT TOP 1 id FROM tree ORDER BY path DESC 

Sie können die Demo hier finden. Demo