个人博客：http://www.80soho.com/?p=781场景：有这样一个需求：设计开发一个评论系统，要求用户对评论进行评论文章互动回复，层数不限。这个需求开发者基本都遇到过，大家可以先回忆一下或者考虑一下这个数据表怎么设计！定义：具有递归关系的数据非常普遍，数据通常以树状或分层方式组织。在树结构中，实例称为节点（node），每个节点有多个子节点和一个父节点，最上面的节点称为根（root）节点，它没有父节点，最下面的节点没有子节点节点称为叶子，中间的节点简称为非叶子节点。评论数据是一种树形结构数据，评论的子节点就是它的回复。还有很多树状结构的数据，比如员工和经理的关系，菜单等等；方案：以下方案均不考虑外键约束，数据库为MYSQL！邻接表可能是最常见的解决方案，直接添加parent_id字段，引用同一张表中的其他响应。表结构如下CREATETABLE`Comments`(`comment_id`int(11)NOTNULLAUTO_INCREMENTCOMMENT'commentID',`parent_id`int(11)NOTNULLDEFAULT'0'COMMENT'comment'sparentID',`article_id`int(11)NOTNULLDEFAULT'0'COMMENT'文章ID',`comment`varchar(200)DEFAULT''COMMENT'评论内容',PRIMARYKEY(`comment_id`))ENGINE=InnoDBDEFAULTCHARSET=utf8COMMENT='简化评论表';邻接表总是依赖于父节点，看它的优缺点：树操作中最常见的一项无法完成，查询一个节点的所有后代；一个很长的回复需要用一个简单的sql来检索分支还是很困难的；也可以先获取文章的所有评论，在程序的栈内存中处理积分，但是数据量和访问量都很大，每次有人访问都做数据处理不切实际；添加叶子节点操作非常方便；删除节点会变得更复杂：考虑到数据的完整性，删除一个子树要考虑处理它所有的后代节点；上述方案可以称为：“纯数字”反模式！明智地使用反模式：邻接表设计的优点是可以快速获得给定节点的直接父节点，并且插入新节点也很容易。如果您的应用程序需要这样的要求，那么使用邻接表就可以了！再看看其他解决方案：路径枚举路径枚举的设计是将所有的祖先信息组合成一个字符串，作为每个节点的一个属性保存起来：CREATETABLE`Comments`(`comment_id`int(11)NOTNULLAUTO_INCREMENTCOMMENT'CommentID',`path`varchar(1000)NOTNULLDEFAULT'0'COMMENT'Path:eg:1/2/4',`article_id`int(11)NOTNULLDEFAULT'0'COMMENT'articleID',`comment`varchar(200)DEFAULT''COMMENT'评论内容',PRIMARYKEY(`comment_id`))ENGINE=InnoDBDEFAULTCHARSET=utf8COMMENT='简化评论表';看看这个解决方案是否解决了邻接表的问题？1.通过比较每个节点的路径查询一个节点的祖先：比如查找comment_id为4的所有祖先的sql：SELECT*fromCommentsAScwhere'1/3/4/'likeCONCAT(c.路径,'%');2.查询一个节点的所有背景：比如comment_id为1的所有背景：SELECT*fromCommentsAScwherec.pathlikeCONCAT('1/','%');3。插入节点：只需要复制一份父节点的路径；comment_id是自动生成的，需要先插入再修改；这种方案的缺点：数据库不能保证路径的格式总是正确的或者路径中的节点确实存在，需要应用程序的逻辑代码来维护，验证路径的开销字符串的正确性非常高；而且不管varcharde的长度设置多大，还是有长度限制的，所以不能支持树结构的无限扩展。闭包表闭包表记录了树中所有节点之间的关系，而不仅仅是那些直接的父子关系，是一种简单优雅的分层存储方案。该方案不再使用Comments表来存储树的结构，而是将树中任何具有祖先-后代关系的节点对存储在一个新表中，即使这两个节点不是直接的父子关系，也添加一行指向节点本身，表结构如下：CREATETABLE`Comments`(`comment_id`int(11)NOTNULLAUTO_INCREMENTCOMMENT'CommentID',`article_id`int(11)NOTNULLDEFAULT'0'COMMENT'文章ID',`comment`varchar(200)DEFAULT''COMMENT'评论内容',PRIMARYKEY(`comment_id`))ENGINE=InnoDBAUTO_INCREMENT=6DEFAULTCHARSET=utf8COMMENT='简化评论表';CREATETABLE`TreePaths`(`ancestor`int(11)NOTNULLDEFAULT'0'COMMENT'ancestor',`descendant`int(11)NOTNULLDEFAULT'0'COMMENT'descendant')ENGINE=InnoDBDEFAULTCHARSET=utf8;下面看相关操作1.Searchforancestors:搜索评论的祖先5:SELECTc.*fromCommentsascJOINTreePathsastonc.`comment_id`=t.ancestorWHEREt.descendant=5;2.搜索背景：搜索评论1的后代：SELECTc.*来自CommentsascJOINTreePathsastonc.`comment_id`=t.descendantWHEREt.ancestor=1;3。插入子节点：比如评论5增加一个新的子节点，应该先插入self-to-self关系，然后在TreePaths表中搜索所有后代为评论5的节点，增加'ancestor-这些节点和新节点之间的后代关系。TreePaths表可以继续优化：增加path_length字段，表示祖先和后代的层数等；综上所述，上述三种方案各有优缺点。如何选择设计取决于应用程序中最需要的操作是什么性能优化：邻接表是最全面的设计，很多开发者都懂；路径枚举可以直观的展示祖先和后代之间的路径，但同时由于不能保证引用完整性，使得这个设计非常脆弱，闭包代表了一个通用的设计，需要额外的表来存储关系，并采用空间换时间的方案，减少运算过程中冗余计算带来的消耗。当然还有其他的设计方案，没有最好的方案，只有最适合某一应用需求的方案，欢迎多多交流！
