How is HierarchyId stored in SQL Server?

Question

I have a hierarchyid with the value '/1/'. When I insert it into the SQL Database it's stored as 0x58.

Here is my table:

CREATE TABLE [dbo].[Category](
    [CategoryId] [int] IDENTITY(1,1) NOT NULL,
    [Name] [nvarchar](max) NULL,
    [HierarchyDescription] [hierarchyid] NULL,
 CONSTRAINT [PK_Category] PRIMARY KEY CLUSTERED 
(
    [CategoryId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]

And here is how I do it:

INSERT INTO [dbo].[Category] ([Name] ,[HierarchyDescription])
VALUES ('CAT1', '/1/');

How is the value 0x58 obtained?

I tried doing this in C#

Encoding.ASCII.GetBytes("/1/");

And I got the value 0x2F312F (47 49 47) in Hex.

Answer 1

HierarchyId is documented as Extremely compact

The average number of bits that are required to represent a node in a tree with n nodes depends on the average fanout (the average number of children of a node). For small fanouts (0-7), the size is about 6*logAn bits, where A is the average fanout. A node in an organizational hierarchy of 100,000 people with an average fanout of 6 levels takes about 38 bits. This is rounded up to 40 bits, or 5 bytes, for storage.

So it is clear that it can manage to fit more than one level in a byte.

The internal format isn't documented but someone has previously investigated this (way back machine link as the original page didn't load when I looked at it).

Disclaimer: The source in itself is non authoritative and just deduced from inspection of values and I may have introduced further errors in the below!

The below gives some fairly simple examples

WITH HierarchyIdStrings(path) As
(
SELECT '/'  UNION ALL
SELECT '/0/'  UNION ALL
SELECT '/1/'  UNION ALL
SELECT '/1/1/'  UNION ALL
SELECT '/1.1/'  UNION ALL
SELECT '/2/'    UNION ALL
SELECT '/98/'  
)
SELECT HierarchyId::Parse(path) AS HierarchyId, path, 
bin,
trimmed_bin = LEFT(bin, 1 + LEN(bin) - CHARINDEX('1', REVERSE(bin)))
FROM HierarchyIdStrings
CROSS APPLY(SELECT CONVERT(VARCHAR(1784), CAST(HierarchyId::Parse(path) AS VARBINARY(892)), 2)) V1(hex)
CROSS APPLY (SELECT 
REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(REPLACE(
hex,
 '0', '0000'),'1', '0001'),'2', '0010'),'3', '0011'),
 '4', '0100'),'5', '0101'),'6', '0110'),'7', '0111'),
 '8', '1000'),'9', '1001'),'A', '1010'),'B', '1011'),
 'C', '1100'),'D', '1101'),'E', '1110'),'F', '1111') ) V2(bin)
 ORDER BY HierarchyId

Results

+-------------+-------+--------------------------+--------------------+
| HierarchyId | path  |           bin            |    trimmed_bin     |
+-------------+-------+--------------------------+--------------------+
| 0x          | /     |                          |                    |
| 0x48        | /0/   |                 01001000 |              01001 |
| 0x58        | /1/   |                 01011000 |              01011 |
| 0x5AC0      | /1/1/ |         0101101011000000 |         0101101011 |
| 0x62C0      | /1.1/ |         0110001011000000 |         0110001011 |
| 0x68        | /2/   |                 01101000 |              01101 |
| 0xE02540    | /98/  | 111000000010010101000000 | 111000000010010101 |
+-------------+-------+--------------------------+--------------------+

The binary representation of 0x58 is 01011000 but trailing zeroes should be ignored so we only have 5 bits to care about. 01011.

The linked article supposes that the initial prefix 01 is reserved for components /0/ ... /3/ so it knows it only has to read three more bits for this component. The next two bits are for the value itself and the final bit is 1 because this is not a dotted component.

The representation of /1/1/ just concatenates two of these together.

The representation of 1.1 adds 1 to 01011 to get 01100 then concatenates a 01011 onto the end of that.

/98/ is more complicated. This gives a bit string of 111000000010010101.

The linked article indicates that the range /80/ through /1103/ will have the prefix 1110 and be in the form 1110aaa0zzz0y1xxx1

• aaa = 000 (decimal 0)
• zzz = 001 (decimal 1)
• y = 0 (decimal 0)
• xxx = 010 (decimal 2)

1x + 8y + 16z + 80 = 2 + 0 + 16 + 80 = 98

There is also the possibility that the component may have a negative number. See the linked article if interested in that!

Answer 2

I solved it by doing the following, there may be a better way

hierarchyValue = "/1/";
MemoryStream memStream = new MemoryStream();
BinaryWriter binWriter = new BinaryWriter(memStream);
hierarchyValue.Write(binWriter);
byte[] propertyValue = memStream.ToArray();

The value stored in the database for the HierarchyId is propertyValue