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

时间:2020-12-29 05:33:37

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:引入关系表

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

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

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

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

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

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

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

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

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

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

将father_id和son_id作为联合主键。

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

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

首先是可维护性的提升。

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

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

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

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

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

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


三、结果对照

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

方案1

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


方案2

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


方案3

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


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

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

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

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

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