国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

sql反模式(二) — 單純的樹

cnTomato / 3030人閱讀

摘要:其他的樹形結構數據像職員與經理的關系,菜單等等很多方案以下所有方案中暫不考慮外鍵約束,數據庫是鄰接表這個可能是最常見的解決方案,直接添加字段,引用同一張表中的其他回復。

個人博客:http://www.80soho.com/?p=781
場景:

有這么個需求:設計開發一個評論系統,要求用戶可以評論文章以及相互回復,無層級數限制。

這個需求開發人員基本都遇到過,可以先回憶或考慮這個數據表如何設計!


定義:

存在遞歸關系的數據很常見,數據常會像樹或者以層級方式組織。在樹形結構中,實例被稱為節點(node),每個節

點有多個子節點和一個父節點,最上面的節點叫根(root)節點,它沒有父節點,最底層的沒有子節點的節點叫葉

(leaf), 中間的節點簡單地稱為非葉(nonleaf)節點。

評論數據就是一種樹形結構數據,評論的子節點就是它的回復。其他的樹形結構數據像職員與經理的關系,菜單等等很多;


方案:以下所有方案中暫不考慮外鍵約束,數據庫是MYSQL!

鄰接表

這個可能是最常見的解決方案,直接添加parent_id字段,引用同一張表中的其他回復。表結構如下

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

鄰接表總是依賴父節點,看看它的優缺點:

無法完成樹操作中最普通的有一項,查詢一個節點的所有后代;

要用一條簡單的sql檢索一個很長的回復分支還是很困難的;

也可先獲取文章的所有評論,在程序的棧內存中處理整合,但數據量,訪問量都大,每次有人訪問都要做一次數據處理也不切實際;

增加葉子節點操作是非常方便的;

刪除節點會變得比較復雜:考慮數據完整性,刪除一棵子樹,不得不考慮處理其所有的后代節點;

上述這種方案可被叫做:‘單純的數‘ 反模式!

要合理的使用反模式:鄰接表設計的優勢在于能快速地獲取一個給定節點的直接父節點,也很容易插入新節點。如果這樣的需求就是你的應用程序的需求,那使用鄰接表就可以很好地工作!


下面再看看其他的方案:

路徑枚舉

路徑枚舉的設計通過將所有的祖先的信息聯合成一個字符串,并保存為每個節點的一個屬性:

CREATE TABLE `Comments` (
  `comment_id` int(11) NOT NULL AUTO_INCREMENT COMMENT "評論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 "評論內容",
  PRIMARY KEY (`comment_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT="簡化的評論表";

來看看該方案有沒有解決鄰接表的問題,

1. 通過比較每個節點的路徑來查詢一個節點的祖先:例如查找comment_id 為4的所有的祖先的sql:
    SELECT * from Comments AS c where "1/3/4/" like  CONCAT(c.path,"%");
2. 查詢一個節點的所有后臺:例如 comment_id 為 1 的所有后臺:
 SELECT * from Comments AS c where c.path like CONCAT("1/","%");
3. 插入節點:只需一份父節點的路徑即可;comment_id是自動生成,需要先插入再修改;
該方案的缺點:數據庫不能確保路徑的格式總是正確或者路徑中的節點確實存在,需應用程序的邏輯代碼來維護,且驗證字符串的正確性的開銷很大;再者,無論將varcharde的長度設定為多大,依舊存在長度限制,因而不能支持樹結構的無限擴展。

閉包表

閉包表記錄樹中所有節點間的關系,而不僅僅只有那些直接的父子關系,是一個簡單而優雅的分級存儲解決方案。

該方案不再使用Comments表來存儲樹的結構,而是將樹中任何具有祖先-后代關系的節點對都存儲在新表中,即使兩個節點不是直接的父子關系,同時,還增加一行指向節點自己,表結構如下:

CREATE TABLE `Comments` (
  `comment_id` int(11) NOT NULL AUTO_INCREMENT COMMENT "評論ID",
  `article_id` int(11) NOT NULL DEFAULT "0" COMMENT "文章ID",
  `comment` varchar(200) DEFAULT "" COMMENT "評論內容",
  PRIMARY KEY (`comment_id`)
) ENGINE=InnoDB AUTO_INCREMENT=6 DEFAULT CHARSET=utf8 COMMENT="簡化的評論表";
CREATE TABLE `TreePaths` (
  `ancestor` int(11) NOT NULL DEFAULT "0" COMMENT "祖先",
  `descendant` int(11) NOT NULL DEFAULT "0" COMMENT "后代"
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

下面看看相關操作

1. 搜索祖先:搜索評論5的祖先:
  SELECT c.* from Comments as c JOIN TreePaths as t on c.`comment_id` = t.ancestor WHERE t.descendant=5;

2. 搜索后臺:搜索評論1的后代:
  SELECT c.* from Comments as c JOIN TreePaths as t on c.`comment_id` = t.descendant WHERE t.ancestor=1;

3. 插入子節點:

例如評論5新增一個子節點,應首先插入一條自己到自己的關系,然后搜索TreePaths表中后代是評論5的所有節點,增加這些節點和新節點的’祖先-后代‘關系。


TreePaths表可以繼續優化:增加path_length字段表示祖先與后代的層級數等等;


綜述

以上列舉了三個方案,沒種設計都各有優劣,如何選擇設計依賴于應用程序中的哪種操作最需要性能上的優化:

鄰接表是最方面的設計,并且很多開發中都了解它;

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

閉包表示通用的設計,它要求一個張額外的表來存儲關系,使用空間換時間的方案減少操作過程中冗余的計算所造成的消耗。


當然還有其他的設計方案,沒有最好的方案,只有最適合某個應用需求的方案,歡迎多多交流!

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/31140.html

相關文章

  • 樹和樹的算法

    摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式,為二叉樹的節點個數。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數據類型(ADT)或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。它是由n(n>=1)個有限節點組成一個...

    RaoMeng 評論0 收藏0
  • 樹和樹的算法

    摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式,為二叉樹的節點個數。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數據類型(ADT)或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。它是由n(n>=1)個有限節點組成一個...

    PiscesYE 評論0 收藏0
  • leetcode449. Serialize and Deserialize BST

    摘要:題目要求將二叉搜索樹序列化和反序列化,序列化是指將樹用字符串的形式表示,反序列化是指將字符串形式的樹還原成原來的樣子。假如二叉搜索樹的節點較多,該算法將會占用大量的額外空間。 題目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...

    Honwhy 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<