理解树形结构数据的操作（上）

树形结构数据 

        在Web开发中经常遇到树形数据的操作，如菜单、组织机构、行政区(省、市、县)等具有层级关系的数据。在数据结构和数据库设计中，处理树形结构数据时，有几种常见的方法，包括邻接表、嵌套集（Nested Set）、左右值编码（Left-Right Encoding）和全路径（Full Path）等。这些方法各有特点，适用于不同的应用场景。

1. ‌邻接表（Adjacency List）‌：

           邻接表是一种图的数据结构，用于表示图中顶点之间的关系。在树形结构的表示中，邻接表可以清晰地展示节点之间的父子关系。每个节点都有一个列表，存储它的直接子节点的信息。这种方法实现简单，易于理解和操作，但在进行树的相关操作时可能效率较低，因为需要频繁地进行递归查询‌。

2. ‌嵌套集（Nested Set）‌：

           嵌套集通过为每个节点分配两个数字（左值和右值），这两个数字定义了一个节点在其父节点下的位置。这种方法通过维护一个有序的节点序列，使得查询子节点、祖先节点等操作变得非常高效，因为可以直接通过数字比较来完成。但是，嵌套集的更新操作相对复杂，因为每次节点的移动都会影响多个节点的左值和右值‌。

3. ‌左右值编码（Left-Right Encoding）‌：

           左右值编码为每个节点增加左右值，这些值通过前序遍历算法分配，形成了一个有序的节点序列。这种方法同样使得查询子节点、祖先节点等操作高效，并且避免了递归查询的效率问题。但是，更新操作同样复杂，因为需要调整多个节点的左右值‌。

4. ‌全路径（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))，随着层级的增加，所需空间也增加。
• 新增、删除需要额外的维护关系的成本。