软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 数据库 -> sqlite3树形结构遍历效率对比测试 -> 正文阅读

[数据库]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:引入关系表
现在数据库表的结构如下图所示。
[img]http://img.blog.csdn.net/20160325154406572?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
它是一种结构化的数据库表结构。将节点的id和父节点id都存储在一个记录中。好处是开发时候快速,坏处是,不便于扩展和修改。
说它不便于扩展,是因为假如一个节点有两个父节点,则一个字段无法满足。再加一个father_id字段吗?显然不现实,因为不知道会有多少个父节点。
说它不便于修改,是因为,如果将多个父节点id都采用格式化都填入father_id字段,则在维护记录的时候会带来“拼串和解析串”的步骤,带来维护上的麻烦。
那么,是否可以换一种思路,采用面向对象的思维创建数据库表呢?于是想到了下面的表结构和表关系。
[img]http://img.blog.csdn.net/20160325154911297?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
如图所示,增加一个关系表,专门用来存储节点之间的关系。将father_id和son_id作为联合主键。如此一来,节点与节点之间的关系,其实就对应的是关系表中的一条记录!一个节点有多少个子节点,关系表中就有多少条记录。一个节点有多少个父节点,也是这样。
这样改造了数据库表之后,带来的好处是显而易见的,
首先是可维护性的提升。从以前的解析修改表字段,到现在的插入删除一条或多条记录。
其次是开发维护人员对于数据的关系也会理解地更加深刻和清楚。
但不可避免,也有不足之处,
首先是开发的成本。这样的表结构和表关系,不利于快速开发。
其次是现在的软件系统已经用了好几年,突然修改,可能会造成现场维护上的压力突然增大。
第三,这样的结构,是否满足业务功能要求的效能,还是个未知数。

三、结果对比


下面给出上述方案1、2、3的测试对比表。
方案1
[img]http://img.blog.csdn.net/20160325160229563?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
方案2
[img]http://img.blog.csdn.net/20160325160246782?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
方案3
[img]http://img.blog.csdn.net/20160325160301422?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
从理论上来讲,查询得到结果的效率是 方案3 > 方案1 > 方案2。
从上面3个表来看,结果的确如期望的那样。
但是,有些意外的是,方案3中从结果集中获取下一条记录这一步骤(即next),太占用时间,竟然达到了97%的占比。
从综合效率上来看,方案1时间最快。其次是方案3,最慢的是方案2。因为方案2要执行大量的函数递归调用,函数栈切换,这是最为耗时的。
......显示全文...
    点击查看全文


上一篇文章      下一篇文章      查看所有文章
2016-03-26 16:27:14  
数据库 最新文章
Python&MySQL&PyQt
最新用python来操作mysql完全解析
mongodb的安装详解
1.PDO简介
《MySQL必知必会学习笔记》:高级联结
【翻译自mos文章】怎么对Microsoft(Office)
MyCAT全局表描述及示例
ocp
关于SQL数据表存储过程表名前缀换成dbo代码
数据库调优教程(二)慢查询数据准备
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年11日历
2018-11-16 20:12:04
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --