How does hierarchyid data type work?

Question

I would like to make a CLR user-defined type in SQL Server 2005 that has the same performance benefits as hierarchyid to model hierarchies.

Does anyone have any ideas/pointers?

Answer 1

SQL Server encodes a hierarchyid using a encoding based on, but different from, ORDPATH.

You can find the “physical representation” of hierarchyid in [MS-SSCLRT]: Microsoft SQL Server CLR Types Serialization Formats. To summarize:

1. Encode each number n in the hierarchyid as a bit string using a variable-length encoding. If a . follows n in the hierarchyid, encode n+1 instead of n.

   The length of the bit string doesn't have to be a multiple of eight!

   The details of the encoding are too long to include here. Note that the encoding must support negative integers, zero, and positive integers. It must also be order-preserving. That is, for integers a and b with encodings e(a) and e(b), if a > b, then e(a) > e(b) (when the encodings are compared lexicographically).

2. Append a 1 to the bit string if a / follows the number. Append a 0 to the bit string if a . follows the number.

3. Concatenate all the bit strings.

4. Append 0s to the result of step 3 until the length is a multiple of 8. (If it was already a multiple of 8, you won't append any 0s here.)

Answer 2

I found it - how hierarchyId is implemented. It's a slick bit-twiddling algorithm called ORDPATH.

http://www.cs.umb.edu/~poneil/ordpath.pdf

(via: http://sqlkpi.com/BLOGS/BOBB/post/ORDPATH-ORDPATH-everywhere.aspx)

This could be an interesting side-project.