Algoritme, database rijen omzetten naar een tree

[HawVer]

Voor een project moet ik de rijen uit een database omzetten naar een boomstructuur. Elke rij bevat een kolom met een referentie naar de parent. Het aantal rijen kan enorm zijn en het moet uiteindelijk gepresenteerd worden in een treeview. Over de diepte van de tree kan ik niets zeggen.

Ik zit zelf te denken aan een binary search tree te denken om de parents op te zoeken. Ik kan ook lineair door de collectie heen lopen maar dat is veel langzamer. Nadeel van binary search is dat het alleen werkt als de unieke sleutel een integer is. Het liefst wil ik ook tekstvelden als primary key ondersteunen. Eventueel zou je een hash kunnen maken van je tekst, maar dan ben je je eventuele performance winst alweer kwijt. Hebben jullie advies? Eventuele hints richting een algoritme?

Ik heb zelf al één van mijn oude schoolboeken uit de kast getrokken, maar die geeft alleen de binary search tree als oplossing. Daar moet toch wel iets handigers voor zijn.

[!null]

Ik heb de theorie ook niet helemaal helder meer, maar een snelle manier van een rescursieve tabel gebruiken is aflopend sorteren op de parent referentie. Hierdoor bouw je de boom logisch op en iedere keer als je een item/node tegen komt schuif je hem onder de parentnode, want die is er op dat moment toch al. (tenzij je tabel inhoudelijk niet meer klopt).
Met deze techniek voeg je als het goed is alleen maar nodes toe in de context van de parentnode dus heb je ook geen zoekproblemen.

Is de betreffende boom wel in de database aanwezig als recursieve tabel of is het anders geïmplementeerd?

[ Voor 10% gewijzigd door !null op 10-11-2009 11:12 ]

[gorgi_19]

EfBe in "\[VB.NET] Treeview + Subnodes (van Subnodes)"

Heb je hier wat aan?

[LuCarD]

of zoiets?
http://articles.sitepoint...rarchical-data-database/2

of
Crisp's blog: Formatting a multi-level menu using only one query

[ Voor 53% gewijzigd door LuCarD op 10-11-2009 11:20 ]

[Matis]

Momenteel ben ik met ongeveer hetzelfde bezig als jij.

Alleen vul ik mijn subnodes pas als er daadwerkelijk op de expand-knop gedrukt wordt.

Ik heb het overigens in VB6 (VBA) gemaakt

[!null]

Ik doelde dus op zoiets als Crisp op die weblog heeft gepost al zou ik het waarschijnlijk net iets anders invullen.

Je moet ook even melden of je er achteraf in wil kunnen zoeken (in de boom als object/variabele, dus niet in de database) of dat je gewoon een menu wil printen oid. Dat scheelt nogal.

Een boom die je bij openklikken (of wat voor actie dan ook) pas uitbreid wordt natuurlijk een vrij platte query waarin je alleen de kinderen ophaalt aan de hand van WHERE parentid = iets.

[Matis]

Maar is het voor jezelf niet veel makkelijker om een root te hebben met daaronder alleen maar children die parentid 0 hebben.

Wanneer je op child X klikt, dat dan middels eenzelfde query alle rijen die parentid X hebben opgehaald worden en toegevoegd worden aan de node bij het On_Expand event.

Dat doe je dan niet in een query, maar het scheelt wel overhead als je veel (of diepe) nodes hebt.

Hmm, dat zegt !null ook letterlijk.

Note to self; beter lezen, dan pas lullen

[ Voor 9% gewijzigd door Matis op 10-11-2009 11:36 ]

[LuCarD]

Matis schreef op dinsdag 10 november 2009 @ 11:36:
Maar is het voor jezelf niet veel makkelijker om een root te hebben met daaronder alleen maar children die parentid 0 hebben.

Wanneer je op child X klikt, dat dan middels eenzelfde query alle rijen die parentid X hebben opgehaald worden en toegevoegd worden aan de node bij het On_Expand event.

Dat doe je dan niet in een query, maar het scheelt wel overhead als je veel (of diepe) nodes hebt.

Hmm, dat zegt !null ook letterlijk.

Note to self; beter lezen, dan pas lullen

