logi sisse meist KKK

Nuputasin pisut puustruktuuri talletamisest andmebaasis ja lugesin pisut juurde ka. N: siit ja siit.

Talletamine iseenesest pole ju probleem, küll aga tekivad küsimused siis, kui on vaja andmeid kasutama hakata, n: mingi sõlme asukohta puus ja selle eellasi/järglasi mugavalt tuvastada, lisada sõlmi ja eemaldada jne. Saan aru, et on 2 klassikalist teed: eellase-põhine (adjacency model) ja eeljärjestusega-puu (Modified Preorder Tree Traversal). Esimene tundus endale alul loogilisem, aga kuna see vajab päris palju rekursiivsust andmekasutusfunktsioonides, hakkasin mõtlema ka teise mudeli peale.

Iseenesest on mu arust selle puuläbinummerdamise puhul tegemist päris vaimuka lahendusega, aga realiseerimisel tekkisid mõned küsimused. Nimelt tundub see lahendus, kus pea kõigi sõlmede vasak- ja paremväärtusi on vaja pidevalt muuta, kui uusi sõlmi lisada või eemaldada, kuidagi liiga ressurssi raiskav.

Parim lahendus, millele ma seni olen tulnud, on piirata harude sügavus ära ja numereerida baassõlmed vastava sammuga. N: kui seada ühe haru võimalikuks sõlmede arvuks 500, siis baassõlmed oleksid 1000, 2000, 3000 jne. See siis võimaldaks vasak- ja paremväärtuste ümberarvutamist piirata ühe haruga. Implementeerida ma veel seda proovinud pole, aga tundub teostatav.

Milliseid variante veel võiks kasutada? On kellelgi mingi oma süsteem puu pidamiseks tabelis? Kuidas teooriat praktikasse kõige paremini rakendada?

(Vabandust, kui terminoloogia pisut longab, ei ole vastavat emakeelset kirjandust lugema sattunud.)

küsitud Feb 04 '11 at 17:45

WK's gravatar image

WK
893712


Parim käsitlus mis mina leidnud olen on see, vt lk 48-77. Eriti peaks Sind huvitama tabel lk 77, kus on toodud ära erinevate meetodite tugevad ja nõrgad küljed. Mina kasutaksin Adjacency List vajadusel kombineerituna Path Enumerationiga. Path-i kaasaegsena hoidmiseks kasutaksin trigereid, või ühesõnaga kapseldaksin selle rakenduse eest ära kuidagi.

link

vastatud Feb 04 '11 at 18:38

Tambet%20Matiisen's gravatar image

Tambet Matiisen ♦♦
77791125

See Closure table mudel tundub veel kõige parem. Võrdlustabel ei too välja tema suurimat miinust (väga sügavad puud vajavad palju kirjeid), aga muidu tundub proovimist väärt idee. Aitüma! PS! Sinu viidatud alajaotus on saadaval ka eraldi esitlusena: http://www.slideshare.net/billkarwin/models-for-hierarchical-data

(Feb 07 '11 at 12:29) WK

Mina olen tihti kasutanud kombineerituna mõlemat samaaegselt. See tähendab, et talletan baasis nii depth ja parent kui ka left ja right väärtused selle põhimõttega, et asi oleks just select päringute jaoks optimeeritud. See, et struktuuri muutmine ja uuendamine on ressursimahukas protsess, polegi väga oluline juhul, kui seda tehakse väga harva.

link

vastatud Mar 25 '11 at 15:55

M%C3%A4rt%20Suga's gravatar image

Märt Suga
1

Sinu vastus
lülita eelvaade

Jälgi seda küsimust

By Email:

Pärast sisselogimist saad tellida muudatuse teavitusi siit

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *kaldkiri* või __kaldkiri__
  • **paks kiri** või __paks kiri__
  • link:[tekst](http://url.com/ "pealkiri")
  • pilt?![alt tekst](/path/img.jpg "pealkiri")
  • nummerdatud nimekiri: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • põhilised HTML märgendid on samuti toetatud

Pinu tööpakkumised

kõik pakkumised »

Küsimuse sildid:

×2
×1

küsitud: Feb 04 '11 at 17:45

nähtud: 2,780 korda

viimati uuendatud: Mar 25 '11 at 15:55

Sarnased küsimused

Litsents: Creative Commons Attribution License | Kontakt: info@pinu.ee