关于树结构的数据,如何在关系型数据库中表示,已经成为了一个老生常谈的问题.在这个项目中,我们也遇到了这个问题.
目前,业界中已经给出了一些解决方案,最常见,最常用的是这三种:Parent-Child, Materialized Path, Nested Sets.其中,讨论最多的,又是Nested Sets.
今天,在选择方案的过程中,对这几种方案,都做了一个详细的比较,也针对我们的使用场景,做了一些假设.最终,选择了第二种方式,即Materialized Path.
这几种方案,其实都不完美.
我们的主要的使用场景,基本如下:
- 查询树中全部的节点,并按其层次关系,组成一个JSON对象,返回给前台
- 分页查询,即查询树中一定数量的一级节点,以及这些一级节点的全部子节点
- 增加一个叶子节点
- 删除一个节点,可能是叶子节点,也可能是非叶子节点
- 修改一个节点的数据
我们的树结构中的特点有:
- 一级节点比较多,二级以后的节点应该就很少了
根据这个特色,我们设计主键字段的为36位的uuid,路径字段的数据类型为TINYTEXT,因为TINYTEXT的长度为255 bytes,基本上能够支持七层深度的树.如果我们采用其他的数据类型,比如说,TEXT,其长度为65535 bytes,那可以支持更深的树.
那我们的主键字段,为什么不采用可以AUTO_INCREMENT的int型呢?考虑到AUTO_INCREMENT是串行操作的,当同时有多个插入操作时,可能会存在性能上的问题.MySQL到底是怎么实现的,我也没看过.但是我觉得在AUTO_INCREMENT这里,至少应该有一个锁机制,来保证生成的id是连续并且唯一的.就算没有,在计算机底层执行主键id+1的操作时,也一定是串行的.而我们采用在代码内自己生成UUID的方式,就可以避免这个约束.
我们之前在查找解决方案的时候,在对这三种方案的对比中,很多文章都使用的是最常规的树的操作的例子.但是,由于我们对树的操作有一些特殊性,比如,删除一个节点,就连带着删除这个节点的子树,使得使用Materialized Path这种方案,比较方便.其实Nested Sets这种方案,也是不错的,但是实现起来比这个复杂一些,就没有采用它.当然,还有其他的方案,比如使用专门的图数据库.
