MySQL Bäume (nested sets) - Fragen bzgl. Update

**AmicaNoctis** · 25.02.2010, 00:59

Hallo,

eigentlich ist das nicht so schwierig. Die einfachste Variante besteht ja darin, den Teilbaum zu entfernen und woanders wieder einzufügen.

Um zwei Kinder eines Knotens (also selbe Ebene) aber effizienter zu tauschen, wird es etwas knifflig. Erstens vom Statement her und zweitens deshalb, weil du dann keinen UNIQUE INDEX auf lft und rgt haben darfst. Während des UPDATE entstehen nämlich kurzzeitig Duplikate. Hier musst du also sehr sorgfältig Sicherheit gegen Performance abwägen.

Code:

update tree
set
	left = left + @offset := if (left < least(:al, :bl) or left > greatest(:ar, :br),
		0,
		if (left > least(:ar, :br) and right < greatest(:al, :bl),
			greatest(:ar, :br) - greatest(:al, :bl) - least(:ar, :br) + least(:al, :bl),
			if (left < greatest(:al, :bl),
				greatest(:ar, :br) - least(:ar, :br),
				least(:al, :bl) - greatest(:al, :bl)
			)
		)
	),
	right = right + @offset;

Für :al musst du dann den lft-Wert des einen Teilbaums (A) und für :ar dessen rgt-Wert übergeben. Für den zweiten Teilbaum (B) übergibst du den lft-Wert als :bl und den rgt-Wert als :br.

Edit: Wenn du die beiden Teilbäume schon vorsortiert übergibst, kannst du sogar noch auf die ganzen greatest- und least-Aufrufe verzichten:

Code:

update tree
set
	left = left + @offset := if (left < :al or left > :br,
		0,
		if (left > :ar and right < :bl,
			:br - :bl - :ar + :al,
			if (left < :bl, :br - :ar, :al - :bl)
		)
	),
	right = right + @offset;

Der Teilbaum A muss dann der mit den niedrigeren Werten sein und B der mit den höheren.

Das Statement unterstützt auch nicht benachbarte Teilbäume, aber sie müssen Geschwister sein, also direkt in demselben Elternknoten liegen.

Für deinen 2. Anwendungsfall kommst du trotzdem besser, wenn du den Teilbaum aushängst und neu einhängst.

Gruß,

Amica

**AmicaNoctis** · 25.02.2010, 13:10

Hallo nochmal,

ich hab jetzt auch eine Single-Statement-Lösung für die zweite Aufgabe, also das Verschieben eines beliebigen Teilbaums an eine beliebige neue Stelle:

[Nested Set] move subtree

Das deckt also auch den ersten Fall gleich mit ab.

Gruß,

Amica

**carapau** · 26.02.2010, 21:08

Zitat von AmicaNoctis Beitrag anzeigen

...
ich hab jetzt auch eine Single-Statement-Lösung für die zweite Aufgabe, also das Verschieben eines beliebigen Teilbaums an eine beliebige neue Stelle:

[Nested Set] move subtree ...

Saubere Arbeit, klappt perfekt - Danke!!!

Jetzt hätte ich noch ein kleines Problem: das Löschen.

Hat da jemand was professionelles im Ärmel?

Gruß
carapau

**AmicaNoctis** · 26.02.2010, 21:42

Mit so viel Inspiration solltest du das bisschen Löschen selbst hinbekommen.

Wenn nicht, findest du das in praktisch jedem Nested-Sets-Tutorial. Wie man Google benutzt, weißt du hoffentlich?

Gruß,

Amica

**carapau** · 27.02.2010, 00:23

Zitat von AmicaNoctis Beitrag anzeigen

Mit so viel Inspiration solltest du das bisschen Löschen selbst hinbekommen.

Wenn nicht, findest du das in praktisch jedem Nested-Sets-Tutorial. Wie man Google benutzt, weißt du hoffentlich?

Gruß,

Amica

Ich habs jetzt einfach mit mehreren Queries gemacht, funktioniert wunderbar.

**AmicaNoctis** · 27.02.2010, 00:37

Ja, geht auch nur mit mehreren. Ein DELETE Statement und ein UPDATE Statement um die lft/rgt-Werte zu verringern.

**sqeez3r** · 15.07.2010, 12:39

Hallo!

Während ich die einfacheren Operationen wie Einfügen und Löschen noch problemlos alleine "entwickeln", habe ich bei der Suche nach einer Lösung zum Verschieben google bemüht und bin hier gelandet.

Amica, deine 1-Query-Lösung ist sehr beeindruckend! Allerdings verstehe ich nicht ganz, wie sie einzusetzen ist: Wenn ich die Parameter l, r und p schon in PHP mit den Werten des zu verschiebenden Subbaumes bzw. des Ziel-Subbaumes fülle, kommt am Ende so etwas wie "where 4 < 5 or 5 < 1" heraus, was für mich keinen Sinn gibt.

Vielleicht kann mir jemand auf die Sprünge helfen? DANKE!

