免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › 内核源码 › 请问linux内核的进程地址空间为什么要用红黑树来管理阿
12下一页
最近访问板块 发新帖
查看: 3999 | 回复: 10
打印 上一主题 下一主题

请问linux内核的进程地址空间为什么要用红黑树来管理阿 [复制链接]

nqdgj2007

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2008-11-24 18:42 |只看该作者 |倒序浏览
红黑树比一般的二叉查找树相比有什么好处啊
It'sGifted

论坛徽章:
0
2楼 [报告]
发表于 2008-11-24 18:44 |只看该作者
原帖由 nqdgj2007 于 2008-11-24 18:42 发表
红黑树比一般的二叉查找树相比有什么好处啊


这个是因为Linux的线性空间（struct vm_area_struct）是连成一个链表的，但是由于线性地址空间太大，所以链表可能很长，所以用红黑树的话查找时就非常方便。可参考find_vma()
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
nqdgj2007

论坛徽章:
0
3楼 [报告]
发表于 2008-11-24 18:46 |只看该作者
恩 函数我看过了 我也明白用树形结构查找时间复杂度比较低 但是我不明白的是它比一般的二叉查找树有什么好处
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
It'sGifted

论坛徽章:
0
4楼 [报告]
发表于 2008-11-24 18:49 |只看该作者
原帖由 nqdgj2007 于 2008-11-24 18:46 发表
恩 函数我看过了 我也明白用树形结构查找时间复杂度比较低 但是我不明白的是它比一般的二叉查找树有什么好处


看数据结构
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
nqdgj2007

论坛徽章:
0
5楼 [报告]
发表于 2008-11-24 19:49 |只看该作者
数据结构里面没有  算法导论里面也没有把它和二叉查找树进行比较
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
It'sGifted

论坛徽章:
0
6楼 [报告]
发表于 2008-11-24 20:04 |只看该作者
原帖由 nqdgj2007 于 2008-11-24 19:49 发表
数据结构里面没有  算法导论里面也没有把它和二叉查找树进行比较


红黑树其实就是平衡二叉树，它可以保证树到叶子结点的深度一致，这样就能够很好的保证搜索的效率，如果是仅仅只是二叉树的话，极端情况下效果就非常差
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
nqdgj2007

论坛徽章:
0
7楼 [报告]
发表于 2008-11-24 20:07 |只看该作者
感谢楼上
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
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
8楼 [报告]
发表于 2008-11-24 22:29 |只看该作者
原帖由 It'sGifted 于 2008-11-24 20:04 发表


红黑树其实就是平衡二叉树，它可以保证树到叶子结点的深度一致，这样就能够很好的保证搜索的效率，如果是仅仅只是二叉树的话，极端情况下效果就非常差


最关键的解释就是：
红黑树其实就是平衡二叉树

偶简单学过数据结构，确实二叉树极端不平衡的时候，效果会很差
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
sunchiang

论坛徽章:
0
9楼 [报告]
发表于 2008-11-25 11:07 |只看该作者
红黑树好像和AVL不太一样，我也不是很清楚。我记得ULK第三版里面提到的进程地址空间用的AVL管理，不是红黑树，也许我记错了？有没有比较熟悉这方面的兄弟具体给说说
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
It'sGifted

论坛徽章:
0
10楼 [报告]
发表于 2008-11-25 17:44 |只看该作者
原帖由 sunchiang 于 2008-11-25 11:07 发表
红黑树好像和AVL不太一样，我也不是很清楚。我记得ULK第三版里面提到的进程地址空间用的AVL管理，不是红黑树，也许我记错了？有没有比较熟悉这方面的兄弟具体给说说



进程地址空间的管理就是红黑树
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP