I know this is really an implementation detail and might not exactly be relevant for the runtime, but I've been working a lot on streamlining tree operations in sql server, and have begun to move away from the adjacency model which promotes recursive calls,
e.g., this is an example product category structure:
| Id | Name | ParentId |
| 1 | Foo | NULL |
| 2 | Bar | 1 |
With the adjacency model, if I need read a tree or sub-tree, I have to recursively select where ParentId = ?. The adjacency model works really well for maintaining trees, not so much for read operations.
With nested sets, we mark the extents of the sub-tree within the larger tree, e.g.:
| Id | Name | ParentId | Left | Right |
| 1 | Foo | NULL | 1 | 6 |
| 2 | Bar | 1 | 2 | 3 |
| 2 | Ner | 1 | 4 | 5 |
This is also know as Modified Preorder Tree Traversal (MPTT). This allows us to optimise read operations which are more likely to be far more frequent than write operations. The ParentId is there purely as a mechanism for simplifying some selects (e.g.. for
direct descendent, or possible to rebuild the tree if required. E.g, if I want to get the sub-tree of Foo, I would do the following:
SELECT c.Id, c.Name, c.ParentId
FROM dbo.Category c,
SELECT [Left], [Right] FROM dbo.Category p WHERE p.Id = <parent id here>
) AS p
WHERE c.[Left] >= p.[Left] AND c.[Right] <= p.[Right]
ORDER BY c.[Left], c.[Right]
Conversely, the operations to insert, delete and move items are a little trickier and we have to manage the [Left] and [Right] values accordingly, but the trade off I think personally is worth it, as we get the immediate benefits of a much quicker and performant
read operation, and the translation to a tree structure can happen in code, rather than spread between code and database. We bypass recursion completely.
Not sure if this is just an pipe dream, but it EF provided my built-in support for designing a tree structure and storing it in Sql Server, generating the underlying table structure and operations to read/write the tree, I'd be in developer heaven!