今天在blog里面写了两篇关于BSD radix树路由表设计原理的文章： http://blog.chinaunix.net/index.php?blogId=9831 也算是一个把自己对BSD的学习心得公之于众的开始吧。热切地期待着大家的指正！ 再次感谢xie_minix，是他的文章拉近了我和radix.c的距离。 [ 本帖最后由 雨丝风片 于 2005-11-22 18:17 编辑 ]

原来在这里没有专门讨论BSD内核和程序开发的版块，所以有些东西就先写在blog里了。BSD程序开发版开张之后，这些东西就该逐步搬家了！:D 我一直相信，最好的学习应该是开放式的，让大家一起来考虑一个问题会比一个人冥思苦想的效率要高得多。事实上，下面这篇最先发表在我的blog里的关于BSD radix树路由表的文章就曾经得到过多位朋友的指正，非常感谢他们！以下是原文，继续期待各位朋友的指正！:D 本文pdf版本： 在这里写下我的...

2.6内核中页高速缓存部分引入了 radix tree结构,中文翻译成基树. 有同事说看其搜索算法是多级hash表,数据确实是散列存放的, 但是现在用google,这两个概念都没有搜到. 有没有人知道这两个概念,它们是不是等同? 谢谢!

在第一部分介绍完BSD radix树路由表的表头、节点、条目等数据结构之后，本部分将集中介绍BSD radix树路由表的查找、添加和删除算法。 目录：4 BSD路由表的路由查找：寻叶、辨重、回溯； 5 BSD路由表的路由添加：寻叶求异、存异求同、普适提升； 6 BSD路由表的路由删除：独有一叶、父子同源无后继、父子同源有后继、父子异源无后继、父子异源有后继。 4 BSD路由表的路由查找 前已述及，BSD路由表使用的是经BSD修改之后的Patric...

首先我的理解是这样的： 1. 在/usr/src/sys/net/radix.c中有一些全局变量如rn_zeros、rn_ones，并且有人全局的树mask_rnhead，这些都在route_init()->rn_init()时初始化。然后在route_init()中调用各domain的dom_rtattach函数最终调用rn_inithead初始化自己的Tree。 2. 其它使用radix tree的模块如ipfw直接调用rn_inithead初始化自己的Tree。radix Tree的机制没有完全搞清楚，这里不明白的是，全局的Tree在其它Tree被操作时只要使用...