Beágyazott készlet
A hierarchikus struktúrák tárolása a beágyazott készletek modelljével
Szülő-gyermek modell
Hagyományosan a hierarchikus struktúra olyan modell, amelyben a szülők és a leszármazottak közötti kapcsolatot egyértelműen figyelik. Fa szerkezet esetén minden csomópont egyedi azonosítóval és szülő azonosítójával rendelkezik. Az azonosítóknak semmi köze az adatokhoz, mindegyikük egyedi csomópont-azonosítóként szolgál. A fa gyökereinek különleges értékkel kell rendelkezniük a szülői csomópont azonosítójára, mivel a szülő gyökere nem létezik.
Vegye figyelembe a következő sémát:
Minden nyíl a csomópont szülőjére mutat az azonosító értékeknek megfelelően. parentID és érték a táblából. Ezt a modellt leggyakrabban a hierarchikus struktúrák képviseletére használják. Minden csomópontnak információi vannak a szülőkkel és a leszármazottaikkal kapcsolatban.
Ugyanakkor problémák, amikor az ilyen modell, ha azt akarjuk, hogy minden gyermek egy csomópontot. Tegyük fel, hogy meg kell, hogy egy azonosítót minden gyermek elem csomópont ID-1 Nézzük mi chart, nyugodtan mondhatjuk, hogy ez a csomópont 3., 4. és 5. Mindazonáltal, ha egy adatbázis tábla, hogy ez nem olyan egyszerű.
A gyermek csomópontok megszerzése
Először minden olyan csomópontot kapunk, amelynek szülője az 1. azonosítójú csomópont. Esetünkben ezek a 3. és 4. csomópontok (a sárga nyílások száma a lekérdezés számát jelöli az adatbázisban). Most meg kell szereznünk a 3. és 4. csomópontok gyermekelemeit. Nem nehéz meglátni, hogy ez a módszer sok adat felhasználásával több száz, sőt több ezer lekérdezést eredményez az adatbázisba. Kérjük, vegye figyelembe, hogy a szükséges lekérdezések száma arányos a fa magasságával. Mindig egy lekérdezést kell végrehajtanunk, mint az adatfa magassága.
Beágyazott készletek - a probléma megoldása (beágyazott készlet)
Itt található a beágyazott készletek ötlete. Ez a modell nem olyan egyszerű, mint az előző, ezért próbáljunk kitalálni. A szülő azonosítója helyett a csomópont bal és jobb értékét tároljuk. Nézd meg a táblázatot és az alábbi ábrát:
Ez az, igaz? Mi történt?
Szóval, nyugodtan. Menjünk vissza egy lépéssel és kitaláljuk, hogy történt. A bal és a jobb értékek a gyermekcsomókra vonatkozó hivatkozásokat tárolják. A gyermekcsomópontok viszont ilyen változókkal rendelkeznek, így a beágyazott halmazok meghatározása. Ha például az A csomópont összes elemének (ID = 1) megszerzéséhez szükséges, akkor a következő lekérdezést hajtanám végre:
Válaszul kaptam a C, D és E csomópontokat. Megjegyezzük, hogy nem rekurzív módon, csak egy kérés volt.
Minden rendben van, de hogyan definiálja a bal és a jobb értékeket az elkészített fa számára?
Meglepő módon ez egyáltalán nem nehéz. Itt van az eljárás algoritmusának sémája:
A jobb és bal oldali értékek meghatározása
Indítsa el a bal felső nyilat, és a számláló egyenlő 0. A csomópont átadásakor növelje a számlálót 1-gyel, és írja be a csomópontba. Ha a csomópont bal oldalán van, akkor a számláló értéke marad. és ha jobb, akkor jobb.
Megjegyzendő, hogy ha ez a csomópontnak nincs gyermek elemei, az értékek a bal és a jobb különböznek egy, és ha van, a különbség az értékeket legalább három, és az elmélyülő fészkelő növekszik kettő. Ez az információ sok dologról mesél el anélkül, hogy további kéréseket kívánunk az adatbázisban használni.
Alternatív nézet
Próbáljuk meg értelmezni ezt az adatstruktúrát:
Egy ilyen rendszerből könnyen meghatározhatjuk a készletek szerkezetét és a fészkelés mélységét (a gyökértől való távolság). Az alsó koordináta sor egy dimenziót képvisel, amelyben minden csomópont található. Az egyes következő csomópontok azonosítója egyenként növekszik, és minden csomópont pufferrel rendelkezik az adattároláshoz. Ha ismét kérvényt kértünk az A csomópont összes gyermeke megszerzéséig, akkor kérésünk a következő formában történne:
Csomópontok hozzáadása
Adjuk hozzá egy új csomópontot G-értékkel közvetlenül a fa gyökere (gyökércsomópont) után. Nézd meg a táblázatot és az alábbi ábrát:
Ha egy csomópontot egy másik csomópont közvetlen gyermekeinek szeretne hozzáadni, akkor először ki kell osztania a mezőt a fában. Ehhez a forráscsomópont megfelelő értékét kapjuk. A mi esetünkben ez a 13. A kívánt terület kiválasztásához adjunk hozzá 2 értéket a jobb és bal oldali értékhez. amelyek több mint 13.
Mivel mi hozzá egy csomópont után azonnal a gyökér, frissítse az értékek bal nincs szükség (hozzátesszük G csomópont utódja a gyökér a jogot, hogy minimálisra csökkentsék a lekérdezések száma az adatbázisban. Próbálja meg hozzáadni a bal oldali csomópont és hány értékeket akkor kell frissíteni). Miután azonosították a szükséges helyet, add meg a csomópont megadásával a bal értéke egyenlő az érték a jobb gyökér csomópont, és a megfelelő értéket az azonos értékű plusz egy.
Hogyan lehet törölni a csomópontokat?
A csomópontok törlése nagyon egyszerű művelet. Elemezzünk néhány lehetséges lehetőséget:
A végső csomópont eltávolítása (amely nem rendelkezik gyermekekkel)
Törölje a végső csomópontot, és a többi fa változatlan marad
- Csökkentse az összes bal oldali értéket 2-szel, ami nagyobb, mint a távoli csomópont bal oldali értéke
- Csökkentse az összes megfelelő értéket 2-szel, ami nagyobb, mint a távoli csomópont megfelelő értéke
- Törölje a csomópontot
Csomópont törlése gyermekekkel
- Csökkentse a bal és a jobb értéket egy értékkel, ha a bal oldali érték nagyobb, mint a törölni kívánt csomópont bal oldali értéke, és a megfelelő érték kisebb, mint a megfelelő érték.
- Csökkentse az összes bal oldali értéket 2-vel, ha nagyobbak, mint a törölni kívánt csomópont bal oldali értéke.
- Csökkentse az összes megfelelő értéket 2-tel, ha azok nagyobbak, mint a törölt csomópont megfelelő értéke.
- Távolítsa el a csomópontot.
A gyökércsomó eltávolítása
Úgy tűnik, egy csomópont törlése a gyermekekkel, kivéve, hogy a végén nem csak egy, hanem több fát is kaphatunk. Ha a gyökérnek több leszármazottja van, akkor a végén gyökércsomókká válnak. Általában ez nem túl jó, de néha ez a viselkedés szükséges.
Eltávolítás példa
Lássuk, hogyan néz ki egy csomópont törlése a gyermekekkel (A csomópont, 1. index):
Megjegyzés, C és D csomópontok gyermekei legyenek a gyökér csomópont, és a csomópont E leszármazottja volt C. Ha még folytatódott, és törölje a gyökér, akkor kapott volna eredményeként gyökér csomópont 4 és 2 gyermek (általában az eredmény egy hiba, de megint minden attól a feladattól).
hatékonyság
A beágyazott készletek nagyon hatékonyak az elemek gyermekei listájának lekérésekor. De vannak hátrányai, például amikor csomópont törlése vagy hozzáadásakor ez a modell elveszik, mert számos frissítést kell végrehajtani az adatbázisban. Még akkor is, ha csak három beérkezett SQL lekérdezést kezel, a csomópontok frissítésére irányuló kérelmek száma meglehetősen nagy lehet, ami befolyásolhatja az adatbázis sebességét.