aspose file tools*
The moose likes Java in General and the fly likes Tree structure retrieval from Database Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Tree structure retrieval from Database" Watch "Tree structure retrieval from Database" New topic
Author

Tree structure retrieval from Database

John Lincoln
Ranch Hand

Joined: Feb 11, 2003
Posts: 192
Hi,

I am currently storing a tree structre as a table in the database. My retrieval process includes a a nested for-loop which just checks if there are any child nodes and loos through for nodes.

But it is very slow. Is there a better approach how this can be achieved.

Please throw some light

thanks
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
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
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

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.


[Jess in Action][AskingGoodQuestions]
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18658
    
    8

As Stan James said:
This breaks of course if we get a child before we get the parent.
And:
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.
John Lincoln
Ranch Hand

Joined: Feb 11, 2003
Posts: 192
Hi,

Thanks for the replies. I will try both the options and will post my experience here

thanks
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Another interesting algorithm can be found at http://www.sitepoint.com/article/hierarchical-data-database/2

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
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
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.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Tree structure retrieval from Database