Search code examples
mysqlnested-set-modeladjacency-list-model

Adjacency List Model vs Nested Set Model for MySQL hierarchical data?

There are two ways to work with hierarchy data in MySQL:

  1. Adjacency List Model
  2. Nested Set Model

A major problem of the Adjacency List Model is that we need to run one query for each node to get the path of the hierarchy.

In the Nested Set Model this problem does not exist, but for each added node is necessary to give a MySQL UPDATE on all others left and right value.

My hierarchical data is not static data, such as product categories of e-commerce. Are constant registration of users in hierarchical sequence.

In my application, while there are many constants users registration, I also need to get the hierarchical path until reach the first node in the hierarchy.

Analyzing my situation, which of the two alternatives would be best for my application?

Solution

  • The Nested Set Model is nowdays not commonly used in databases, since it is more complex than the Adiacency List Model, given the fact that it requires managing two “pointers” instead of a single one. Actually, the Nested Set Model has been introduced in databases when it was complex or impossible to do recursive queries that traversed a hierarchy.

    From 1999, standard SQL include the so called Recursive Common Table Expressions, or Recursive CTE, which makes more simple (and standardized!) to make queries that traverse recursive path within a hierarchy with any number of levels.

    All the major DBMS systems have now included this feature, with a notably exception: MySQL. But in MySQL you can overcome this problem with the use of stored procedures. See, for instance, this post on StackOverflow, or this post on dba.stackexchange.

    So, in summary, these are my advices:

    1. If you can still decide which DBMS use, consider strongly some alternatives: for instance, if you want to stick with an open source database, use PostgreSQL, use the Adiacency List Model, and go with Recursive CTEs for your queries.
    2. If you cannot change the DBMS, still you should go with the Adiacency List Model, and use stored procedures as those cited in the references.

    UPDATE

    This situation is changing with MySQL 8, which is currently in developement and which will integrate Recursive CTEs, so that from that version the Adiacency List Model will be more simple to use.