Implementing a hierarchical data structure in a database

mysql database hierarchical-data
Me_here picture Me_here · Feb 13, 2009 · Viewed 16.3k times · Source

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

Bill Karwin picture Bill Karwin · Feb 13, 2009

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:

Related questions

'IF' in 'SELECT' statement - choose output value based on column values

SELECT id, amount FROM report I need amount to be amount if report.type='P' and -amount if report.type='N'. How do I add this to the above query?

Read More
How do I quickly rename a MySQL database (change schema name)?

The MySQL manual at MySQL covers this. Usually I just dump the database and reimport it with a new name. This is not an option for very big databases. Apparently RENAME {DATABASE | SCHEMA} db_name TO new_db_name; does …

Read More
MySQL Error: : 'Access denied for user 'root'@'localhost'

$ ./mysqladmin -u root -p 'redacted' Enter password: mysqladmin: connect to server at 'localhost' failed error: 'Access denied for user 'root'@'localhost' (using password: YES)' How can I fix this?

Read More