How to design database tables for hierarchical data with unknown depth?

Question

I want to create hierarchical data with unknown depth like this:

Create categories and sub categories and for those subcategories they will have also subcategories and so on.

The depth of the subcategories is unknown and only will be done in the runtime by the user.

What I though about is to but them all in one table and have a parent column holding the ID of the parent category like this:

I don't know if this is the right way to do it, but I can't see any other way.

I have did a quick search and what I have found is not directly related to DB table design.

I am using MS SQL Server 2012

Answer 1

There are 3 common approaches to this & 1 not so common.

1. Adjacency lists (your approach) Pro - easy to understand, fast inserts anywhere Con - slow to query trees of unknown depth recursively

2. Nested sets Pro - fast to query Con - Inserts in middle of list are slow

3. Path - like hierarchyid (basically a binary path) Pro - fast Con - like hierarchyid usually have limited length - i think hierarchyid is about 892 bytes max

4. Closure table Pro - Best of nested sets & adjacency lists. Fast inserts & selects. Con - A bit hard to get your head around at first but worth the effort if performance is an issue

Source: SQL Antipatterns - Bill Karwin

Answer 2

The most widely used design pattern for represnting hierarchies in tables is called "Adjacency List". This is the pattern you've presented in the question.

One alternative is called "Nested Sets". Here is a description of Nested Sets in a nutshell: https://en.wikipedia.org/wiki/Nested_set_model

If you look up Adjacency List vs Nested Set, you'll get a lot of articles discussing the trade offs between the two.

Basically, Adjacency list is easy to update, but hard to work with, except for the most basic operations. nested Set is hard to update, but easy to work with. Operations like find the path from the root, find the sub tree are strightforward and well understood.