Hierarchical Data Models: Adjacency List vs. Nested Sets Hierarchical Data Models: Adjacency List vs. Nested Sets database database

Hierarchical Data Models: Adjacency List vs. Nested Sets


Nested sets are better for performance, if you don't need frequent updates or hierarchical ordering.

If you need either tree updates or hierarchical ordering, it's better to use parent-child data model.

It's easily constructed in Oracle and SQL Server 2005+, and not so easily (but still possible) in MySQL.


I would use the Modified Preorder Tree Traversal algorithm, MPTT, for this sort of hierarchical data. This allows great performance on traversing the tree and finding children, if you don't mind a bit of a penalty on changes to the structure.

Luckily Django has a great library available for this, django-mptt. I've used this in a number of projects with a lot of success. There's also django-treebeard which offers several alternative algorithms, but I haven't used it (and it doesn't seem as popular as mptt anyway).


According to these articles:

http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/http://explainextended.com/2009/09/29/adjacency-list-vs-nested-sets-mysql/

"MySQL is the only system of the big four (MySQL, Oracle, SQL Server, PostgreSQL) for which the nested sets model shows decent performance and can be considered to stored hierarchical data."