摘要：其他的樹(shù)形結(jié)構(gòu)數(shù)據(jù)像職員與經(jīng)理的關(guān)系，菜單等等很多方案以下所有方案中暫不考慮外鍵約束，數(shù)據(jù)庫(kù)是鄰接表這個(gè)可能是最常見(jiàn)的解決方案，直接添加字段，引用同一張表中的其他回復(fù)。

個(gè)人博客：http://www.80soho.com/?p=781

有這么個(gè)需求：設(shè)計(jì)開(kāi)發(fā)一個(gè)評(píng)論系統(tǒng)，要求用戶可以評(píng)論文章以及相互回復(fù)，無(wú)層級(jí)數(shù)限制。

這個(gè)需求開(kāi)發(fā)人員基本都遇到過(guò)，可以先回憶或考慮這個(gè)數(shù)據(jù)表如何設(shè)計(jì)！

存在遞歸關(guān)系的數(shù)據(jù)很常見(jiàn)，數(shù)據(jù)常會(huì)像樹(shù)或者以層級(jí)方式組織。在樹(shù)形結(jié)構(gòu)中，實(shí)例被稱(chēng)為節(jié)點(diǎn)(node)，每個(gè)節(jié)

點(diǎn)有多個(gè)子節(jié)點(diǎn)和一個(gè)父節(jié)點(diǎn)，最上面的節(jié)點(diǎn)叫根(root)節(jié)點(diǎn),它沒(méi)有父節(jié)點(diǎn)，最底層的沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)叫葉

(leaf), 中間的節(jié)點(diǎn)簡(jiǎn)單地稱(chēng)為非葉(nonleaf)節(jié)點(diǎn)。

評(píng)論數(shù)據(jù)就是一種樹(shù)形結(jié)構(gòu)數(shù)據(jù)，評(píng)論的子節(jié)點(diǎn)就是它的回復(fù)。其他的樹(shù)形結(jié)構(gòu)數(shù)據(jù)像職員與經(jīng)理的關(guān)系，菜單等等很多；

鄰接表

