Shawn Dube (8/20/2012)
Thanks for this article and the original! One question though... have you tried a very deep hierarchy on any of your methods? Like a million node binary tree (not necessarily balanced)? Something where one "leg" of the tree is a few thousand nodes deep?
Just wondering what limitations may creep up.
Greatly appreciate your work!
The deepest real-world hierarchies I'm used to seeing are certain multi-level-marketing companies. Those can get pretty deep.
Adjacency queries turn into nightmares on that kind of data. After all, they have to do a scan for every level, and deep hierarchies are (by their very nature) large tables.
Nested Sets are still nearly instantaneous to query. If it's a lot of rows of data, returning the dataset to the client and rendering it will be your performance issue on those. No matter how deep a Nested Set hierarchy is, querying one is simply a single scan. If you haven't indexed the necessary columns, that might be a problem, but that's not likely to come up since the hierarchy data is likely to be the clustered index on a hierarchy table.
Hierarchy ID works like nested sets. On deep queries, it's still very fast. If you look into the way they get stored and indexed, which is as a binary string, that makes sense. After all, 0x1 and all it's children nodes, 0x102, 0x1F3, and so on, are all in the same range. It's like looking up all the names that start with "A" in the phone book.
Updates are the same as in the examples in the article. Adjacency, you just update one row and you're done. Should be so fast, even on a million-rows deep, that you can't measure the time taken. Nested Sets, you rebuild the table, and that takes lots of time. Hierarchy ID, you have to update every child, so you're doing a million-row update, and that won't be fast and might take a fair chunk of disk space in both tempdb and your log file. It'll be massively faster than a Nested Sets update, and a lot easier to do, but it will be slow compared to Adjacency.
- 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