Linq to SQL Nested Objects

There is another way to store/retrieve a tree hierarchy as explained in this fogbugz blog post:

Turns out there's a pretty cool solution for this problem explained by Joe Celko. Instead of attempting to maintain a bunch of parent/child relationships all over your database -- which would necessitate recursive SQL queries to find all the descendents of a node -- we mark each case with a "left" and "right" value calculated by traversing the tree depth-first and counting as we go. A node's "left" value is set whenever it is first seen during traversal, and the "right" value is set when walking back up the tree away from the node. A picture probably makes more sense:

The Nested Set SQL model lets us add case hierarchies without sacrificing performance.

How does this help? Now we just ask for all the cases with a "left" value between 2 and 9 to find all of the descendents of B in one fast, indexed query. Ancestors of G are found by asking for nodes with "left" less than 6 (G's own "left") and "right" greater than 6. Works in all databases. Greatly increases performance -- particularly when querying large hierarchies

Here's another post going into more detail. It's written using Sql and php but I think you can get the gist of it and easily translate in Linq to Sql.

In MS SQL 2005 and up you can create recursive queries. In LINQ to SQL however, you are out of luck. Without restructoring the data in the database, there is no way you can traverse the tree in a single database call.

However... there is 1 workaround I can think of. When you are able to group all Category elements of a single tree (or a part of the tree) together, you can pre-load that part of the complete tree in a single statement. After that, you will be able to traverse that part of the tree, without triggering new calls to the database. It would look something like this:

// Load the category that will be used as starting point.
var subCategory = db.Categories.Single(c => c.Id == 56);

// Performance: Load the complete group in one go.
var categories = (
    from category in db.Categories
    where category.GroupId == subCategory.GroupId
    select category)
    .ToArray();

// Traverse the tree and get the top-most parent (if any).
var parent = subCategory.GetParents().LastOrDefault();

// Extension method to get the parents.
public static IEnumerable<Category> GetParents(
    this Category category)
{
    while (category.Parent != null)
    {
        // NOTE: cat.Parent will not cause a database call
        // when the Parent is already loaded by L2S.
        yield return cat.Parent;
        category = category.Parent;
    }
}

This of course will only work if you will be able to determine elements as a group. Whether this solution will be faster also depends on the size of the group. When the group of objects that you load (and don't use) is very big, it will actually slow the application down.