MikeTech开发笔记:评论模块

June 25, 2019
Spring BootBackend DevData StructureAlgorithm

前些日子重新开发了我的个人博客 MikeTech,其中一个功能就是评论模块,在每篇文章底下会有一个评论框,用户可以留言,或者是回复某个留言,这篇文章将会讲述这个功能的前后端设计。

功能描述

功能很简单,就和大家每天在各个平台上使用的评论功能一样,可以给文章留言,或者去回复某一个人的留言。这些留言会根据层级显示出来。下面的图片能很好的解释这个功能, 其中Yigang Zhou和C是对文章进行了评论,而A是回复了YigangZhou的评论,B回复了A的评论。每一条评论会因为层级的不同而有不同的左边距,这样就能很直观的看出谁在回复谁了。

数据库设计

数据库设计很简单,我只使用了一张数据表用于评论。下面是这张表的大体结构。

  • id: 评论的id,主键
  • content:评论的内容
  • name:评论者的名字
  • date:评论的时间
  • email:评论者的email
  • parent_id:这条评论的父评论id
  • post_id:这条评论所属的文章的id

post_id代表文章的id,假设我有一篇文章id为10,那么这篇文章下面所有的评论的post_id都会被设为10,用于检索特定文章下的所有评论。

parent_id 则是这条评论所属评论的id,如果这条评论是在文章根部进行评论的,那么parent_id为-1。拿上一张图举例子,Yigang和C是对文章进行了直接评论,那么这两条评论的parent_id 都为 -1。假设A评论的id为20,B回复了A,那么B评论的parent_id则为20。不难理解。

评论树的建立

那么接下来的问题就是怎么样把评论按照层级展示出来了。对数据结构有了解的同学不难看出评论应该是一个树结构。下图是一个简单的树结构(二叉树),博客的每一条评论可以被看做是树的一个节点,评论节点的子叶节点则为回复这条评论的节点。比如下图的H,I节点可以被看做是D的回复,而D,E则是评论B的回复。

每次有用户评论的时候会在数据库里面新建一个条目,就相当于一个评论节点,需要显示一篇文章评论的时候则需要把所有的节点读取出来,因为数据库读出来是根据时间来排序的,所以并不能直接拿来使用,所以需要把评论的所有节点重建为一颗评论树,然后再对这棵树进行一次前序遍历即可得到正确的评论层级。需要表现层级的话,每个评论节点的深度则为层级,根节点深度为0,对根部节点的评论深度为1,以此类推。

接下来用代码讲解一下,首先我建立了一个Comment类来代表一个评论。

  1. public class Comment {
  2. //id
  3. private int id;
  4. //父评论的Id
  5. private int parentId;
  6. //内容
  7. private String content;
  8. public Comment(int id, int parentId, String content) {
  9. this.id = id;
  10. this.parentId = parentId;
  11. this.content = content;
  12. }
  13. //getter and setter..
  14. }

然后创建一些Comment实例用来测试:

  1. List<Comment> comments = new LinkedList<>();
  2. comments.add(new Comment(0,-1,"root1"));
  3. comments.add(new Comment(1,-1,"root2"));
  4. comments.add(new Comment(2,-1,"root3"));
  5. comments.add(new Comment(3,0,"root1的relay"));
  6. comments.add(new Comment(4,2,"root3的relay"));
  7. comments.add(new Comment(5,3,"root1的relay的reply"));
  8. comments.add(new Comment(6,1,"root2的reply1"));
  9. comments.add(new Comment(7,1,"root2的reply2"));
  10. comments.add(new Comment(8,5,"root1的relay的reply的reply"));
  11. comments.add(new Comment(9,0,"root1的reply2"));

然后建立一个CommentNode类来表示评论树的一个节点,因为评论树不是像二叉树那样每个节点最多只有两个子节点,这颗评论树的子节点数目不固定,所以不能方便用数组进行序列化或者还原。只能通过遍历数据库里读出来的Comment实例来判断节点的归属。下面代码CommentNode的构造器中就是重建评论树的过程,每次初始化一个CommentNode节点的时候构造器会对所有的Comment进行一次遍历来寻找当前Node的子节点,然后再递归的创建CommentNode作为子节点,每次新建的时候节点深度会+1。

  1. public class CommentNode {
  2. public int depth = 0; //深度
  3. public Comment root; //当前Node的Comment实例
  4. public List<CommentNode> children = new ArrayList<>(); //子叶节点
  5. public boolean isLeaf(){
  6. return children.isEmpty();
  7. }
  8. public CommentNode(Comment root, List<Comment> allComments, int depth){
  9. this.root = root;
  10. this.depth = depth;
  11. for (Comment comment: allComments){
  12. if (comment.getParentId() == root.getId()){
  13. //递归调用
  14. CommentNode node = new CommentNode(comment, allComments, depth+1);
  15. children.add(node);
  16. }
  17. }
  18. }
  19. }

上述的代码只是为了方便讲解树的还原过程,并不高效。可以看到CommentNode每次初始化的时候都要遍历一次Comment列表,非常不高效,这样的算法复杂度能达到 N^2。哈希表可以用来优化这套流程,可以在生成Comment列表的时候进行一次遍历然后根据父id作为key,父id所属的所有Comment列表作为Value生成一个哈希表。这样每次CommentNode初始化的时候只要查询哈希表就行了,省去了遍历所有Comment的低效率。

设计好这个类之后只要初始化一个id为-1的空CommentNode即可重建评论树:

  1. Comment root = new Comment(-1,-1,"");
  2. CommentNode node = new CommentNode(root, comments,-1);

从调试界面可以看出树的结构:

tree

评论树的前序遍历

那么既然评论树已经建立了,那么只需要将它打印出来就可以了,这里的打印方法应该为前序遍历,先遍历跟节点,然后是子叶节点。下面是一段示例代码,preorderTraversal函数会被递归调用来打印整颗树,getPadding的作用是根据子叶的深度来输出一些字符来代表左边距。

  1. public static void preorderTraversal(CommentNode root){
  2. //不打印id为-1的节点
  3. if (root.root.getId() != -1){
  4. System.out.println(getPadding(root.depth)+root.root.getContent());
  5. }
  6. if (root.isLeaf()){return;}
  7. for (CommentNode n: root.children){
  8. preorderTraversal(n);
  9. }
  10. }
  11. public static String getPadding(int level){
  12. String padding = "";
  13. for (int i=0;i<level;i++){
  14. padding += "- ";
  15. }
  16. return padding;
  17. }

下图是程序的输出结果,可以看出来评论内容和层级都没有问题。

tree_print

前端渲染

既然后端已经能够通过前序遍历得到排序好的评论列表了,那么前端显示的解决方案就很简单了,只是需要渲染一个列表就行了,列表的每一列则为一个评论,这一列的评论的层级则用左边距来表示,下图是MikeTech评论显示的API,其中的level则代表当前评论的层级,0代表根部,1代表回复根部评论,以此类推。

comments_api

comments_level

以上就是评论系统的一个简单的实现。

Comments

July 21, 2018 at 10:52 am

There are no comments

keyboard_arrow_up