Does your database have something like a node-id and parent-node-id for each row? You can read all rows and do something like ...
This breaks of course if we get a child before we get the parent. I might try making a placeholder parent node with an id and no other fields in that case. And instead of automatically making a new node for each row, check to see if there is already a placeholder node.
It's getting hard to explain which is a bad sign. I'm not even sure how to add a placeholder to the tree or some collection without knowing its parents. Let's see what anybody else has.
A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Is it slow because you're doing lots of queries? If so, you can speed it up by... well, by doing fewer queries. Either you can fetch all rows, then assemble the tree yourself in Java, or you can tell the database to deliver the tree to you already built. With (semi-) standard SQL, you have to do this with a union and multiple self-joins, and it's messy; but Oracle, DB2, and SQL Server have extensions (CONNECT BY or WITH) that let this be done relatively neatly.
This breaks of course if we get a child before we get the parent.
It's getting hard to explain which is a bad sign.
Absolutely. I had the problem that loading a 10,000-node tree using the obvious recursive method took quite a few minutes. So I rewrote my algorithm to read all the nodes in a single query. And yes, it's a problem when you get children before the parents. You sort of have to throw those nodes into a work area and build up tree fragments as you go along (note that getting a parent isn't the end of the story because the parent's parent might not have shown up yet).
And I also had the requirement that non-leaf nodes with no children weren't supposed to appear in the final tree, which required even more waiting in the work area.
So it took me quite a while to get a functional design. The basics are this: you have a work area where you store nodes that don't have a full path to the root. This work area may contain tree fragments as well as single nodes. When you get a node, if its parent isn't already in the tree then you put it in the work area. If its parent is in the work area then attach it to the parent, and if it has children in the work area then attach them to it. If the node's parent is already in the tree, then you attach it to the parent. You also see if it has any children in the work area, and if it does, you pull them out and attach them to it.
Or you could not bother to build tree fragments in the work area, but just do a recursive search for children in the work area when you take a node out of it to be attached to the tree.
Joined: Feb 11, 2003
Thanks for the replies. I will try both the options and will post my experience here
I just found it by googling for "database trees". I'm sure that some more elaborate search can come up with more.
The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Joined: Jan 29, 2003
So it took me quite a while to get a functional design.
Heh, heh, I started out thinking I could improvise one in the message reply but quickly gave up. I guess you could read nodes into a Map keyed by node-id and "tree them up" in a single pass through all the nodes. The parent should always be in the map by then. Is that too naive? The map gets oughtta be a lot faster than database operations.