mysql - Implementing a hierarchical data structure in a database

Question

I know there are two approaches: adjacency list and nested tree. It's said that adjacency list can become slow to use on traversal because of numerous queries. But I don't know any realistic figures for this. The site I'm making will have in the region of 200 pages. Is traversal to generate (for example) a sitemap going to take longer than about 0.3 seconds?

Running on MySQL (innoDB) with LAMP stack.

I'd prefer to implement adjacency if possible because of the more simplistic design.

Thanks.

Answer 1

There are more options than just the two you mention. There are:

• Adjacency List (the "parent_id" one almost everyone uses)
• Nested Sets
• Path Enumeration
• Closure Table (aka Adjacency Relation)

See my answer to "What is the most efficient/elegant way to parse a flat table into a tree?"

Or a couple of books:

• "Trees and Hierarchies in SQL for Smarties" by Joe Celko.
• "SQL Design Patterns" by Vadim Tropashko.