软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
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年7日历
2018-7-19 13:40:20
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --