评论模块数据结构设计

发表于 更新于

需求

  • 评论文章
  • 回复评论
  • 查询文章评论列表 不展开子评论
  • 查询文章评论列表 展开子评论
  • 展示子评论总数

方案设计

需求是一个典型的评论盖楼场景，传统的方案是一个自连接的表

自连接表，表新增一列（parent_id）外键，该列引用当前表的id值

自连接表的查询,一般都数据当成一个list全部查出来，在应用服务内构建
成一个树结构，再去做其他处理。如果一个文章的评论特别多，例如微博热帖这种场景，性能就回成为瓶颈。
因此通过自己构建树形索引结构，优化查询性能。

树形结构

核心字段

  • 节点id 自增id
  • 父节点id 父节点id
  • 左值
  • 右值
  • 树深 当前数深度， root节点是0
  • 编号 当前节点在整棵的位置，用来排序，root节点是1
  • 数据内容 节点存储的数据，评论内容

场景分析

场景1

  1. 假设db有评论A 。此时A的左值是1，右值是2,编号是1，对应图里面的step1

  2. 在A评论下新增B评论，对应图里面的step2

    • 左值=父节点（A)右值
    • 右值=左值+1
    • 编号= 父节点(A)编号 + （父节点(A)右值-父节点(A)左值+1）/2

  3. 当前树下其他节点左值更新

    • 条件 该节点左值> 新增节点（B）的父节点（A）右值 即>=2
    • 动作 左值+=2
    • 本场景 没有复合条件的，无更新

  4. 当前树下其他节点右值更新

    • 条件 右值>=新增节点（B）的父节点（A）右值 即>=2
    • 动作 右值+=2
    • 该场景节点A满足条件，则A的右值改成2, 对应图里面的step3

  5. 其他节点编号更新

    • 条件 节点编号 >= 新增节点（B）的编号
    • 动作 编号+=1
    • 该场景没有满足条件的

场景2

该场景与场景1一样

场景3

结构优点

  1. 计算子节点数量， （右值-左值）/2，例如 A （8-1）/2=3 ，B （5-2）/2=1
  2. 列出当前子节点（包括下层子节点），查询 节点左值> 当前节点左值 并且 节点右值<当前节点右值，a. 例如 B节点的所有子节点，即 where 左值>2 and 右值<5列出当前节点 一层子节点，通过parent node 即可
  3. 列出当前节点 一层子节点，通过parent node 即可
  4. 列出当前节点，特定层级的所有叶子结点， 结合2和树深即可
  5. 展开整个树，通过编号排序即可

代码实现

节点代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/* Copyright © 2020 Yuech and/or its affiliates. All rights reserved. */
package wiki.chenxun.blog.example.reply;

import lombok.AllArgsConstructor;
import lombok.Getter;

/**
 * @author 陈勋
 * @version 1.0
 * @date 2021-05-19 3:43 下午
*/


public class Node {

/**
 * 节点id
 */
private String id;

/**
 * 树id，一般是文章id
 */
private String treeId;

/**
 * 　左值
 */
private Integer left;

/**
 * 右值
 */
private Integer right;

/**
 * 树深
 */
private Integer depth;

/**
 * 编号
 */
private Integer index;

/**
 * 商城节点id
 */
private String parentId;

/**
 * 数据
 */
private String data;

public static Node rootNote(String id, String treeId,String data) {
    Node node = new Node(id, treeId, 1, 2, 0, 1, null, data);
    return node;
}

public void incrementLeft() {
    this.left += 2;
}

public void incrementRight() {
    this.right += 2;
}

public void incrementIndex() {
    this.index += 1;
}

}





树代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

/* Copyright © 2020 Yuech and/or its affiliates. All rights reserved. */
package wiki.chenxun.blog.example.reply;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.UUID;
import java.util.stream.Collectors;

/**
   * @author 陈勋
    * @version 1.0
* @date 2021-06-18 6:37 下午
  */
  public class Tree {

  private String treeId;

  private List<Node> nodeList = new ArrayList<>();

  private Node rootNode;

  public Tree(String treeId,String data) {
  this.treeId = treeId;
  this.rootNode = Node.rootNote(UUID.randomUUID().toString(), treeId,data);
  nodeList.add(rootNode);
  }

  public String addNode(String data, String parentNodeId) {

       Node parentNode;
       if (parentNodeId != null) {
           parentNode = nodeList.stream()
               .filter(i -> parentNodeId.equals(i.getId()))
               .findFirst().orElse(null);
       } else {
           parentNode = rootNode;
       }
       if (parentNode == null) {
           throw new IllegalArgumentException("parent Node not exist");
       }

       final Integer parentRight = parentNode.getRight();
       // 本次新增node在树里面的编号
       final Integer nodeIndex = parentNode.getIndex() + (parentNode.getRight() - parentNode.getLeft() + 1) / 2;
       // 数深
       final Integer nodeDepth = parentNode.getDepth() + 1;

       // 构建子节点
       Node node = new Node(UUID.randomUUID().toString(), this.treeId,
           parentNode.getRight(), parentNode.getRight() + 1,
           nodeDepth, nodeIndex,
           parentNodeId, data);

       // 跟新其他节点左值
       nodeList.stream().filter(i -> i.getLeft() >= parentRight)
           .forEach(Node::incrementLeft);

       // 更新其他节点右值
       nodeList.stream().filter(i -> i.getRight() >= parentRight)
           .forEach(Node::incrementRight);

       // 更新其他节点编号，大于等于index都往后挪一个位置
       nodeList.stream().filter(i -> i.getIndex() >= nodeIndex)
           .forEach(Node::incrementIndex);
       //添加新节点
       nodeList.add(node);

       return node.getId();

  }

  /**
    * 测试打印，左序遍历
      */
      public void print() {
      nodeList.sort(Comparator.comparing(Node::getIndex));
      String s=String.join(",", nodeList.stream()
      .map(Node::getData).collect(Collectors.toList()));

      System.out.println(s);

  }

}


测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13

    public void test(){
    Tree tree=new Tree("tree_1","文章");

    String a= tree.addNode("a",null);
    String b=tree.addNode("b",null);
    tree.addNode("c",a);
    tree.addNode("d",a);
    tree.addNode("e",b);

    tree.print();
}

业务应用

  • 数据可以和索引剥离，即data字段存的是数据id，root节点存文章id，其他节点存评论id
  • 新增节点的时候，需要把整颗树锁住
    • 通过redis做分布式锁
    • 通过select for update 做数据库悲观锁 （不推荐）
    • 通过 新增version字段做乐观锁，树的版本等于root节点的版本（推荐）
  • 删除节点，该场景下其实不删除索引，只是把数据id指向的数据删除
    • 如果删除的太多，就需要把整个树reBuild.(本场景未实现,有需要的朋友可以给留言)