Indexes and Nested Sets

Question

I am using a nested set to represent a hierarchy in my application, and am wondering where the best place to put indexes (clustered or otherwise) is. I am using Microsoft SQL Server 2008.

Operations:

1. About 40 times a day, a new hierarchy will be added just off the root.
2. Hierarchies will probably never be deleted.
3. Hierarchies are accessed often during the day by parentId to incrementally fill combo boxes.
4. Hierarchies are VERY rarely moved. Perhaps not even once a month.
5. Biggest access is via left and right when linking with other tables. This is by far the most frequent access against the hierarchy.

I toyed with putting a clustered index on left and right (as the majority of the time, it will be queried with a val BETWEEN @left AND @right. But is clustering on left and right the correct way to go about it?

Many thanks in advance to anyone with more experience of SQL indexes than I!

Schema as it stands

_id       INT IDENTITY NOT NULL
_idParent INT IDENTITY NULL
_name     NVARCHAR(64)
_left     INT NOT NULL
_right    INT NOT NULL

Answer 1

Your best bet is to test various index configurations and just see which works best. At first glance though, clustered on lft and rgt seems like it would be best. It sounds like there isn't much DML on the table, so it shouldn't have to rearrange the data very often and the clustered index on lft and rgt should turn most of your queries into clustered index scans/seeks.

The only downside that I see is that if you're putting hierarchies right below the root then it might involve moving a lot of other hierarchies as well. Will you always be adding onto the "right" side of the root? That would only involve updating the rgt column in the root row, which would be good. If you add into the middle of the left side of the root then you'll have to shift over all other hierarchies to the right of the new one. Also, how large is your table? That will have some affect on things. If it's small enough then shifting those hierarchies might not be a big deal anyway. You definitely want to try to insert onto the right side of the root if you can though.

EDIT: One other thing... have you looked into the SQL Server built-in hierarchyid data type?