sqlite3树形结构遍历效率对照測试

sqlite3树形结构遍历效率对照測试

一、缘起

项目数据结构：本人从事安防行业，视频监控领域。项目中会遇到监控点位的组织机构划分、暂时划分的巡逻点位等。这些相机点位、连同组织机构，它们在逻辑关系上构成了一个树形结构。

又因为不论什么一个点位属于一个组织机构，也可能属于一个被暂时创建的视频巡逻计划中，因此，能够看出，不论什么一个节点，包含相机节点和组织机构节点，都有可能有至少一个父级节点，且不论什么一个组织机构节点也会有多个下级子节点。这中逻辑关系又构成了图。

数据量规模：一个市级别的管理平台，点位数量在十万至几十万级别。一个省级别的管理平台，所接入的点位规模在百万级别。

问题：监控平台常常须要用到的功能，就是要高速查询出来一个节点下的全部子节点、子节点的子节点等的树形结构。

我们的数据库眼下採用的是sqlite3。

眼下须要对查询遍历部分做性能上的优化，由我来承担完毕这项工作。本人无数据库方面开发的经历。仅仅用了一天时间尝试了例如以下4种方案。或许还有最好的。亲爱的读者您看到了这篇帖子，假如知道有更好的方法，还请赐教，笔者不胜感激。

因为一些原因。在这里不便于公开各个方案的代码、sql语句、或sqlite表结构等信息。还请谅解。

二、方案

从上面的数据结构能够看出，要想查询到一个节点的全部子节点，通常的做法是必须使用递归的方法。这就有了方案1、2、3。假设转换一下思路。则就产生方案4。

方案1：multimap递归查询

因为每一个节点极其父节点构成一个pair，这恰巧和STL中的multimap的数据模型一致。所以自然考虑到使用multimap实现递归遍历的方案。

详细例如以下：

（1）从数据库中查询全部的数据。

（2）将查询的结果集插入（insert）到multimap中。

（3）用递归的方法遍历查询到multimap中的节点及全部树形子节点。

方案2：函数递归查询

方案1是将全部数据都查询出来，然后在multimap中递归查找。方案2的思路是。查找这个节点的子节点，然后查找子节点的子节点，然后查找子节点的子节点的子节点......（子子孙孙无穷匮也）。实现方法是编写一个递归函数，递归地查询数据库，即递归地select。

（1）从数据库中查询全部的父节点是“传入节点”的节点记录。

（2）从（1）中的结果集中，取出查询到的节点id，将这个节点作为“父节点”，然后又一次运行（1）。

（3）由（1）和（2），假设某一次遍历的结果集为空。则表示当前遍历到的这个节点是叶子节点，它没有子节点了。

则递归函数退出。

方案3：sql语句递归查询

方案1、2的思路都是在sql语句之外递归查询。

假设可以写出递归的sql语句，效果是不是能更好呢？于是有了方案3。简单来说。方案3是将方案2中用函数实现的"查找子节点的子节点的子节点......"。替换为用sql语句来实现。

关于sqlite3的递归语句，请參考我的另外一篇博文《sqlite3-递归查询》。

这里要注意一下，sqlite3的递归语法 with recursive 可能在 其3.7.X 及下面版本号不受支持，可能会提示语法错误syntax error。我的sqlite3库升级到3.8.x之后就能查询到结果了。

方案4：引入关系表

如今数据库表的结构例如以下图所看到的。

它是一种结构化的数据库表结构。

将节点的id和父节点id都存储在一个记录中。

优点是开发时候高速。坏处是，不便于扩展和改动。

说它不便于扩展，是由于假如一个节点有两个父节点。则一个字段无法满足。再加一个father_id字段吗？显然不现实，由于不知道会有多少个父节点。

说它不便于改动，是由于。假设将多个父节点id都採用格式化都填入father_id字段。则在维护记录的时候会带来“拼串和解析串”的步骤，带来维护上的麻烦。

那么。能否够换一种思路，採用面向对象的思维创建数据库表呢？于是想到了以下的表结构和表关系。

如图所看到的。添加一个关系表，专门用来存储节点之间的关系。

将father_id和son_id作为联合主键。

如此一来，节点与节点之间的关系，事实上就相应的是关系表中的一条记录！一个节点有多少个子节点，关系表中就有多少条记录。一个节点有多少个父节点。也是这样。

这样改造了数据库表之后。带来的优点是显而易见的。

首先是可维护性的提升。

从曾经的解析改动表字段，到如今的插入删除一条或多条记录。

其次是开发维护人员对于数据的关系也会理解地更加深刻和清楚。

但不可避免，也有不足之处。

首先是开发的成本。这种表结构和表关系。不利于高速开发。

其次是如今的软件系统已经用了好几年。突然改动，可能会造成现场维护上的压力突然增大。

第三，这种结构。是否满足业务功能要求的效能，还是个未知数。

三、结果对照

以下给出上述方案1、2、3的測试对照表。

方案1

方案2

方案3

从理论上来讲。查询得到结果的效率是 方案3 > 方案1 > 方案2。

从上面3个表来看，结果的确如期望的那样。

可是，有些意外的是。方案3中从结果集中获取下一条记录这一步骤(即next)，太占用时间，居然达到了97%的占比。

从综合效率上来看，方案1时间最快。其次是方案3，最慢的是方案2。

由于方案2要运行大量的函数递归调用。函数栈切换。这是最为耗时的。