3 ms·

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 a

by platz 12y ago

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.

tempVariable 12y ago
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!
- alistairbayley 12y ago
  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.htm 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 https://communities.bmc.com/docs/DOC-9902 And a paper: http://www.sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdf 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-nested-intervals-vs-adjacency-list-comparison/ http://vadimtropashko.wordpress.com/2008/08/09/one-more-nest...
rickmode 12y ago
One just needs to be aware that nested sets eventually hit a limit. 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”-book/ http://vadimtropashko.wordpress.com/“sql-design-patterns”-bo...

by platz 12y ago

tempVariable 12y ago

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!

alistairbayley 12y ago
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.htm 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 https://communities.bmc.com/docs/DOC-9902 And a paper: http://www.sigmod.org/publications/sigmod-record/0506/p47-article-tropashko.pdf 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-nested-intervals-vs-adjacency-list-comparison/ http://vadimtropashko.wordpress.com/2008/08/09/one-more-nest...

rickmode 12y ago

One just needs to be aware that nested sets eventually hit a limit. 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”-book/ http://vadimtropashko.wordpress.com/“sql-design-patterns”-bo...