51–60 of 60 posts
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.
Earlier quoted context omitted.
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.
Second, the materialized path's length exceeded the database's indexable length limit. (MySQL, the DB in question, has a default index limit of 767 bytes, so only first 767 bytes are indexed.)
There are ways around these issues (like using "UPDATE ... WHERE" rather than using an ORM to walk the tree and update... sigh). We also had other app-specific / design-specific issues too that swamped these issues performance wise.
I'm hopefully we won't need ancestor and descendant queries again in our re-design. But I'm keeping PostgreSQL with its Common Table Expression stuff--the thing that facilities recursive queries--in my back pocket. It's that or use a stored procedure to build the capability by hand.
A good book on the subject is Joe Celko's Trees and Hierarchies in SQL for Smarties. http://www.amazon.com/Hierarchies-Smarties-Edition-Kaufmann-... He spends a chapter on each of the models outlined in this post: adjacency, path, and nested set models.
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.
I experimented with a variation by Vadim Tropashko using something called "Farey fractions" [1]. These represent the intervals as a 2x2 matrix of four integers rather than two floating point values.
The numbers are effectively limited to 32-bit values in the matrix since a multiplication is required (resulting in 64-bit intermediate results).
It was very interesting, but couldn't model a file system hierarchy well. It could roughly 10^32 items in the best case, but a very small number (hundreds) in edge cases.
For example, it maxes out at a depth of 17 with 100 items at each level, or a depth of 34 with 10 items each. This might be fine for modeling some hierarchies, but definitely not a file system. The edge case is if the fraction extends along one edge. So if we have 10 items per level, and add a child at the leftmost edge each time, we create the most costly fractional subdivision. Do this 35 times and you hit an math overflow.
[1] Check out the Chapter 5 and Errata links: http://vadimtropashko.wordpress.com/“sql-design-patterns”-bo...
What are the upsides to this vice using a graph database like Neo4j?
Another option for storing tree structures is the closure table [1]. It acts as a sort of "many-to-many" junction table between the tree nodes, storing the relationships between each. [1] https://coderwall.com/p/lixing/closure-tables-for-browsing-t...
http://stackoverflow.com/questions/192220/what-is-the-most-e...
http://www.slideshare.net/billkarwin/models-for-hierarchical...
http://karwin.blogspot.in/2010/03/rendering-trees-with-closu...
Line from the page: "I just picked up a copy and it looks great! You are right about the whole approach and my stuff stinks." - Joe Celko, author of SQL for Smarties.
A good book on the subject is Joe Celko's Trees and Hierarchies in SQL for Smarties. http://www.amazon.com/Hierarchies-Smarties-Edition-Kaufmann-... He spends a chapter on each of the models outlined in this post: adjacency, path, and nested set models.
If you're using Rails (3.2 through 4.1), try this: http://mceachen.github.io/closure_tree/
Like it says in the README:
* Fetch your whole ancestor lineage in 1 SELECT. * Grab all your descendants in 1 SELECT. * Get all your siblings in 1 SELECT. * Fetch all descendants as a nested hash in 1 SELECT. * Find a node by ancestry path in 1 SELECT. * 2 SQL INSERTs on node creation * 3 SQL INSERT/UPDATEs on node reparenting
None of the other approaches above have even remotely similar performance characteristics. If your tree is small (tens of nodes), you won't care. If it's bigger, you will.
A good book on the subject is Joe Celko's Trees and Hierarchies in SQL for Smarties. http://www.amazon.com/Hierarchies-Smarties-Edition-Kaufmann-... He spends a chapter on each of the models outlined in this post: adjacency, path, and nested set models.
If you're storing a tree in an RDBMS, please look into the closure table algorithm rather than adjacency, nested set, or materialized paths. If you're using Rails (3.2 through 4.1), try this: http://mceachen.github.io/closure_tree/ Like it says in the README: * Fetch your whole ancestor lineage in 1 SELECT. * Grab all your descendants in 1 SELECT. * Get all your siblings in 1 SELECT. * Fetch all descendants as a nest…