這個(gè)可能是最常見(jiàn)的解決方案，直接添加parent_id字段，引用同一張表中的其他回復(fù)。表結(jié)構(gòu)如下

 CREATE TABLE `Comments` (
  `comment_id` int(11) NOT NULL AUTO_INCREMENT COMMENT "評(píng)論ID",
  `parent_id` int(11) NOT NULL DEFAULT "0" COMMENT "評(píng)論的父ID",
  `article_id` int(11) NOT NULL DEFAULT "0" COMMENT "文章ID",
  `comment` varchar(200) DEFAULT "" COMMENT "評(píng)論內(nèi)容",
  PRIMARY KEY (`comment_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT="簡(jiǎn)化的評(píng)論表";

鄰接表總是依賴父節(jié)點(diǎn)，看看它的優(yōu)缺點(diǎn)：

無(wú)法完成樹(shù)操作中最普通的有一項(xiàng)，查詢一個(gè)節(jié)點(diǎn)的所有后代；

要用一條簡(jiǎn)單的sql檢索一個(gè)很長(zhǎng)的回復(fù)分支還是很困難的；

也可先獲取文章的所有評(píng)論，在程序的棧內(nèi)存中處理整合，但數(shù)據(jù)量，訪問(wèn)量都大，每次有人訪問(wèn)都要做一次數(shù)據(jù)處理也不切實(shí)際；

增加葉子節(jié)點(diǎn)操作是非常方便的；

刪除節(jié)點(diǎn)會(huì)變得比較復(fù)雜：考慮數(shù)據(jù)完整性，刪除一棵子樹(shù)，不得不考慮處理其所有的后代節(jié)點(diǎn)；

要合理的使用反模式：鄰接表設(shè)計(jì)的優(yōu)勢(shì)在于能快速地獲取一個(gè)給定節(jié)點(diǎn)的直接父節(jié)點(diǎn)，也很容易插入新節(jié)點(diǎn)。如果這樣的需求就是你的應(yīng)用程序的需求，那使用鄰接表就可以很好地工作！

下面再看看其他的方案：

路徑枚舉

路徑枚舉的設(shè)計(jì)通過(guò)將所有的祖先的信息聯(lián)合成一個(gè)字符串，并保存為每個(gè)節(jié)點(diǎn)的一個(gè)屬性：

CREATE TABLE `Comments` (
  `comment_id` int(11) NOT NULL AUTO_INCREMENT COMMENT "評(píng)論ID",
  `path` varchar(1000) NOT NULL DEFAULT "0" COMMENT "路徑：eg: 1/2/4",
  `article_id` int(11) NOT NULL DEFAULT "0" COMMENT "文章ID",
  `comment` varchar(200) DEFAULT "" COMMENT "評(píng)論內(nèi)容",
  PRIMARY KEY (`comment_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT="簡(jiǎn)化的評(píng)論表";

來(lái)看看該方案有沒(méi)有解決鄰接表的問(wèn)題，

1. 通過(guò)比較每個(gè)節(jié)點(diǎn)的路徑來(lái)查詢一個(gè)節(jié)點(diǎn)的祖先：例如查找comment_id 為4的所有的祖先的sql：

    SELECT * from Comments AS c where "1/3/4/" like  CONCAT(c.path,"%");

2. 查詢一個(gè)節(jié)點(diǎn)的所有后臺(tái)：例如 comment_id 為 1 的所有后臺(tái)：

 SELECT * from Comments AS c where c.path like CONCAT("1/","%");

3. 插入節(jié)點(diǎn)：只需一份父節(jié)點(diǎn)的路徑即可；comment_id是自動(dòng)生成，需要先插入再修改；

該方案的缺點(diǎn)：數(shù)據(jù)庫(kù)不能確保路徑的格式總是正確或者路徑中的節(jié)點(diǎn)確實(shí)存在，需應(yīng)用程序的邏輯代碼來(lái)維護(hù)，且驗(yàn)證字符串的正確性的開(kāi)銷(xiāo)很大；再者，無(wú)論將varcharde的長(zhǎng)度設(shè)定為多大，依舊存在長(zhǎng)度限制，因而不能支持樹(shù)結(jié)構(gòu)的無(wú)限擴(kuò)展。

閉包表

閉包表記錄樹(shù)中所有節(jié)點(diǎn)間的關(guān)系，而不僅僅只有那些直接的父子關(guān)系，是一個(gè)簡(jiǎn)單而優(yōu)雅的分級(jí)存儲(chǔ)解決方案。

該方案不再使用Comments表來(lái)存儲(chǔ)樹(shù)的結(jié)構(gòu)，而是將樹(shù)中任何具有祖先-后代關(guān)系的節(jié)點(diǎn)對(duì)都存儲(chǔ)在新表中，即使兩個(gè)節(jié)點(diǎn)不是直接的父子關(guān)系，同時(shí)，還增加一行指向節(jié)點(diǎn)自己，表結(jié)構(gòu)如下：

CREATE TABLE `Comments` (
  `comment_id` int(11) NOT NULL AUTO_INCREMENT COMMENT "評(píng)論ID",
  `article_id` int(11) NOT NULL DEFAULT "0" COMMENT "文章ID",
  `comment` varchar(200) DEFAULT "" COMMENT "評(píng)論內(nèi)容",
  PRIMARY KEY (`comment_id`)
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8 COMMENT="簡(jiǎn)化的評(píng)論表";

CREATE TABLE `TreePaths` (
  `ancestor` int(11) NOT NULL DEFAULT "0" COMMENT "祖先",
  `descendant` int(11) NOT NULL DEFAULT "0" COMMENT "后代"
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

下面看看相關(guān)操作

1. 搜索祖先：搜索評(píng)論5的祖先：

  SELECT c.* from Comments as c JOIN TreePaths as t on c.`comment_id` = t.ancestor WHERE t.descendant=5;

2. 搜索后臺(tái)：搜索評(píng)論1的后代：

  SELECT c.* from Comments as c JOIN TreePaths as t on c.`comment_id` = t.descendant WHERE t.ancestor=1;

3. 插入子節(jié)點(diǎn)：

例如評(píng)論5新增一個(gè)子節(jié)點(diǎn)，應(yīng)首先插入一條自己到自己的關(guān)系，然后搜索TreePaths表中后代是評(píng)論5的所有節(jié)點(diǎn)，增加這些節(jié)點(diǎn)和新節(jié)點(diǎn)的’祖先-后代‘關(guān)系。

TreePaths表可以繼續(xù)優(yōu)化：增加path_length字段表示祖先與后代的層級(jí)數(shù)等等；

綜述

以上列舉了三個(gè)方案，沒(méi)種設(shè)計(jì)都各有優(yōu)劣，如何選擇設(shè)計(jì)依賴于應(yīng)用程序中的哪種操作最需要性能上的優(yōu)化：

鄰接表是最方面的設(shè)計(jì)，并且很多開(kāi)發(fā)中都了解它；

路徑枚舉能夠很直觀地展示出祖先與后代之間的路徑，但同時(shí)由于它不能確保引用完整性，使得這個(gè)設(shè)計(jì)十分脆弱，

閉包表示通用的設(shè)計(jì)，它要求一個(gè)張額外的表來(lái)存儲(chǔ)關(guān)系，使用空間換時(shí)間的方案減少操作過(guò)程中冗余的計(jì)算所造成的消耗。