免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: Godbach

Linux内核中的红黑树 [复制链接]

论坛徽章:
3
金牛座
日期:2014-06-14 22:04:062015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2009-01-03 22:29 |显示全部楼层
原帖由 蚊见蚊爱 于 2009-1-3 16:45 发表
这种数据结构的东西,还是看教材,代码参考产品代码 (STL 中也有 这个数据结构, ),最好不要使用未经严格测试的代码,


STL确实比较强大
Linux内核中的这部分代码,应该是比较稳定可靠的了:wink:

论坛徽章:
0
发表于 2009-01-03 22:33 |显示全部楼层
原帖由 Godbach 于 2009-1-2 12:50 发表
请教prolj兄一个问题:
如果我想统计一段时间内和我本地主机通信的IP总数,你觉得用哪种方式实现更好?


这个rb_tree 和hash 都好,  hash 的难点就在于估算总数,在数量级可以预见的情况下,hash的性能可以令人非常满意

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-03 22:36 |显示全部楼层
原帖由 lbaby 于 2009-1-3 22:33 发表


这个rb_tree 和hash 都好,  hash 的难点就在于估算总数,在数量级可以预见的情况下,hash的性能可以令人非常满意


可以预见的情况下?
那如果我设定了hash表项最多为500,000个,应该也算可预见吧。这个时侯lbaby兄会在hash和rb_tree之间选择那个?

论坛徽章:
3
金牛座
日期:2014-06-14 22:04:062015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2009-01-03 22:42 |显示全部楼层
原帖由 lbaby 于 2009-1-3 22:33 发表


这个rb_tree 和hash 都好,  hash 的难点就在于估算总数,在数量级可以预见的情况下,hash的性能可以令人非常满意


如果树建好了后,不存在插入和删除的话,其实AVL树的性能比rbtree还占优势:wink:

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-03 22:44 |显示全部楼层

回复 #34 dreamice 的帖子

是吗。不过很多情况下建树主要就是用来动态的插入和删除吧。

论坛徽章:
3
金牛座
日期:2014-06-14 22:04:062015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:49:45
发表于 2009-01-03 22:49 |显示全部楼层
原帖由 Godbach 于 2009-1-3 22:44 发表
是吗。不过很多情况下建树主要就是用来动态的插入和删除吧。


也有用静态树的情况,这样的话用avl树性能上稍微好一些,但没有数量级的提升,都是log(N)级的。

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-03 22:51 |显示全部楼层
原帖由 dreamice 于 2009-1-3 22:49 发表


也有用静态树的情况,这样的话用avl树性能上稍微好一些,但没有数量级的提升,都是log(N)级的。

OK,以后有对应的应用可以尝试一下。

论坛徽章:
0
发表于 2009-01-04 09:43 |显示全部楼层
原帖由 Godbach 于 2009-1-3 22:36 发表


可以预见的情况下?
那如果我设定了hash表项最多为500,000个,应该也算可预见吧。这个时侯lbaby兄会在hash和rb_tree之间选择那个?



可预见的意思是,  你可以根据历史或经验估算出你要处理的数据的数量级,和你想出来的设定的那个数无关

比如:你的站点每日访问量100万,那我们就在大于 150万 小于200万之间选一个素数作为hash表项大小
如果我上边没说清,我这里补充一下

hash 表的实现简单,用起来也好用,现在的内存都是白菜价,不用白不用。
省下的时间都是自己的,泡泡妞,灌灌水, 何乐而不为捏?

论坛徽章:
0
发表于 2009-01-04 10:05 |显示全部楼层
http://lxr.linux.no/linux+v2.6.28/include/linux/hash.h

另外内核里也有不错的 hash 实现,Godbach 兄可以去看看

论坛徽章:
36
IT运维版块每日发帖之星
日期:2016-04-10 06:20:00IT运维版块每日发帖之星
日期:2016-04-16 06:20:0015-16赛季CBA联赛之广东
日期:2016-04-16 19:59:32IT运维版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-19 06:20:00每日论坛发贴之星
日期:2016-04-19 06:20:00IT运维版块每日发帖之星
日期:2016-04-25 06:20:00IT运维版块每日发帖之星
日期:2016-05-06 06:20:00IT运维版块每日发帖之星
日期:2016-05-08 06:20:00IT运维版块每日发帖之星
日期:2016-05-13 06:20:00IT运维版块每日发帖之星
日期:2016-05-28 06:20:00每日论坛发贴之星
日期:2016-05-28 06:20:00
发表于 2009-01-04 10:05 |显示全部楼层

回复 #38 lbaby 的帖子

譬如说我的设备最多就防50万个链接,再多的我都直接放过。不用添加表项。

也就是我知道我的设备就可以处理的上限。我以这个上限建表,也算固定的了

[ 本帖最后由 Godbach 于 2009-1-4 10:07 编辑 ]
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP