免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 5408 | 回复: 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就够了,而红黑树需要更多的次数(与索引量的二倍对数相关)。

论坛徽章:
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
发表于 2018-10-06 15:49 |显示全部楼层
B+树在内存里的效率没有红黑树高,因为B+Tree中非叶子节点不存数据,所以B+Tree一般用在外存上,比如数据库,记录放一起,上层索引节点放一起。
不过话说回来,BTree(不是B+Tree)和RBTree其实各方面都差不多,如果合理选择分叉数搞不好BTree有时候还能快一点。

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

评分

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

查看全部评分

论坛徽章:
154
2022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:5720周年集字徽章-年
日期:2022-10-26 16:44:2015-16赛季CBA联赛之深圳
日期:2022-11-02 14:02:4515-16赛季CBA联赛之八一
日期:2022-11-28 12:07:4820周年集字徽章-20	
日期:2023-07-19 08:49:4515-16赛季CBA联赛之八一
日期:2023-11-04 19:23:5115-16赛季CBA联赛之广夏
日期:2023-12-13 18:09:34
发表于 2018-10-11 19:15 来自手机 |显示全部楼层
就是因为应用场景一个是内存,一个是磁盘
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP