[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);
}
```
后來打開新浪微博的一看，感覺原理相似，只不過不同的是排序方式是按時間倒序，這種做法速度很快，其并沒有實現樹狀結構，通過減少深度來換取了遍歷的速度。并且用戶的習慣就是最新的回復要不在最上面，要不在最下面，值得學習一番！當然大公司到底是怎么做的就不是我這種小輩能猜到的了。
