16 ms·

I've written an implementation of nested sets for at least 3 DB engines over the years (SQL Server, MySQL and PostgreSQL). Some of that article is plainly dang

I've written an implementation of nested sets for at least 3 DB engines over the years (SQL Server, MySQL and PostgreSQL). Some of that article is plainly dangerous and I wouldn't recommend following it without some extensive research elsewhere. SQL for Smarties is the usual reference. Firstly they seem to insist on MyISAM which is just crap. I don't need to cite any references on that. Secondarily, they use LOCK TABLE whilst modifying the data. That basically blocks other writes yet doesn't give any transactional capabilities. Due to the denormalised nature of the nested set implementation, you NEED transactions to ensure operations are ACID compliant or you risk tree corruption. Thirdly, they do not discuss in detail the performance constraints of nested sets i.e. it is purely a read-optimised. When nested sets start growing in node count, the modification operations do not scale as a significant chunk of the tree needs to be renumbered inside a transaction.

NyxWulf 17y ago
I've done the same, and I agree with your post entirely. There are a few tricks to making nested sets perform reasonably well on large data sets. I've tested this model on trees that contain up to 100 million items within the scope of a single tree, and I have a pretty good feel for how well it would perform beyond that. - The first and most important consideration is what defines the scope of a tree. For example, if you are building a discussion board, and using nested sets (I've done this) you would want each post/reply set to be a separately scoped tree. That decision alone vastly reduces much of the write contention. - Next, if the tree is going to be heavily used, store the tree in a separate table with each row fixed width and the primary key of the item it refers to. Databases are much more efficient at reads and writes when rows are fixed width and do not contain nullable or variable length data. - Additionally it's important to maintain the data for the adjacency list within your structure, so that if you ever have errors or corruptions with your tree, you can rebuild it correctly. - Next if you need to insert some type of sub-tree into a larger tree. You can compute the sub-tree and then insert it into the larger tree in a single operation, instead of doing multiple inserts that lock the entire tree. This is a relatively difficult optimization and something I don't typically build until it becomes necessary. - Spend some time working through the math of how Nested Sets work. It's relatively simple, and really understanding it will help you implement efficient bulk operations on your trees. - It's important to get a write lock on the tree before you get your left and right values for the tree. If you get your left and write values before you get exclusive access to the data you are working with, someone else could have done an insert while you were building your tree, and when you do your insert, you will have corrupted the entire tree. - Finally if you are interested in this topic, I cannot recommend Joe Celko's books highly enough. SQL For Smarties has a thorough discussion of the different models. Additionally he has a separate book that only deals with Hierarchical data models, and he delves further into the various issues and implementation tricks with these data structures.
- smithjchris 17y ago
  Some excellent suggestions there. Many thanks :-)

NyxWulf 17y ago

I've done the same, and I agree with your post entirely. There are a few tricks to making nested sets perform reasonably well on large data sets. I've tested this model on trees that contain up to 100 million items within the scope of a single tree, and I have a pretty good feel for how well it would perform beyond that. - The first and most important consideration is what defines the scope of a tree. For example, if you are building a discussion board, and using nested sets (I've done this) you would want each post/reply set to be a separately scoped tree. That decision alone vastly reduces much of the write contention. - Next, if the tree is going to be heavily used, store the tree in a separate table with each row fixed width and the primary key of the item it refers to. Databases are much more efficient at reads and writes when rows are fixed width and do not contain nullable or variable length data. - Additionally it's important to maintain the data for the adjacency list within your structure, so that if you ever have errors or corruptions with your tree, you can rebuild it correctly. - Next if you need to insert some type of sub-tree into a larger tree. You can compute the sub-tree and then insert it into the larger tree in a single operation, instead of doing multiple inserts that lock the entire tree. This is a relatively difficult optimization and something I don't typically build until it becomes necessary. - Spend some time working through the math of how Nested Sets work. It's relatively simple, and really understanding it will help you implement efficient bulk operations on your trees. - It's important to get a write lock on the tree before you get your left and right values for the tree. If you get your left and write values before you get exclusive access to the data you are working with, someone else could have done an insert while you were building your tree, and when you do your insert, you will have corrupted the entire tree. - Finally if you are interested in this topic, I cannot recommend Joe Celko's books highly enough. SQL For Smarties has a thorough discussion of the different models. Additionally he has a separate book that only deals with Hierarchical data models, and he delves further into the various issues and implementation tricks with these data structures.

smithjchris 17y ago
Some excellent suggestions there. Many thanks :-)