分类目录接口

考虑到文章、题目类型进行分类会提高便利性，故设置了分类目录。

使用了预排序遍历树MPTT。

[1]Monika Handayani,Muhammad Hendra,Muhammad Bahit,Noor Safrina. Traversal Tree Implementation in Chart of Account Design[P]. 1st Annual Management, Business and Economic Conference (AMBEC 2019),2020.

我的理解是利用了DFS的括号化定理：

在有向图G中进行DFS。记节点发现时间为

d

、节点结束搜索时间为

f

，对于搜索过程中的任意两个节点

u

和

v

满足三种情况之一：

[u . d, u . f]

与

[v . d, v . f]

区间不重合，两个节点不存在父子关系；

[u . d, u . f]

在

[v . d, v . f]

区间内部，

u

是

v

的后代；

[v . d, v . f]

在

[u . d, u . f]

区间内部，

v

是

u

的后代 .

数据库表设计：

Service类：

3.1 所有目录

由于目录是查询较多、改动较少的数据。每次查询时重新组织目录树结构会带来不必要的时间消耗，故使用Cache Aside机制，将目录树结构存储至Redis。

先从缓存中读取数据，如果没有就再去数据库里面读数据，然后把数据放回缓存中，如果缓存中可以找到数据就直接返回数据；更新数据的时候先把数据持久化到数据库，然后再让缓存失效。

可以考虑的问题：
Cache Aside的安全性；热点数据的过期

100个线程循环10次，JMeter测试结果如下，可以看出使用Redis缓存数据的性能要远优于重复使用MySQL查询与组织数据。

生成目录树，通过parentID找到该节点的所有子节点，再递归找到子节点的所有子节点：

注意：categoryID才是分类的唯一标识，因为name仍然有可能出现重名的情况，比如“操作系统->其他”、“数据库->其他”，若以“其他”作为标识进行查询，有可能出现重复。

3.2 删除目录

还未完成的功能：

应对该接口进行权限校验，比如仅管理员可删除

应校验目录下有无文章与习题，保证数据一致性

设category左右坐标为

[l, r]

，则所有坐标范围在

[l, r]

内的节点都需要删除。

令

w i d t h \leftarrow r - l + 1

，对所有目录节点

v

，若左坐标大于

r

，则令其减

w i d t h

、右坐标大于

r

，也令其减

w i d t h

。

即对于在category之后的节点坐标，减去了category节点的宽度。

最后令缓存失效。

3.3 插入分类路径

应对该接口进行权限校验，比如仅管理员可删除

对形如['计算机网络'、'传输层'、'TCP协议']的List<String>数据，将其插入至目录树中。

3.4 插入子分类

应对该接口进行权限校验，比如仅管理员可删除

根据父节点Id与分类名，插入新的分类。

3.5 查询子孙节点

为文章、习题分类查询准备的方法。

查询category的所有子孙节点，设左右坐标为[l, r]，即查询所有所有[l, r]内的节点。

3.6 查询祖先节点

查询category的所有祖先节点（包含category本身），设左右坐标为[l, r]，即查询所有所有左坐标小于等于l，右坐标大于等于r的节点。

3.1 所有目录#

3.2 删除目录#

3.3 插入分类路径#

3.4 插入子分类#

3.5 查询子孙节点#

3.6 查询祖先节点#

3.1 所有目录

3.2 删除目录

3.3 插入分类路径

3.4 插入子分类

3.5 查询子孙节点

3.6 查询祖先节点