路由表的结构与算法分析--trie插入

简介:

在linux的trie树中插入一条路由是很复杂的,远比查找要复杂的多,因为每插入一条路由就要看看是否要动态调整trie树,不是还好,如果要动态调 整,那活儿就大了,正是因为这一点,trie路由表往往在大型的机器上用到,那些机器不吝啬动态调整trie树的时候的空间损失,如果是性能不那么靠铺的 机器,还是老老实实用哈希路由表吧,只要不是疯狂插入很多路由表导致很多哈希碰撞,性能是很棒的,我在pc上装过trie,一旦路由条目大了,内存疯狂耗 尽,要知道,路由表用的可是内核内存阿,不被换出的。bsd一向巨猛,unix嘛,linux一向不管那么多,代码凌乱而有序,要懂得欣赏,仔细品味才有收获。 
bsd以前的路由表是基于二叉radix树的,而现在是固定多分枝trie树,具体就是32位分为4段,然后类似于页目录页表那样多叉树搜索,如果是二叉 树的,那么只要访问路由表就要锁住全树,这么说好像多分枝树就不用锁了一样,错了,同样要锁,不同之处在于二叉树如果只锁一个节点那么对下面同样影响很大,想象一下如果锁住了根的左孩子,那么满树的情况下一半的节点都要受影响,但是多分枝就不同了,比如n分枝,如果锁住根的第m孩子(m如果一位一位的比较,那么就是二叉radix树,,因为一位非0即1,所以树就有2个孩子,如果32位32位比较,那么就是2的32次方叉树,也就是根节 点有2的32次方个孩子,所有的ip地址每个为一个孩子,世界上没有哪个路由表是这么实现的,还是二叉树的好一些,但是考虑到前面说的缺点,bsd改进了 radix树,使之成为固定分支的trie树,实质和二叉radix树是一样的。linux来了,世界不吭气了,你不是说叉数多了不好,少了又有这样那样 的缺点,bsd来了个折中,不多不少,2的8次方,在数字上来个折中,linux则更进一步,在动态效果上来了个折中,也就是说,linux的trie完 全动态,游走于二叉和2的32次方叉之间,看你还怎么说,即使你说m叉正好,那么盯着linux几分钟,更新一下路由表,它确实到了m叉,如果你说n叉很 糟糕,但linux这时确实是n叉树,那么继续盯几分钟,插入几条路由或删除几条,哈哈,不是n叉了吧,这一切是怎么实现的呢?这正是我这篇文章要说的动态trie树的插入。来吧,看代码:

static



 本文转自 dog250 51CTO博客,原文链接:http://blog.51cto.com/dog250/1274167

相关文章
|
8天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
31 0
|
2天前
|
搜索推荐 算法 程序员
常见排序算法及其稳定性分析
常见排序算法及其稳定性分析
|
2天前
|
存储 算法 搜索推荐
【大数据分析与挖掘技术】Mahout推荐算法
【大数据分析与挖掘技术】Mahout推荐算法
9 0
|
3天前
|
存储 移动开发 算法
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构(下)
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构
12 0
|
3天前
|
机器学习/深度学习 算法 搜索推荐
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构(上)
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构
9 0
|
8天前
|
机器学习/深度学习 自然语言处理 算法
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
|
8天前
|
机器学习/深度学习 算法 数据可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
Matlab决策树、模糊C-均值聚类算法分析高校教师职称学历评分可视化
|
8天前
|
算法 搜索推荐 数据挖掘
MATLAB模糊C均值聚类FCM改进的推荐系统协同过滤算法分析MovieLens电影数据集
MATLAB模糊C均值聚类FCM改进的推荐系统协同过滤算法分析MovieLens电影数据集
|
8天前
|
算法 数据可视化 数据挖掘
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
|
8天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。