免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 5505 | 回复: 12

[算法] 问一个数据库的BTree的问题。 [复制链接]

论坛徽章:
89
水瓶座
日期:2014-04-01 08:53:31天蝎座
日期:2014-04-01 08:53:53天秤座
日期:2014-04-01 08:54:02射手座
日期:2014-04-01 08:54:15子鼠
日期:2014-04-01 08:55:35辰龙
日期:2014-04-01 08:56:36未羊
日期:2014-04-01 08:56:27戌狗
日期:2014-04-01 08:56:13亥猪
日期:2014-04-01 08:56:02亥猪
日期:2014-04-08 08:38:58程序设计版块每日发帖之星
日期:2016-01-05 06:20:00程序设计版块每日发帖之星
日期:2016-01-07 06:20:00
发表于 2017-10-24 21:10 |显示全部楼层
建数据库的时候,一个表里面存储的数据可能有若干个维度。

假设有3个维度,1个数据值:field_01, field_02, field_03, data_value

现在使用field_01, field_02, field_03来做主键。

然后数据库(比如说PostgreSQL)会建一个索引,貌似默认是使用BTree。

如果这个表非常大的情况下,会不会影响性能。

所谓非常大:100G。

现在在一个16G内存的台式机上弄,提取数据的时候,有点慢。

每次select的时候,都是通过前面3个字段来提取大概几千条数据出来。有的时候需要大概不到1分钟左右。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-10-25 18:11 |显示全部楼层
本帖最后由 yulihua49 于 2017-10-25 18:31 编辑
fender0107401 发表于 2017-10-24 21:10
建数据库的时候,一个表里面存储的数据可能有若干个维度。

假设有3个维度,1个数据值:field_01, field_ ...

Btree,在数据量很大的时候,对检索性能影响很小,应该是对数级别,底是每个数据块的节点数。
你这个题目,要看看是否选中索引,还有你的提取语句是否优化。

绑定变量否,硬解析还是软解析,是否正确使用游标,是否批量操作。
你这个题目,我用ORACLE做应该在1秒以内。去年做过这个。1000个记录(1000个KEY)一批,每批在18~70ms。加上并行处理,每秒处理27000~36000记录。

http://www.itpub.net/thread-1938103-1-1.html

当时的任务,从基层传来数百万的数据,要在数亿的数据表里查询是否有重复,把没有重复的插入表中。就是一个大的检索,要求速度快。每秒至少5000个才能跟上数据上传。

论坛徽章:
223
2022北京冬奥会纪念版徽章
日期:2015-08-10 16:30:32操作系统版块每日发帖之星
日期:2016-05-10 19:22:58操作系统版块每日发帖之星
日期:2016-02-18 06:20:00操作系统版块每日发帖之星
日期:2016-03-01 06:20:00操作系统版块每日发帖之星
日期:2016-03-02 06:20:0015-16赛季CBA联赛之上海
日期:2019-09-20 12:29:3219周年集字徽章-周
日期:2019-10-01 20:47:4815-16赛季CBA联赛之八一
日期:2020-10-23 18:30:5320周年集字徽章-20	
日期:2020-10-28 14:14:2615-16赛季CBA联赛之广夏
日期:2023-02-25 16:26:26CU十四周年纪念徽章
日期:2023-04-13 12:23:10操作系统版块每日发帖之星
日期:2016-05-10 19:22:58
发表于 2017-10-25 20:44 来自手机 |显示全部楼层
反正你的要求,能转换nosql就主动转,既然用到btree了就老实接受这一切。ps该数据结构是为磁盘存储系统设计的

论坛徽章:
89
水瓶座
日期:2014-04-01 08:53:31天蝎座
日期:2014-04-01 08:53:53天秤座
日期:2014-04-01 08:54:02射手座
日期:2014-04-01 08:54:15子鼠
日期:2014-04-01 08:55:35辰龙
日期:2014-04-01 08:56:36未羊
日期:2014-04-01 08:56:27戌狗
日期:2014-04-01 08:56:13亥猪
日期:2014-04-01 08:56:02亥猪
日期:2014-04-08 08:38:58程序设计版块每日发帖之星
日期:2016-01-05 06:20:00程序设计版块每日发帖之星
日期:2016-01-07 06:20:00
发表于 2017-10-25 20:46 |显示全部楼层
yulihua49 发表于 2017-10-25 18:11
Btree,在数据量很大的时候,对检索性能影响很小,应该是对数级别,底是每个数据块的节点数。
你这个题 ...

