Jump to content
  • Advertisement
Sign in to follow this  

How to store tree structures in a DB table?

This topic is 4233 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Let's say i have a dynamic tree structure full of "nodes". Every node has the same properties (branch and leaf nodes are the same, technically). Every node can have an unlimited number of children. Nodes can be removed, added, updated, and spliced/grafted. Now... how to put this in a database? Assuming i'm using MySQL (because i am), do you know how this can be done in a way that reduces the number of queries needed to get info from the tree? I could obviously brute-force my way through it and make a gajillion queries using a recursive function that traverses the tree, but i would like to get info with one or two queries for performance. I've done some internet research on the topic but it seems like most of the solutions are optimized for binary trees. Obviously that doesn't work in this situation because nodes have more than two children. How can I lay out my database tables? Thanks for any input!

Share this post


Link to post
Share on other sites
Advertisement
Well, as far as I can tell you have three choices here:

a) Retrieve the data by using tons of queries.

b) Add a column to the table with a "root_id" containing the id of the node that is at the root of the tree (in addition to a "parent_id" column showing each node's immediate parent), and collect them all in one go using
select * from some_silly_table where root_id = node_id_of_the_tree_root

c) Switch to a database that supports "CONNECT BY" queries for handling recursive structures (Oracle and PostgreSQL comes to mind)

Share this post


Link to post
Share on other sites
You could also use the Modified Preorder Tree Traversal method of working with tree data structures. This article walks through a simple implementation of this method using PHP and MySQL.

I've used this in the past to handle category data and to handle posts in a tree-style forum, and am quite happy with it. If you search for it on Google, you'll find a lot of info about this method as well.

Share this post


Link to post
Share on other sites
I second Fling-master's suggestion. I have used that method myself, and the page he linked to is the same place I learnt it from. It's an effective method, but be sure that you understand it fully before trying to implement it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fling-master
You could also use the Modified Preorder Tree Traversal method of working with tree data structures. This article walks through a simple implementation of this method using PHP and MySQL.

I've used this in the past to handle category data and to handle posts in a tree-style forum, and am quite happy with it. If you search for it on Google, you'll find a lot of info about this method as well.


I already read that article. As i mentioned before, its example relies on an underlying binary-tree scheme which doesn't seem to fit what i need (unlimited child nodes). If i misinterpreted the example, please let me know.

Share this post


Link to post
Share on other sites
I tend to use 2 tables.

The first to store the node info, the second to store the hierarchy.

The hierarchy table has the form

ChildID, Level, ParentID

with ChildID and Level as the compound primary key.

imagine the hierarchy

a
\ b
\ c

the table would contain
{b, 1, a}
{c, 1, b}
{c, 2, a}

it's now trivial to find all the parents or children of a particular node.

if you had

a
\ b

i.e. {b, 1, a}

and added c to b
you first insert {c, 1, b}

then insert matching the parent of c (i.e. b) to the child and incrementing the level

i.e.
INSERT INTO hierachy (ChildID, Level, ParentID)
SELECT 'C', Level + 1, ParentID
FROM hierachy
WHERE ChildID = 'B'

simple eh?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
you could also search for papers by Jens Teubner describing his (and Thorsten Grust's) method of accelerating xpath queries in a tree structure stored in a relational database. This is based on storing the tree using its relative position in the pre/post plane. it is quite easy (and extremely efficient!) to store tree structured data this way in a relational db.
they've also implemented an open source xpath accelerator for monetdb. if you need these kind of queries to be *really* fast. anyway.. their papers almost always show how they store and query tree-structured data. worth reading!

Share this post


Link to post
Share on other sites
Thanks for the links and ideas.

I've given each record a tree_order and a linear_order field (integers) in addition to depth and parent fields. There incurs some extra storage space requirements for those extra fields, but in this case, storage space is insignificant compared to the performance requirements. Storage is cheap.

The tree_order keeps the information in tree node order where the root node is 1, the first child is 2, and the first child's first child is 3, and so on (depth-first). The linear_order is an application-specific order that starts at the bottom of the tree and works it's way across and up (sort of upside-down breadth-first).

Using this i can pull a query like "SELECT * FROM table WHERE root_node = X ORDER BY tree_order" and rebuild the tree into an actual structure by popping off rows from the result set and using a recursive function. My insertion and updates will be very infrequent (if ever needed at all after initial setup), so extraction speeds are the most important. But even then, it would simply require a "SET tree_order = tree_order + 1 WHERE tree_order > X" type of query if i inserted something into the middle of tree, shifting everything up a notch.

Seems to do well so far. Again, thanks for the help.

Share this post


Link to post
Share on other sites
Quote:
Original post by leiavoia
I already read that article. As i mentioned before, its example relies on an underlying binary-tree scheme which doesn't seem to fit what i need (unlimited child nodes). If i misinterpreted the example, please let me know.


No it doesn't; you have indeed misinterpreted it. True, the example tree that is depicted in that article does not have more than two childern per node, but that's just a bad example, not a limitation of the technique. There is no reason why you cannot have more than two children per node.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!