fa tárolási módszer bd - előfoglalás fa bejárás (beágyazott készletek)
Tartalomjegyzék cikk
1. Bevezetés
A design az adatbázis gyakran kell tárolni fa, valamint az adatbázis tábla nem kifejezetten tárolására fák, meg kell, hogy vegye igénybe a különböző trükköket. A legegyszerűbb és legkézenfekvőbb módja -, hogy tartsa az egyes elemek
fa mellett az azonosító (id) hivatkozás a szülő elem (parent_id). De munka egy ilyen fa van társítva egy nagy overhead, így például az összes
fa, azt kell használni rekurzív (vagy emuláció), így ez az egyik SQL lekérdezés
Minden fa elem. Az alábbiakban ismertetjük a módszer, amely lehetővé teszi, hogy a lehető legkisebb költséggel, elvégezve a szükséges műveleteket gyakran fákkal.
2. A módszer leírása
Tegyük fel, hogy egy fát, és azt mondjuk, hogy minden fa elem egy pár értékek, amelyeket szokásosan balra és jobbra. Mi megy a fa körül a gyökér mélység (rekurzív), és rendeljen szekvenciális index bal értéke a felső, ha eljutunk ez az első alkalom, és a megfelelő értéket, ha eljutunk, hogy egy második időt, vagy a csúcs a végső csúcsa a fa (amelynek nincs leszármazottja) . Például, amint az a fénykép a fedélzeten:
3. Előnyök
Mit teszünk az Ön számára? Ez ad nekünk, hogy teljesítményét számos általánosan használt műveletek dolgozik fával (nem kapcsolódik annak módosításával) vihetünk egy (1) SQL-lekérdezés:
- Előállítása részfa (a lista a csúcsok, amelyek egy részfáját egy bizonyos adott csomópont). Ehhez csak be kell kérni elemek listájának bal értékek nagyobbak, mint egy adott csomópont, és a helyes érték - kevesebb:
SELECT * FROM `` tree` WHERE left`> AND `right` <
SELECT * FROM `` tree` WHERE left`
Ehhez már csak be kell rendelni egy minta balról az értéket:
SELECT * FROM `tree` ORDER BY` left`;
Ha ezt kombináljuk 1. bekezdés szerint ez lehetséges egy részletes listát adott részfa.Nem nyújthat be kiegészítő megkeresést. A tetején, amelyre szükségünk van, hogy a kötet csak úgy (jobbra - balra - 1) / 2.
lehet elérni, ha a kérelem elem a legnagyobb érték a bal (vagy jobb legkisebb), melyek az érték kisebb, mint a bal mind a jobb és bal fölött mind a jobb:
$ Bal = min ($ node1_left, $ node2_left);
$ Right = max ($ node1_right, $ node2_right);
SELECT * FROM `` tree` WHERE left` <$left AND ` right `> $ Megfelelő sorrendben `left` DESC LIMIT 1;
Ezen felül, a fa van néhány lehetőség hasznos tulajdonságai:
- Végső csomópont a fa értéke egyenlő a jobb, bal + 1;
- Az első leszármazottja csúcsok elhagyta bizonyos értéke egyenlő az érték a bal szülő - 1;
- Az utolsó gyerek egy bizonyos csúcs joga értéke egyenlő az érték a jobb szülő + 1.
Ahhoz azonban, hogy a rekurzív fa bejárás, még könnyebben kezelhető a hagyományos fa tároló módszerrel az id és parent_id. Nem látok okot arra, hogy hagyjon fel - két fa tároló módszer sikeresen ötvözik, és használja így előnyeit egyaránt.
4. hátrányai
Ezt a módszert az úgynevezett a hátránya, ami az, hogy ha hozzáadni, törölni, és mozgassa a fa elem is újra kell számolni az értékeket a bal és a jobb a fa.
4.1. Elem hozzáadása
Egy új gyermek elem bizonyos adott csúcsban lehet kétféleképpen történhet: a lista tetején a gyermek elemek, és a végén.
UPDATE `tree` SET` left` = `left` + 2 WHERE` left`>;
UPDATE `tree` SET` right` = `right` + 2 WHERE` right`>;
INSERT INTO `tree` SET` left` = + 1, `right` = + 2;
UPDATE `tree` SET` left` = `left` + 2 WHERE` left`>;
UPDATE `tree` SET` right` = `right` + 2 WHERE` right`> =;
INSERT INTO `tree` SET` left` =, `right` = + 1;
Amennyiben $ parent_left és $ parent_right - balra és jobbra értéke a szülő csomópont volt.
Számos kiegészítő elemek ugyanabban a szülő elem lehet optimalizálni nem feltétlenül végre 2 frissítést minden hozzáadott elem - lehetséges, hogy végre frissítése 2 az összes hozzáadott elemet közvetlenül.
4.2. Egy elem törlése vagy részfa
Egy elem törlése vagy részfájának is viszonylag egyszerű:
DELETE FROM `` tree` WHERE left`> = AND `right` <= ;
UPDATE `tree` SET` left` = `left` - + - 1 Ahol a 'left`>;
UPDATE `tree` SET` right` = `right` - + - 1 Ahol a 'right`>;
Amennyiben $ balra és jobbra $ - bal és jobb értékek a felső elem eltávolításához vagy részfa.
4.3. Mozgó elem vagy részfa
Mozgó elemfát a legnehezebb ebben a műveletben is újra kell számolni az értékek a bal és jobb oldalán az egész fát, bár talán optimálisan megvalósítható úgy, hogy a mozgás a szállított fa elemek egy és vertex eltávolítását mozgatható az egész részfa.
4.4. becsületesség
Sajnos, a integritását a fa könnyen megtörni, és elég nehéz visszaállítani. Pontos helyreállítása befejeződött újraszámítása a fa. A kompromisszumos integritásának lehet, például vészhelyzeti megszakítás társított módosításával a fa struktúra. Mint fentebb említettük, a hozzáadása és eltávolítása elem fa áll, több kéréseket. Ha csak egy részük, akkor a integritását a fa lesz törve. Ezért: Először is, azt javasoljuk, hogy egy fa asztal karbantartási műveletek (például a InnoDB MySQL) és működtetni hozzáadása és eltávolítása a fa elemek a tranzakció (START tranzakció ..., COMMIT); Másodszor, adjunk hozzá egy egyedi index a bal és a jobb oldali érték -, persze, nem garantálja a sértetlenségét, de segíthet megelőzni buta hibákat, amikor dolgozik fával.
4.5. Care, hogy frissítse a fa
Amikor a fa módosítás végrehajtása nem szabad elfelejteni, hogy a bal és jobb értékek után megváltozott minden struktúra változását. Így, ha egy válogatást az elemek a fa az adatbázis tábla, valamint egy módosítást, a bal és jobb értékek a minta lesz elavult. Vagy ha megvan a bal és jobb értékek és menti a megfelelő változók módosítását követően a fa változóban tárolt értékek valószínűleg elavult.
5. További Reading
5 hozzászólás a „fa módszer tárolására egy adatbázisban - előfoglalás fa bejárás (beágyazott Sets)”
Lehetséges, hogy tárolja a táblázat ezzel a módszerrel egy-két fa?
Vagy root elemének az egész fát lehet csak egy?
Lehetőség van továbbá, hogy nem úgy tűnik, hogy minden eszközzel biztosítani, hogy a fa szerkezet a listán, kivéve, persze, a saját agy - nem mi határozzuk hiányában ciklusok és egyediségét a gyökér. Továbbá, ugyanazon a csomóponton így tartalmazhatnak több fák egyszerre-de még akkor kiderül, „dag”. Személy szerint, én csak ezt a kérdést - persze ez mind jó, hogyan lehet gyorsan működik fák SQL-en keresztül?
Továbbra is megérteni, hogyan lehet a formázott (beljebb) fa az adatbázisból?
És azt hiszem, hogy így legyen:
- Az első leszármazottja csúcsok elhagyta bizonyos értéke egyenlő az érték a bal szülő + 1; (1 helyett)
- Az utolsó gyerek egy bizonyos csúcs joga értéke egyenlő az érték a jobb szülő - 1 (egy helyett)