• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Tree structure retrieval from Database

 
John Lincoln
Ranch Hand
Posts: 192
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24212
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Paul Clapham
Sheriff
Posts: 21322
32
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 192
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

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

thanks
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic