Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Representing Trees in PostgreSQL

woss.name

Post reply on HN
Print view View original

31–40 of 60 posts

Re: Representing Trees in PostgreSQL

#31

Post by jhgg »

robertfw wrote: post #28
savagej wrote: post #19

I've used django-mptt to represent a tree of human phenotypes before. It was fast and quite an easy api to use. I was using PostgreSQL as the backend. https://www.djangopackages.com/packages/p/django-mptt/

I've also used django-mptt and just wanted to throw another vote behind it in case anyone is considering using it. Our data structure was a good fit for MPTT (many reads, few writes) so I can't comment on how it would behave in the opposite scenario. Nice API, very easy to use from a developer standpoint. We were using MySQL.

Likewise. I've done some heavy modification ontop of django-mptt to support limiting tree depth when querying, calculating total children, querying siblings, etc...

https://gist.github.com/jhgg/32a379e34c8a56303295

Re: Representing Trees in PostgreSQL

#32

Post by elliotec »

techtalsky wrote: post #4

There's a great Ruby on Rails gem called acts_as_sane_tree (after the non-recursive acts_as_tree) that uses postgresql's recursive queries. I'm using it on a project and have found it useful with good performance: https://github.com/chrisroberts/acts_as_sane_tree

I've used gem awesome_nested_set with lots of success in the past. https://github.com/collectiveidea/awesome_nested_set. Updated quite often, Rails 4 supported

Re: Representing Trees in PostgreSQL

#33

Post by Someone »

barosl wrote: post #9

Does anyone remember how Drupal handles the hierarchical comments? It maintains a "sort key" field for each comment, which consists of multiple index numbers for all levels, much like the section numbers in Wikipedia. 1 1.1 1.2 2 2.1 2.1.1 2.1.2 2.1.2.1 In this way, displaying comments in a tree form is trivial. Just ORDER BY the sort key. I find it brilliant for applying to such an application.

But beware of what may happen when you get over 9:

  1
  1.1
  1.2
  10
  2
  2.1
To support that, you will have to be careful when picking collation order, and binary collation will not do it. It may be better to use fixed-width numbers with leading zeroes instead, but that, of course, may unnecessarily grow the space used by the table.

And of course, that also is what RCS and SCCS use for numbering revisions.

Re: Representing Trees in PostgreSQL

#34

Post by alistairbayley »

tempVariable wrote: post #20
platz wrote: post #15

Earlier quoted context omitted.

I've done nested set before; it's interesting - very fast for queries, but requires a lengthy insert/update cost. Also, team members were absolutely clueless as to what was really going on. I'm not sure nested sets are really much faster than what modern rdbms's can provide today.

In addition to expensive insert/update, it is necessary to keep the left and right boundaries across ALL of your entries in perfect order. If the boundaries get out of whack, fixing the tree is a nightmare scenario. I worked on a multi-tenant application with distinct trees present in one table and with one tree per table and so on. Fun fun fun!

I think the nested intervals model, a refinement of nested sets, solves this slow update problem: http://www.rampant-books.com/art_vadim_nested_sets_sql_trees...

But I've never had to use it, so I am just guessing.

Same article, different site: https://communities.bmc.com/docs/DOC-9902

And a paper: http://www.sigmod.org/publications/sigmod-record/0506/p47-ar...

Here's a comparison of the different approaches in a matrix: http://vadimtropashko.wordpress.com/2008/08/09/one-more-nest...

Re: Representing Trees in PostgreSQL

#35

Post by Walkman »

I don't know if ActiveRecord is capable of doing this, but here is how to do it with Django ORM:

in models.py:

    class Node(models.Model):
        parent = models.ForeignKey('self', related_name='children')
in the view:

    nodes = Node.objects.prefetch_related('children')
in template:

    {% for node in nodes %}
        {% for subnode in node.children.all %}
        ...
        {% endfor %}
    {% endfor %}
This will make exactly two queries; one for all the parent nodes, and one for the children nodes. Django will make the pairing automagically, so you don't have to do it in view code.

Re: Representing Trees in PostgreSQL

#36

Post by andrewflnr »

rickmode wrote: post #16
kpmah wrote: post #3

There is also ltree http://www.postgresql.org/docs/9.3/static/ltree.html Adjacency lists also don't perform that badly with recursive queries in my experience.

This. The project I'm on used materialized paths, which lead to great pain. I investigated nested intervals ... and they could't achieve the tree depths we needed (we were modeling a file system tree). We are back to adjacency lists (using a parent ID) but redesigned to avoid the need for recursive ancestor and descendant queries. _But_ the RDBMS doesn't support recursive queries and I've been curious about PostgreSQ…

Can you elaborate on how materialized path caused pain? Was it more performance or maintenance? I would have expected MP to be a good fit for modeling a file system.

Re: Representing Trees in PostgreSQL

#37

Post by techtalsky »

elliotec wrote: post #32
techtalsky wrote: post #4

There's a great Ruby on Rails gem called acts_as_sane_tree (after the non-recursive acts_as_tree) that uses postgresql's recursive queries. I'm using it on a project and have found it useful with good performance: https://github.com/chrisroberts/acts_as_sane_tree

I've used gem awesome_nested_set with lots of success in the past. https://github.com/collectiveidea/awesome_nested_set . Updated quite often, Rails 4 supported

Yeah, the Nested Set model is cool but it does not use recursive postgresql queries under the hood: http://mikehillyer.com/articles/managing-hierarchical-data-i...

Re: Representing Trees in PostgreSQL

#38

Post by caust1c »

Walkman wrote: post #35

I don't know if ActiveRecord is capable of doing this, but here is how to do it with Django ORM: in models.py: class Node(models.Model): parent = models.ForeignKey('self', related_name='children') in the view: nodes = Node.objects.prefetch_related('children') in template: {% for node in nodes %} {% for subnode in node.children.all %} ... {% endfor %} {% endfor %} This will make exactly two queries; one for all the pa…

Unfortunately, this still only gets the children of the root. If you want to be able to recursively get all the children and grandchildren of a root, you're going to be doing (N - leaves) queries where N is the number of Nodes in the tree.

However, there is of course a django package to help with this and gathers all the nodes you care about into one query:

https://github.com/django-mptt/django-mptt

Re: Representing Trees in PostgreSQL

#40

Post by herge »

Walkman wrote: post #35

I don't know if ActiveRecord is capable of doing this, but here is how to do it with Django ORM: in models.py: class Node(models.Model): parent = models.ForeignKey('self', related_name='children') in the view: nodes = Node.objects.prefetch_related('children') in template: {% for node in nodes %} {% for subnode in node.children.all %} ... {% endfor %} {% endfor %} This will make exactly two queries; one for all the pa…

If you ever need to deal with trees deeper than one level in django, I'd highly recommend looking at (as mentioned in another comment):

https://www.djangopackages.com/packages/p/django-mptt/

Post reply on HN