5

I'm looking for a Django tree library and doing my best to avoid Nested Sets (they're a nightmare to maintain).

The cons of the adjacency list model have always been an inability to fetch descendants without resorting to multiple queries. The WITH clause in Postgres seems like a solid solution to this problem.

Has anyone seen any performance reports regarding WITH vs. Nested Set? I assume the Nested set will still be faster but as long as they're in the same complexity class, I could swallow a 2x performance discrepancy.

Django-Treebeard interests me. Does anyone know if they've implemented the WITH clause when running under Postgres?

Has anyone here made the switch away from Nested Sets in light of the WITH clause?

Koobz
  • 6,928
  • 6
  • 41
  • 53
  • You may be interested in django-mptt (http://code.google.com/p/django-mptt/), which is a Django implementation of modified preorder tree traversal. On the other hand, you may not (it's difficult to know without knowing what problem you're trying to solve). Sadly, I've no idea what django-treebeard does, so I can't answer your question more helpfully than that. – Dominic Rodger Jan 31 '10 at 16:24
  • Treebeard is similar to MPTT except it offers multiple tree implementations (including the basic adjacency list model). The problem I'm trying to solve is implementing an efficient tree structure while avoiding nested sets. "WITH" is a relatively new technology as far as the open-source RDBMS go and has the potential to make this possible. I'm wondering if anyone has used it in practice. – Koobz Jan 31 '10 at 23:46

2 Answers2

4

Here's another reference comparing the performance (but without reference to django): http://explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/

Adjacency list vs. nested sets: PostgreSQL (Quassnoi) Given the said above and taking into account that the nested sets model is much harder to manage, we can conclude that adjacency list model should be used to manage hierarchical data in PostgreSQL 8.4.

Bryce
  • 8,313
  • 6
  • 55
  • 73
1

Some thoughts regarding the possibilities of this approach here:

https://cra.mr/2010/05/30/scaling-threaded-comments-on-django-at-disqus/

In short: David Cramer (django-debug-toolbar) really likes recursive queries and how they've performed for Disqus.

Orkhan Alikhanov
  • 9,122
  • 3
  • 39
  • 60
Koobz
  • 6,928
  • 6
  • 41
  • 53