[TOC=3,3]
* * * * *
### 1. 背景
今天monitor韩找我问关于如何实现无限评论的问题，我无意间想起了前几天学习数据结构中的树的存储结构时的东西，两个人便脖有兴致的讨论了一番。
* * * * *
### 2. 想法（1）
一开始的想法很简单，数据库中存两个关键字段id与parent_id,通过递归或迭代来实现功能，comment表设计如下：
| 字段名 | 描述 |
| -- | -- |
| id | 主键 |
| pid| 双亲节点（也就是回复了哪一条记录）|
| type| 1（回复文章的评论） 2（回复评论的评论）|
| content| 内容 |
| create_at | 创建时间 |
|...... | ......|
php代码如下：
```
<?php
function showAll($aid)
{
static $all = array();
$sql = "select * from comment where type = 1 and aid = $aid";
$arr = query($sql);
if(!empty($arr))
{
foreach($arr as $val)
{
$all[] = getTree($val[aid]);
}
}
}
function getTree($id = 0)
{
static $_tree = array();
$sql = "select * from comment where pid = $id and type = 2";
$arr = query($sql);
if(empty($arr))
{
return $_tree;
}
foreach($arr as $val)
{
$val['child'] = getTree($val['id']);
$_tree[] = $val;
}
return $_tree;
}
```
这种设计实现了树型结构，遍历出来的评论也可以把树状结构体现出来，但是其性能问题是我们所不能容忍的，当评论很多时，时间复杂度为O(n^8)的算法相当于一直给用户看黑白电影，服务器也会垮掉。
* * * * *
### 3. 想法（2）
上面的设计最大的问题在于遍历树型结构时，需要大量的递归操作，于是我们看了下腾讯qq空间说说的做法，腾讯并没有去实现树结构，而是更像是一个双层的feed流操作，每一层中按时间正序排列，请看截图：
因此猜测其数据存储结构如下:
```
shuoshuo{
sid(说说的id);
content;
create_at;
who_id;
}
//评论，就是回复说说的评论
comment{
sid;
cid(评论id);
content;
create_at;
who_id;
to_who_id;
}
//回复，就是回复评论的评论
reply{
sid;
cid(评论id);
content;
create_at;
who_id;
to_who_id;
}
```
php代码如下：
```
<?php
function getSS($sid)
{
static $all = array();
$sql = "select * from comment where sid = $sid";
$arr = query($sql);
if(!empty($arr))
{
foreach($arr as $val)
{
$all[] = getReply($val[cid]);
}
}
}
function getReply($cid)
{
$sql = "select * from reply where cid = $cid oreder by create_at";
return query($sql);
}
```
后来打开新浪微博的一看，感觉原理相似，只不过不同的是排序方式是按时间倒序，这种做法速度很快，其并没有实现树状结构，通过减少深度来换取了遍历的速度。并且用户的习惯就是最新的回复要不在最上面，要不在最下面，值得学习一番！当然大公司到底是怎么做的就不是我这种小辈能猜到的了。