**AmicaNoctis** · 15.07.2010, 12:59

Zitat von sqeez3r Beitrag anzeigen

kommt am Ende so etwas wie "where 4 < 5 or 5 < 1" heraus, was für mich keinen Sinn gibt.

Warum nicht? Vier ist doch kleiner als fünf: Bedingung erfüllt.

Nur wenn z. B. l = 12; r = 19; p = 15 ist, ergibt sich 19 < 15 or 15 < 12 womit die Bedingung nicht erfüllt ist, weil man dann einen Teilbaum in sich selbst verschieben würde, was nicht gehen kann und darf.

**sqeez3r** · 15.07.2010, 13:51

Achso, ok ich verstehe.

Trotzdem funktioniert der Query bei mir nicht. Wahrscheinlich mache ich etwas falsch!

Ich habe nur zwei Teilbäume:
zsb1 5 8
zsb2 1 4
blech von zsb1 6 7
blech von zsb2 2 3

Wenn ich nun den Eintrag "zsb2" (inkl. "blech von zsb2") in "zsb1" verschieben möchte, sieht das so aus:

Code:

$result = $this->query("SELECT `liGrenze`, `reGrenze` FROM `bauteil` WHERE `Teilenr` = '" . $id . "'");
        $bauteil = $result->fetch_object();
        $result = $this->query("SELECT `liGrenze`, `reGrenze` FROM `bauteil` WHERE `Teilenr` = '" . $zielID . "'");
        $zielBauteil = $result->fetch_object();

$this->query("
        update bauteil
        set
    liGrenze = liGrenze + if (".$zielBauteil->liGrenze." > ".$bauteil->reGrenze.",
        if (".$bauteil->reGrenze." < liGrenze and liGrenze < ".$zielBauteil->liGrenze.",
            ".$bauteil->liGrenze." - ".$bauteil->reGrenze." - 1,
            if (".$bauteil->liGrenze." <= liGrenze and liGrenze < ".$bauteil->reGrenze.",
                ".$zielBauteil->liGrenze." - ".$bauteil->reGrenze." - 1,
                0
            )
        ),
        if (".$zielBauteil->liGrenze." <= liGrenze and liGrenze < ".$bauteil->liGrenze.",
            ".$bauteil->reGrenze." - ".$bauteil->liGrenze." + 1,
            if (".$bauteil->liGrenze." <= liGrenze and liGrenze < ".$bauteil->reGrenze.",
                ".$zielBauteil->liGrenze." - ".$bauteil->liGrenze.",
                0
            )
        )
    ),
    reGrenze = reGrenze + if (".$zielBauteil->liGrenze." > ".$bauteil->reGrenze.",
        if (".$bauteil->reGrenze." < reGrenze and reGrenze < ".$zielBauteil->liGrenze.",
            ".$bauteil->liGrenze." - ".$bauteil->reGrenze." - 1,
            if (".$bauteil->liGrenze." < reGrenze and reGrenze <= ".$bauteil->reGrenze.",
                ".$zielBauteil->liGrenze." - ".$bauteil->reGrenze." - 1,
                0
            )
        ),
        if (".$zielBauteil->liGrenze." <= reGrenze and reGrenze < ".$bauteil->liGrenze.",
            ".$bauteil->reGrenze." - ".$bauteil->liGrenze." + 1,
            if (".$bauteil->liGrenze." < reGrenze and reGrenze <= ".$bauteil->reGrenze.",
                ".$zielBauteil->liGrenze." - ".$bauteil->liGrenze.",
                0
            )
        )
    )
        where ".$bauteil->reGrenze." < ".$zielBauteil->liGrenze." or ".$zielBauteil->liGrenze." < ".$bauteil->liGrenze);

Und am Ende kommt dann das raus:

[Code entfernt, da überlang (>900 Zeichen) und nicht wirklich relevant, Amica]

Es sind allerdings keine Zeilen von dem Qry betroffen.
Sorry, wenn ich mich blöd anstelle

**AmicaNoctis** · 15.07.2010, 13:57

Dann muss dein p 8 sein, nicht 5.

-- moves a subtree before the specified position
-- if the position is the rgt of a node, the subtree will be its last child
-- if the position is the lft of a node, the subtree will be inserted before
-- @param l the lft of the subtree to move
-- @param r the rgt of the subtree to move
-- @param p the position to move the subtree before

Übrigens: Das Statement kannst du ganz leicht mit den Parametern füllen, indem du prepared Statements verwendest. Dann brauchst du das nicht so umständlich zusammenstückeln.

**sqeez3r** · 15.07.2010, 17:34

Hallo Amica!

Danke nochmals für deine Hilfe. So funktioniert es einwandfrei.
Das ganze in einem Statement ist echt super, denn so erspart man sich auch den ganzen "LOCK TABLES" Kram

Das Ganze als Prepared Statement umzusetzen ist auch eine gute Idee, das mache ich direkt mal.

MySQL Bäume (nested sets) - Fragen bzgl. Update