Page 1 of 1

Tree Transversal vs. adjacency model

Posted: Sun Apr 15, 2007 8:17 pm
by GeXus
I understand that tree traversal is concidered the best for storing hierarchies, but to be honest.. It's freakin' hard! Is adjacency model really that bad?

Posted: Sun Apr 15, 2007 8:27 pm
by aaronhall
As bad as what? You don't have much of a choice if you're using a tabular database.

Posted: Sun Apr 15, 2007 8:31 pm
by GeXus
I mean compared to tree traversal... I could spend days trying to figure this out.. and I will if adjacency is simply inefficient.

Posted: Sun Apr 15, 2007 9:24 pm
by aaronhall
The two aren't comparable. "Adjacency model" describes how you would store hierarchical data in tabular form. "Tree traversal" describes how you would access and present that data. In PHP, you can use a recursive function to construct an array of arrays from the tabular data, and use another recursive function to traverse that array and display the data.

Posted: Sun Apr 15, 2007 9:34 pm
by GeXus
Maybe i'm using the wrong terms.. Here is an example of what im comparing..

Tree Traversal (left and right values assigned to nodes)

Adjacency (using a parent_id column, to store the id of the parent node)

Posted: Sun Apr 15, 2007 9:46 pm
by aaronhall
I'm still confused about "tree traversal" -- can you write out an example database schema?

Posted: Mon Apr 16, 2007 2:46 am
by CoderGoblin
Sitepoint Storing Hierarchical Data in a Database is what I used to get to grips with it. Fairly straightforward.

Posted: Mon Apr 16, 2007 8:39 am
by Begby
Pre-order tree transversal and the adjacency model both have advantages and disadvantages

preorder

- Very slow inserts and updates which get slower as the tree grows larger
- Very fast reads including getting an entire tree or arbitrary subtree in a single query
- Sometimes complex SQL

Adjacency
- Fast inserts and updates
- Slow reads, can only be done in one (potentially slow) SQL statement if you have a fixed tree depth or you have to run the results through a recursive function. As your tree grows reading it becomes slower.
- Simpler SQL


Personally I prefer tree transversal mainly for the fact that its so darn easy to get a really slick tree into any form out of it without too much hassle. The SQL looks complex, but it is actually pretty logical. One thing you can do is setup a set of stored procedures, or encapsulate it into a class, then you don't have to always deal with it.

A really good reference on this stuff is a book by Joe Celko. I can't remember the name of the book, but google for it. After you get around the author's ego you will find a really good discussion and reference for both of these storage types along with well documented and extensive SQL examples.