简介
在数据库设计中，经常会遇到需要存储多级分类信息的情况，如商品分类、地区分类等。本文将详细介绍如何在MySQL中设计和管理多级分类数据
解决方案
一. 层级字段（Hierarchy Field）方法
层级字段方法是最常见和简单的多级分类设计方法之一。它通过在分类表中添加一个表示层级关系的字段来实现。每个分类记录包含一个字段来表示其父级分类的ID
数据表结构
CREATE TABLE categories (
id INT PRIMARY KEY,
name VARCHAR(255),
parent_id INT,
level INT
);
-
id：分类ID，作为主键
-
name：分类名称
-
parent_id：父级分类的ID
-
level：分类所处的层级
数据插入
在向分类表中插入数据时，我们可以根据父级分类的ID来设置相应的层级字段和层级信息。
例如，插入三级分类数据的示例：
INSERT INTO categories (id, name, parent_id, level) VALUES
(1, '电子产品', NULL, 1),
(2, '手机', 1, 2),
(3, '平板电脑', 1, 2),
(4, '苹果手机', 2, 3),
(5, '华为手机', 2, 3),
(6, 'iPad', 3, 3),
(7, '安卓平板', 3, 3);
查询分类
使用层级字段方法，可以轻松地进行分类的查询。例如，要获取所有二级分类的手机列表，可以执行以下查询：
SELECT * FROM categories WHERE level = 2 AND parent_id = 1;
层级字段方法的优缺点
优点：
- 简单直观，易于理解和实现
- 查询和操作单个层级的分类很高效
缺点：
- 难以处理复杂的层级关系，如循环引用或动态变化的层级
- 查询多级分类和递归操作时，性能可能受到影响
- 从根节点进行递归查询，时间复杂度是 O(n)
二. MPTT预排序算法
什么是MPTT算法？
MPTT算法是一种用于处理树状结构数据的算法，其中MPTT代表Modified Preorder Tree Traversal（修改的先序遍历树遍历）。它通过为树中的每个节点分配一个预排序值来组织和表示树的结构。这种预排序值允许我们以一维的方式存储和操作树，同时保持树的层次结构和父子关系。
MPTT 正是为了解决多层级关系数据的查询效率问题，它的时间复杂度竟然能高效到一个常量，即
O(1)
MPTT算法的原理
MPTT算法的原理很简单，它通过以下几个步骤来为树节点分配预排序值：
- 初始化左值和右值为1
- 对树进行深度优先搜索（DFS）的先序遍历
- 遍历到一个节点时，将该节点的左值设为当前左值，并将当前左值加1
- 递归处理节点的每个子节点
- 当处理完所有子节点后，将节点的右值设为当前左值，并将当前左值加1
通过这个过程，我们可以为每个节点分配唯一的左值和右值，从而形成树的预排序遍历结构。
MPTT分析
以下是django-mptt模块定义的一个部门
from mptt.models import MPTTModel, TreeForeignKey
class Department(MPTTModel):
"""组织"""
name = models.CharField("组织名称", max_length=255)
# 部门标识，不同于自增 id，多数情况存储各个公司组织架构系统的id, 非必须
code = models.CharField("组织标识", null=True, blank=True, unique=True, max_length=64)
parent = TreeForeignKey("self", on_delete=models.CASCADE, null=True, blank=True, related_name="children")
order = models.IntegerField("顺序", default=1)
profiles = models.ManyToManyField(Profile, blank=True, related_name="departments", verbose_name="成员")
enabled = models.BooleanField("是否启用", default=True)
extras = JSONField("额外信息", default={})
category_id = models.IntegerField("用户目录ID", null=True, blank=True)
class Meta:
ordering = ["id"]
verbose_name = "组织表"
verbose_name_plural = "组织表"
index_together = [
["tree_id", "lft", "rght"],
["parent_id", "tree_id", "lft"],
]
在上述代码中，在进行数据库迁移后，数据库里面额外多出了 5个字段，分别是： lft、rgt、level、tree_id、parent_id。
这些多出来的字段就是为了定义树的结构和层级。下面我们就来分析一下，每个字段的作用是什么
- tree_id：树的 id，用来区分数据库中众多树的某一颗树。
- level：一颗标准的树会有高度、深度、层级，根节点的层级是 1，子节点的层级是父节点层级加 1
- parent_id：父 id，节点的父级 id，根节点没有父节点，所以值为 NULL
- lft：节点左值
- rgt：节点右值。
树结构如下：
查询
-
遍历整棵树：
遍历整棵树只需要查找 tree_id 等于 1 的条件即可 -
某节点下所有的子孙节点：
查找节点 4 的所有子孙节点，以 4 作为参考点。左值大于 6 且右值小于 11 的所有子孙节点，就是节点 4 的所有子孙节点。 -
找到某节点下所有的子节点
查找节点 1 的所有子节点，以 1 作为参考点。tree_id 等于 1 且 level 等于 2 -
查找某节点的路径
查找节点 9 的所有上级路径，以 9 作为参考点。左值小于 14 且右值大于 15 的所有节点，就是节点 “9的路径。结果是：1 -> 7 -> 8 -> 9`。
新增
MPTT 在遍历的时候很快，但是其他的操作就会变得很慢，所以使用 MPTT 要尽量避免查询之外的其他操作，这是因为节点在插入、更新（移动）、删除会破坏树的平衡。所以在做这些操作的时候需要对数进行调整，达到新的平衡
以新增节点操作为例，算法可分解为以下几个步骤：
- 如果要在不存在的树中新增节点，即要创建一颗新树。那么它是没有 parent_id 的，所以 parent_id 值为 NULL，level 是 1，tree_id 是根据已有树的最大 tree_id 加 1
- 如果要在已存在的树中新增节点。那么它的 parent_id 是父节点的 id，level 是父节点的 level 加 1，tree_id 和父节点保持一致。
- 修复被破坏平衡的其他节点的左值。大于 parent_id 右值的所有节点的左值加 2
- 修复被破坏平衡的其他节点的右值。大于等于 parent_id 右值的所有节点的右值加 2
删除
和增加类似，只不过删除一个节点以后对左值和右值进行相反的操作，即减 2
更新
更新（移动）其实就是删除一个老节点，再新增一个新节点，具体算法参考上面的例子
MPTT预排序算法优缺点
优点：
- 查询操作较多的场景，查询的效率不受分类层级的增加的影响，为o(1)
缺点：
- 随着数据的增多，每增删数据，都要同时操作多条受影响数据，执行效率逐渐下降