忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 文库 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 1127 | 回复: 4

[C++] 关于STL中map的一个奇怪问题 [复制链接]

论坛徽章:
6
2015年迎新春徽章
日期:2015-03-04 10:16:53操作系统版块每日发帖之星
日期:2015-08-04 06:20:002015亚冠之鹿岛鹿角
日期:2015-08-05 16:51:182015亚冠之全北现代
日期:2015-08-07 17:14:392015亚冠之武里南联
日期:2015-08-11 15:33:03数据库技术版块每日发帖之星
日期:2016-02-02 06:20:00
发表于 2018-09-23 23:55 |显示全部楼层
我们知道stl中map的底层是用红黑树实现的,unordered_map是用hash实现的。
我有一个疑问,当初实现map的时候为啥不用B+树而是选择了红黑树了?

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2018-09-29 12:00 |显示全部楼层
有什么奇怪的?B+树一般适合大型数据。

论坛徽章:
0
发表于 2018-09-29 13:18 |显示全部楼层
因为红黑树比B+树好啊。  当然,要看你的用途,在内存里,红黑树比B+树好。

而在大型数据索引的用途上,红黑树却根本不可行,而B+树好得多。因为,一个大表的索引也仅需几次从磁盘的读取“页”的I/O就够了,而红黑树需要更多的次数(与索引量的二倍对数相关)。

论坛徽章:
43
15-16赛季CBA联赛之四川
日期:2018-10-13 23:26:5015-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:36程序设计版块每日发帖之星
日期:2016-07-02 06:20:0015-16赛季CBA联赛之天津
日期:2016-11-02 00:33:1215-16赛季CBA联赛之浙江
日期:2017-01-13 01:31:49
发表于 2018-10-06 15:49 |显示全部楼层
B+树在内存里的效率没有红黑树高,因为B+Tree中非叶子节点不存数据,所以B+Tree一般用在外存上,比如数据库,记录放一起,上层索引节点放一起。
不过话说回来,BTree(不是B+Tree)和RBTree其实各方面都差不多,如果合理选择分叉数搞不好BTree有时候还能快一点。

说到底也就是最初的作者的一个选择而已,你要用BTree重新实现一个map也没问题,具体的性能还是要做过benchmark才知道。

评分

参与人数 1信誉积分 +10 收起 理由
lxyscls + 10 很给力!

查看全部评分

论坛徽章:
131
操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57数据库技术版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:052022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57IT运维版块每日发帖之星
日期:2016-05-11 17:06:49操作系统版块每日发帖之星
日期:2016-05-11 17:06:57综合交流区版块每日发帖之星
日期:2016-05-11 17:07:05操作系统版块每日发帖之星
日期:2016-05-11 17:06:57程序设计版块每日发帖之星
日期:2016-05-11 17:06:57
发表于 2018-10-11 19:15 来自手机 |显示全部楼层
就是因为应用场景一个是内存,一个是磁盘
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:wangnan@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP