开源世界中的算法与数据结构 3 -- Linux IPv6 FIB表实现
这篇讲的是Linux IPv6 FIB（转发信息库）实现的演进。作者从IPv4 FIB的实现局限性出发，探讨了直接将其扩展到IPv6的可行性——如果照搬IPv4的哈希链表方案，最坏情况下需要进行128次哈希计算和链表遍历，效率堪忧。文章随后切入正题，展示了Linux内核2.6版本实际采用的解决方案：使用Patricia（基数）树来重构IPv6 FIB。这不仅是一次数据结构的替换，更体现了对IPv6巨大地址空间的工程适配，通过树形结构显著提升了查找效率与扩展性，让网络栈能更优雅地应对新一代协议的挑战。