• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Tree structure retrieval from Database

 
Ranch Hand
Posts: 192
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 28177
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

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

thanks
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
rubbery bacon. rubbery tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic