Tree Transversal vs. adjacency model

Questions about the MySQL, PostgreSQL, and most other databases, as well as using it with PHP can be asked here.

Moderator: General Moderators

Post Reply
GeXus
Forum Regular
Posts: 631
Joined: Sat Mar 11, 2006 8:59 am

Tree Transversal vs. adjacency model

Post 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?
User avatar
aaronhall
DevNet Resident
Posts: 1040
Joined: Tue Aug 13, 2002 5:10 pm
Location: Back in Phoenix, missing the microbrews
Contact:

Post by aaronhall »

As bad as what? You don't have much of a choice if you're using a tabular database.
GeXus
Forum Regular
Posts: 631
Joined: Sat Mar 11, 2006 8:59 am

Post 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.
User avatar
aaronhall
DevNet Resident
Posts: 1040
Joined: Tue Aug 13, 2002 5:10 pm
Location: Back in Phoenix, missing the microbrews
Contact:

Post 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.
Last edited by aaronhall on Sun Apr 15, 2007 9:45 pm, edited 1 time in total.
GeXus
Forum Regular
Posts: 631
Joined: Sat Mar 11, 2006 8:59 am

Post 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)
User avatar
aaronhall
DevNet Resident
Posts: 1040
Joined: Tue Aug 13, 2002 5:10 pm
Location: Back in Phoenix, missing the microbrews
Contact:

Post by aaronhall »

I'm still confused about "tree traversal" -- can you write out an example database schema?
User avatar
CoderGoblin
DevNet Resident
Posts: 1425
Joined: Tue Mar 16, 2004 10:03 am
Location: Aachen, Germany

Post by CoderGoblin »

Sitepoint Storing Hierarchical Data in a Database is what I used to get to grips with it. Fairly straightforward.
Begby
Forum Regular
Posts: 575
Joined: Wed Dec 13, 2006 10:28 am

Post 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.
Post Reply