Tree data structure storage method (query)

Adjacency list model

In daily business development, we often encounter some tree-like data with a hierarchical structure. When stored in a relational database, this data structure is often stored in a model called an adjacency list, like this:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `pid` int(11) DEFAULT 0,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

This model represents The picture shows:

# I believe many people are already familiar with this data model, so I won’t go into too much detail here. Let’s focus on the following data model

Nested set model

Another way to represent a tree is to store it as a set. We redefine the following table structure:

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `lft` int(11) NOT NULL UNIQUE CHECK (lft> 0),
  `rgt` int(11) NOT NULL UNIQUE CHECK (rgt> 1),
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

And the diagram of this model will look like the following:

lft and rgt is used as the boundary of the set. The greater the difference between the two, the larger the set and the more elements in it.

According to the subset, find the parent category

SELECT c2.* 
  FROM categories as c1, categories as c2
  WHERE c1.lft BETWEEN c2.lft and c2.rgt 
      AND c1.title = '华为';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  5 | Harmony OS  |  10 |  13 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

According to the parent, find all the subsets under it

SELECT c1.*
   FROM categories AS c1, categories AS c2
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
    AND c2.title = 'Smartphones';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  3 | Android     |   2 |   5 |
|  4 | iOS         |   6 |   9 |
|  5 | Harmony OS  |  10 |  13 |
|  6 | 小米        |   3 |   4 |
|  7 | iPhone      |   7 |   8 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

View the level of each category

 SELECT COUNT(c2.id) AS indentation, c1.title
  FROM categories AS c1, categories AS c2下周三we'fv
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
  GROUP BY c1.title
  ORDER BY c1.lft;
+-------------+-------------+
| indentation | title       |
+-------------+-------------+
|           1 | Smartphones |
|           2 | Android     |
|           3 | 小米        |
|           2 | iOS         |
|           3 | iPhone      |
|           2 | Harmony OS  |
|           3 | 华为        |
+-------------+-------------+

Advantages and Disadvantages

Adjacency List Model

The adjacency list model is easy to understand, and the code we need is also very simple.

But in most programming languages, it is slow and inefficient. This is mostly caused by recursion. We need to do a database query for each node in the tree.

This can make the function very slow when dealing with large trees since each query takes some time. Because for each function, a recursive algorithm is needed to obtain the number.

Of course, if you use a recursive-friendly language like List, you can ignore the shortcomings of this data model. But for PHP, it will make the entire processing of this data model extremely slow.

Nested set model

Compared with the adjacency list model, this data model is obviously not so easy to understand. And it cannot be so simple to add data. It needs to calculate the values ​​​​on the left and right sides when adding, and move the subsequent values, which increases the pressure of adding data.

Similarly, the benefit it brings is that it allows you to complete a tree query with a simple query, and you can calculate how many sub-elements it has based on the two parameters lft and rgt.

Summary

Both models have their own advantages and disadvantages, one is better than insertion and the other is better than query. Although I prefer the nested set model, it still needs to be chosen based on the specific business.

The above is the detailed content of Tree data structure storage method (query). For more information, please follow other related articles on the PHP Chinese website!