Waarom gaat iedereen er automatisch van uit dat het om een menu gaat? Er zijn meerdere toepassingen mogelijk hierarchial data

[cariolive23]

Met een recursieve query kun je e.e.a. al opvragen, dan is het alleen nog maar presentatie:
http://wiki.phpfreakz.nl/CommonTableExpression

Dit is een voorbeeld in PostgreSQL, Oracle en SQL Server kennen dit in elk geval ook.

[gorgi_19]

!null schreef op dinsdag 10 november 2009 @ 11:33:
Een boom die je bij openklikken (of wat voor actie dan ook) pas uitbreid wordt natuurlijk een vrij platte query waarin je alleen de kinderen ophaalt aan de hand van WHERE parentid = iets.

En wat doe je dan met de kinderen van de kinderen?

LuCarD schreef op dinsdag 10 november 2009 @ 11:54:
Waarom gaat iedereen er automatisch van uit dat het om een menu gaat? Er zijn meerdere toepassingen mogelijk hierarchial data

Waarin verschilt de gedachtengang? (afgezien dat je een menu alleen subselecties ophaalt, maar an sich is een menu ook een boom)

[ Voor 34% gewijzigd door gorgi_19 op 10-11-2009 12:13 ]

[!null]

@cariolive, dat is dus een van de nodeloos ingewikkelde manieren.
Je moet het zo simpel mogelijk oplossen zoals Crisp op die weblog dat doet.

gorgi_19 schreef op dinsdag 10 november 2009 @ 12:11:
[...]

En wat doe je dan met de kinderen van de kinderen?

Dit gaat over de simpelere situatie die Matis schetst. Bij ieder item dat je open klikt haal je zijn kinderen op. Simpel zat.

[HawVer]

!null schreef op dinsdag 10 november 2009 @ 11:10:
Ik heb de theorie ook niet helemaal helder meer, maar een snelle manier van een rescursieve tabel gebruiken is aflopend sorteren op de parent referentie. Hierdoor bouw je de boom logisch op en iedere keer als je een item/node tegen komt schuif je hem onder de parentnode, want die is er op dat moment toch al. (tenzij je tabel inhoudelijk niet meer klopt).
Met deze techniek voeg je als het goed is alleen maar nodes toe in de context van de parentnode dus heb je ook geen zoekproblemen.

Is de betreffende boom wel in de database aanwezig als recursieve tabel of is het anders geïmplementeerd?

Goede tip!

gorgi_19 schreef op dinsdag 10 november 2009 @ 11:15:
EfBe in "\[VB.NET] Treeview + Subnodes (van Subnodes)"

Heb je hier wat aan?

Bedankt voor de link, daar heb ik zeker wat aan.

@overige reacties, bedankt. Overigens is het project een control voor windows form. Ik heb dus geen toegang tot de sql van de statement.

[cariolive23]

!null schreef op dinsdag 10 november 2009 @ 13:16:
@cariolive, dat is dus een van de nodeloos ingewikkelde manieren.
Je moet het zo simpel mogelijk oplossen zoals Crisp op die weblog dat doet.

De oplossing van Crisp is er slechts eentje, het is (net als diverse andere oplossingen) niet dé oplossing. Je komt bv. in de problemen wanneer je alle childs met hun childs van een record wilt opvragen, dat gaat je niet lukken. Ja, wanneer je de complete tabel opvraagt en dan in je applicatie de boel gaan uitpluizen. Maar dat is dus weer nodeloos ingewikkeld en dat wil jij nu net niet. Zie jouw commentaar.

Eén simpele query heeft mijn voorkeur en een recursieve query op zo'n simpel datamodelletje valt in deze categorie. Uitstekende performance, ook bij grote hoeveelheden data.

[!null]

Ja, alleen is dat heel specifiek. Ik kan me niet snel voorstellen wanneer je alle kinderen op dezelfde row wilt hebben. Klinkt voor mij als een foute structuur/ontwerp. Maar soms moet je voor optimalisatie afwijken van een goeie structuur.
Toch blijf ik van mening dat de simpelste oplossing de beste is. Nou ja, tot op zekere hoogte. Je moet niet handmatig voor iedere node een query doen natuurlijk, ook al is dat misschien het simpelst gemaakt.