多谢,我去看看你贴的链接。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-10-25 22:50 |显示全部楼层
本帖最后由 yulihua49 于 2017-10-25 23:00 编辑
action08 发表于 2017-10-25 20:44
反正你的要求,能转换nosql就主动转,既然用到btree了就老实接受这一切。ps该数据结构是为磁盘存储系统设计 ...

用nosql,唯一主键问题也是解决不了,也是得用Btree。
也有用散列表的,但是有一定的局限性。
在数亿数据中找几百万个,你有啥好办法?先别说sql,nosql,先说说算法吧。

我那个办法(是办法,不是算法,算法是数据库弄的)是写了程序,做了测试的。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-10-25 23:12 |显示全部楼层
本帖最后由 yulihua49 于 2017-10-26 09:04 编辑
yulihua49 发表于 2017-10-25 18:11
Btree,在数据量很大的时候,对检索性能影响很小,应该是对数级别,底是每个数据块的节点数。
你这个题 ...

我们这个任务倒是很简单,在收集数据时去掉重复的。这个操作用简单的主键唯一来控制,效率是很低的,就如楼主的情况。
高效的处理方法是:批量+并行。就是检索和插入都要批量进行。链接里说到了如何进行批量检索。之后的操作是在每个批次中挑出不重复的(就是检索没有的),重新组成一个批次进行插入。
而且,不仅新数据不能与数据库内的老数据重复,而且新数据内互相也不能重复,批次内不能重复,批次间也不能重复。这在并行处理中特别重要,同时并行的多个批次间出现的重复也必须剔除。
完成所有这些要求,我们的总处理速度是每秒27000~35000条记录。


论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-10-26 09:04 |显示全部楼层
yulihua49 发表于 2017-10-25 23:12
我们这个任务倒是很简单,在收集数据时去掉重复的。这个操作用简单的主键唯一来控制,效率是很低的,就如 ...

说了这么多,就是表明,Btree本身的处理速度没有问题,主键的插入速度和检索速度都没有问题,关键是你怎样使用它。

你的速度慢,重要原因是时间花在了:
网络传输。SQL解析。磁盘存取。

在1G网上,传输一个来回需要30微秒。每个语句解析一次SQL耗时也很可观。
所以,使用批量处理,一次传输1000个记录,解析一次SQL也是处理1000个记录,可以大大提高效率。再加上并行处理。

论坛徽章:
89
水瓶座
日期:2014-04-01 08:53:31天蝎座
日期:2014-04-01 08:53:53天秤座
日期:2014-04-01 08:54:02射手座
日期:2014-04-01 08:54:15子鼠
日期:2014-04-01 08:55:35辰龙
日期:2014-04-01 08:56:36未羊
日期:2014-04-01 08:56:27戌狗
日期:2014-04-01 08:56:13亥猪
日期:2014-04-01 08:56:02亥猪
日期:2014-04-08 08:38:58程序设计版块每日发帖之星
日期:2016-01-05 06:20:00程序设计版块每日发帖之星
日期:2016-01-07 06:20:00
发表于 2017-10-26 20:43 |显示全部楼层
yulihua49 发表于 2017-10-25 18:11
Btree,在数据量很大的时候,对检索性能影响很小,应该是对数级别,底是每个数据块的节点数。
你这个题 ...

问一个问题,如果整个表有50G,其中有25G的索引,在这种情况下,如果内存只有16G是不是会很慢?我现在担心是不是我这个机器的内存不够大。

虽然公司有不少服务器,但是部门内部一直都是用台式机来搞,我想升级成服务器,但是不知道会不会有比较明显的效果。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-10-26 21:46 |显示全部楼层
本帖最后由 yulihua49 于 2017-10-26 21:54 编辑
fender0107401 发表于 2017-10-26 20:43
问一个问题,如果整个表有50G,其中有25G的索引,在这种情况下,如果内存只有16G是不是会很慢?我现在担 ...

不会慢。如果是多核会好些。另外看看磁盘速度,磁盘总线速度。
换服务器会有一定效果。
但是优化软件比硬件提升效果大得多。
像我那个例子,纯软件优化,就从每秒1500提升到27000,硬件升级怎么也没有这么多。
硬件升级多核,软件还是单线程 ,没有作用的。

论坛徽章:
44
15-16赛季CBA联赛之浙江
日期:2021-10-11 02:03:59程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:452016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:3615-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2017-10-27 13:46 |显示全部楼层
回复 8# fender0107401

不管慢不慢,内存总是要加的,你看我现在用的台式机都64G了……
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP