A brief analysis and sharing of the advantages and disadvantages of three tree structure table designs in MYSQL

Introduction

In development, we often encounter tree-structured scenarios. This article will use the department table as an example to compare the advantages and disadvantages of several designs.

question

Demand background : Search personnel by department.
Question : When selecting a top-level department, how can the table be designed to display all personnel in the current department and its sub-departments across levels?

Recursion? Recursion can solve this problem, but it will inevitably consume performance

Design 1: Adjacency List

Note: (Common parent ID design)

Table Design

CREATE TABLE `dept_info01` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT 'Auto-increment primary key',
  `dept_id` int(10) NOT NULL COMMENT 'Department id',
  `dept_name` varchar(100) NOT NULL COMMENT 'Department name',
  `dept_parent_id` int(11) NOT NULL COMMENT 'Parent department id',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT 'Creation time',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT 'modification time',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

This is the most common design, which can correctly express the tree structure of the menu without redundant data, but cross-level queries require recursive processing.

SQL Examples

1. Query the direct subset of a node

SELECT * FROM dept_info01 WHERE dept_parent_id = 1001

advantage

Simple structure;

shortcoming

1. It is impossible to query all parents and all children of a node without recursion

Design 2: Path Enumeration

Based on Design 1, a parent department ID set field is added to store all parent sets, with multiple sets separated by fixed delimiters, such as commas.

Table Design

CREATE TABLE `dept_info02` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT 'Auto-increment primary key',
  `dept_id` int(10) NOT NULL COMMENT 'Department id',
  `dept_name` varchar(100) NOT NULL COMMENT 'Department name',
  `dept_parent_id` int(11) NOT NULL COMMENT 'Parent department id',
  `dept_parent_ids` varchar(255) NOT NULL DEFAULT '' COMMENT 'Parent department id set',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT 'Creation time',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT 'modification time',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

SQL Examples

1. Query all subsets
1). Through fuzzy query

SELECT
 *
FROM
	dept_info02
WHERE
	dept_parent_ids like '%1001%'

2). It is recommended to use the FIND_IN_SET function

SELECT
	* 
FROM
	dept_info02 
WHERE
	FIND_IN_SET( '1001', dept_parent_ids )

advantage

• Convenient to query all subsets;
• Therefore, the current node level can be obtained by comparing the length of the string dept_parent_ids;

shortcoming

• When adding a new node, the dept_parent_ids field value needs to be processed properly;
• The length of the dept_parent_ids field is difficult to determine. No matter how large the length is, it cannot be infinitely extended.
• Point movement is complex and requires changing the dept_parent_ids field value in all subsets at the same time;

Design 3: Closure Table

• Closure tables are a simple and elegant solution to the problem of hierarchical storage, a way of trading space for time;
• An additional TreePaths table needs to be created, which records the relationship between all nodes in the tree;
• Contains two columns, ancestor column and descendant column, even if there is no direct parent-child relationship between the two nodes; and also adds a row pointing to the node itself;

Table Design

Main table

CREATE TABLE `dept_info03` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT 'Auto-increment primary key',
  `dept_id` int(10) NOT NULL COMMENT 'Department id',
  `dept_name` varchar(100) NOT NULL COMMENT 'Department name',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT 'Creation time',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT 'modification time',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

Ancestor-Descendant Relationship Table

CREATE TABLE `dept_tree_path_info` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT 'Auto-increment primary key',
  `ancestor` int(10) NOT NULL COMMENT 'ancestor id',
  `descendant` int(10) NOT NULL COMMENT 'descendant id',
  `depth` tinyint(4) NOT NULL DEFAULT '0' COMMENT 'Level depth',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

Note: depth is the level depth field. The self-reference is 1, the direct child node is 2, the next level is 3, and so on. The level is the same as the level.

SQL Examples

Inserting a new node

INSERT INTO dept_tree_path_info (ancestor, descendant, depth)
SELECT t.ancestor, 3001,t.depth+1 FROM dept_tree_path_info AS t 
WHERE t.descendant = 2001
UNION ALL
SELECT 3001,3001,1

Query all ancestors

SELECT
	c.*
FROM
	dept_info03 AS c
INNER JOIN dept_tree_path_info t ON c.dept_id = t.ancestor
WHERE
	t.descendant = 3001

Query all descendants

SELECT
	c.*
FROM
	dept_info03 AS c
INNER JOIN dept_tree_path_info t ON c.dept_id = t.descendant
WHERE
t.ancestor = 1001

Delete all subtrees

DELETE 
FROM
	dept_tree_path_info 
WHERE
	descendant IN 
	( 
		SELECT
			a.dept_id 
		FROM
		( SELECT descendant dept_id FROM dept_tree_path_info WHERE ancestor = 1001 ) a
	)

Delete leaf nodes

DELETE 
FROM
	dept_tree_path_info 
WHERE
	descendant = 2001

Mobile Node

• Delete all subtrees (disconnect from the original ancestor first)
• Building new relationships

advantage

• Non-recursive queries reduce redundant computation time;
• Convenient non-recursive query of all parent sets of any node;
• It is convenient to query all subsets of any node;
• Unlimited levels can be achieved;
• Support mobile nodes;
  

shortcoming

• When there are too many levels, moving tree nodes will result in multiple operations on the relationship table;
• A separate table is needed to store the corresponding relationship, and the operation is relatively complicated when adding and editing nodes;

Use in combination

The adjacency list method can be combined with the closure table method. In fact, the parent ID is redundantly added to the main table. In some businesses that only need to query direct relationships, the main table can be queried directly without linking two tables. The ancestor-descendant relationship table is particularly important when cross-level queries are required.

Table Design

Main table

CREATE TABLE `dept_info04` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT 'Auto-increment primary key',
  `dept_id` int(10) NOT NULL COMMENT 'Department id',
  `dept_name` varchar(100) NOT NULL COMMENT 'Department name',
  `dept_parent_id` int(11) NOT NULL COMMENT 'Parent department id',
  `create_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT 'Creation time',
  `update_time` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT 'modification time',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

Ancestor-Descendant Relationship Table

CREATE TABLE `dept_tree_path_info` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT COMMENT 'Auto-increment primary key',
  `ancestor` int(10) NOT NULL COMMENT 'ancestor id',
  `descendant` int(10) NOT NULL COMMENT 'descendant id',
  `depth` tinyint(4) NOT NULL DEFAULT '0' COMMENT 'Level depth',
  PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

Summarize

In fact, in my previous work, I have seen different types of designs, including adjacency lists, path enumeration, and adjacency lists and path enumeration together. Each design has its own advantages and disadvantages, and the design you choose depends on which operations in your application need the most performance optimization.

In summary

• You only need to establish the child-parent set relationship and use the adjacency list method;
• For upward and downward searches, it is recommended to use the closure table method;

This concludes this article on the analysis and sharing of the advantages and disadvantages of three designs of tree-structured tables in MYSQL. For more relevant MYSQL tree-structured table content, please search for previous articles on 123WORDPRESS.COM or continue to browse the following related articles. I hope everyone will support 123WORDPRESS.COM in the future!