• HLogic (8/21/2012)


    For hierarchies of < 50 levels depth, Nested Intervals (Hazel) may be of interest.

    I consider those just a flavor of Nested Sets. It has the one advantage that it doesn't require expanding the range at the top level when you insert at lower levels, while trading that off for complexity of implementation, difficulty in inserting nodes between other nodes at lower levels (requires recomputation of all sub-nodes that are shifted to the right; both version have this issue), difficulty for human data-verification (requires fairly complex math to visually validate the tree composition), and problems with rounding errors towards the bottom of the hierarchy if depth is greater than a certain level (depending on the data type used, this can happen shallower or deeper in the hierarchy).

    It retains the query speed of Nested Sets, since it's a single index scan (usually a range scan rather than a full scan) to resolve the most common hierarchy queries. Per my tests (admittedly limited), the HierarchyID datatype has query speed that's in the same range, can handle deeper hierarchies (it can only go 892 bytes deep, but that's a lot of hex values), and is faster and easier to edit.

    For hierarchies too deep for HierarchyID, I'd probably go breadcrumb/path, if query speed matters more than storage size, or Nested Sets if the hierarchy is relatively static.

    - Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
    Property of The Thread

    "Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon