树状结构如何在数据库中存储

昨天有人在QQ小组问起，无限分层的树状结构，数据量比较大，在一万条以上，如何设计数据库的结构。其实这是个老生常谈的问题，一般的做法是有一个pid字段，为了提高效率，还会有个FullPath字段。（一些人还设置一个层级字段，但我不知道这个字段有何作用），FullPath字段可以用id-id-id….这种方式拼字符串存储，这样可以方便地用 like 语句进行查询某个节点及其子节点。

曾经看到过另外一种存储方式，利用了一般树结构可以转换二叉树的这一做法，用二叉树进行存储，在数据量大的情况下，存储读效率比上述的常见方案更优些，所以特写此文简单介绍一番。

下图说明了这种方案

<a href="http://www.dailybo.com/wp-content/uploads/2015/12/2011072422272454881.gif"><img class="alignnone size-full wp-image-43" src="http://www.dailybo.com/wp-content/uploads/2015/12/2011072422272454881.gif" alt="2011072422272454881" width="411" height="166" /></a>

如图所示，在每个节点上，有left ,right两个字段，我们看到，图上从根节点顺着子节点开始画一条线，每深入一层left加一，到底后，right=left+1，然后顺着节点回溯，right逐级加一，一直回到根节点。

如果要查询某个节点及其子节点，比如 fruit 节点 ，条件为 where left between 2 and 11

要查某个节点的full path ，比如 banana，条件为 where left&lt;8 and right &gt;9

如果要插入某个节点，比如red yellow直接插入一个节点，则update left =left+2 where left&gt;=7 ,update right=right+2 where right&gt;7,然后 新节点的left rigt分别是 7，8。 删除节点类似。

这种方式，因为id都是int型数据，加上索引后，读的效率较高。而fullPath字段的方案查询时候用的是字符串操作like，效率较低。

在内存中，如果要还原树状结构，即在每个节点上增加pid属性和children属性，则稍微麻烦些，可以如下操作：

1 按left between x and y order by left 取数据

2 顺序遍历数据，如果left=上一个Left+1,则是上一个节点的子节点，设置两个对象的父子关系，(【抱歉，这里错误的，感谢“看风景的人”指出。】 如果发生跳号，则是上一个节点的兄弟节点。） 【这样才是正确的】 如果发生跳号，说明这个节点不是上节点的子节点，向上回溯，找到right编号为当前节点left-1的，这个新找到的节点就是当前节点的兄弟。 比如 cherry(4,5)的下一个节点Yellow(7,10)，向上找到red(3,6)为兄弟，meat(12,17)则向上找到 fruit（2,11）为兄弟。

3 如果要按水平查找兄弟节点，比如第二层，第一个节点为 fruit(2,11),然后向下查找，right=11，查找left=12的即为下一个兄弟节点。

OK，大致的方案就介绍到这里，下面是参考地址

Storing Hierarchical Data in a Database Article

顺便说一下，jqgrid的treegrid支持这种数据结构。