树形结构数据
在Web开发中经常遇到树形数据的操作，如菜单、组织机构、行政区(省、市、县)等具有层级关系的数据。在数据结构和数据库设计中，处理树形结构数据时，有几种常见的方法，包括邻接表、嵌套集（Nested Set）、左右值编码（Left-Right Encoding）和全路径（Full Path）等。这些方法各有特点，适用于不同的应用场景。
-
邻接表（Adjacency List）：
邻接表是一种图的数据结构，用于表示图中顶点之间的关系。在树形结构的表示中，邻接表可以清晰地展示节点之间的父子关系。每个节点都有一个列表，存储它的直接子节点的信息。这种方法实现简单，易于理解和操作，但在进行树的相关操作时可能效率较低，因为需要频繁地进行递归查询。 -
嵌套集（Nested Set）：
嵌套集通过为每个节点分配两个数字（左值和右值），这两个数字定义了一个节点在其父节点下的位置。这种方法通过维护一个有序的节点序列，使得查询子节点、祖先节点等操作变得非常高效，因为可以直接通过数字比较来完成。但是，嵌套集的更新操作相对复杂，因为每次节点的移动都会影响多个节点的左值和右值。 -
左右值编码（Left-Right Encoding）：
左右值编码为每个节点增加左右值，这些值通过前序遍历算法分配，形成了一个有序的节点序列。这种方法同样使得查询子节点、祖先节点等操作高效，并且避免了递归查询的效率问题。但是，更新操作同样复杂，因为需要调整多个节点的左右值。 -
全路径（Full Path）：
全路径方法将节点的完整路径存储在每个节点中，这样可以直接通过路径找到任何节点，无需进行复杂的查询操作。这种方法在处理某些特定问题时非常有效，但存储每个节点的完整路径可能会占用较多的存储空间，并且在大型树中维护路径的更新可能会变得复杂和低效。
1.邻接表
1.1. 实现方式
- 每个记录增加一个 parent_id; [id, parent_id]
| id | name | parent_id |
|---|---|---|
| 1 | 华府 | |
| 2 | 华太师 | 1 |
| 3 | 华夫人 | 1 |
1.2. 优点/缺点
- 查询所有子节点：需要递归
- 树形形遍历：需要递归
- 插入：简单
- 删除：需要递归删除
- 移动：简单
- 冗余：无
- 是否有层级限制：无
2.嵌套表(闭包表)
2.1. 实现方式：
1.主表：[id, parent_id]
| id | name | parent_id |
|---|---|---|
| 1 | 华府 | |
| 2 | 华太师 | 1 |
| 3 | 华夫人 | 1 |
| 4 | 武状元 | 2 |
| 5 | 管家 | 2 |
| 6 | 华安 | 5 |
2.嵌套子表：[id, food_id, parent_id]
| id | parent_id | foot_id |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 1 | 3 |
| 3 | 1 | 4 |
| 4 | 1 | 5 |
| 5 | 1 | 6 |
| 6 | 2 | 4 |
| 7 | 2 | 5 |
| 8 | 2 | 6 |
| 9 | 5 | 6 |
2.2. 优点/缺点
- 查询所有子节点：简单，需要关联表
- 树形形遍历：需要递归
- 新增：一般，需要更新嵌套表
- 删除：一般，需要更新嵌套表
- 移动：一般，需要更新嵌套表
- 冗余：数据冗余，需要额外的存储空间(Cn2:C(n,2))，随着层级的增加，所需空间迅速增加
- 是否有层级限制：无
具体说明：
优点：
- 查询、删除一个表下所有子节点方便，select foot_id from table_name where parent_id = x;
缺点：
- 需要额外的存储空间(Cn2:C(n,2))，随着层级的增加，所需空间也增加。
- 新增、删除需要额外的维护关系的成本。