当前，网络化与信息化突破了时间和地域的限制，已成为全球化不可抗拒的世界潮流。目前互联网正与电话网、电视网、无线网、卫星网相结合，互联网在商业运作的驱动下，更加迅猛地发展。但是同时，网络的安全形势也同时越来越严峻。而防火墙作为网络安全的重要组成部分，其性能是非常重要的。防火墙的发展经历了五个时代，目前带状态监测的防火墙是防火墙技术的主流。在防火墙的性能上，过滤规则库的搜索和状态监测表的搜索、维护是关键。这两个方面的技术目前在国内外都研究得比较多。但是相对于网络应用的不断发展，尤其是近年来的宽带网络技术发展，还是有很大不足。在很多场合下，防火墙的性能已经成为网络带宽的瓶颈问题。本文在带状态监测的防火墙结构基础上，首先从总体上设计了整个防火墙的结构，进而研究了过滤规则库和状态监测表的搜索、维护问题，提出了将计算几何学、图论中的数据结构和算法引入防火墙的设计的方式，将基础理论应用到实践中来。在过滤规则库的搜索过程中，本文将规则库视为一个三维空间中有重叠的长方体集合，在规则库中搜索数据包匹配的规则，则转化为在长方体集合中搜索点所处的长方体的问题。参考了计算几何中在一个平面上多个不重叠的矩形中定位的算法，设计出初始化算法和搜索算法。在状态监测表的搜索、维护问题上，本文采用改进后的键树作为数据结构，并且设计了改进的键树的存储方案、在其上的搜索、添加、删除结点等的算法。除了将这些方面的数据结构与算法引入防火墙外，本文还进行了这些方法和其它一些实现方法之间的比较，综合分析了各自的优点与缺点，为将来从事设计的人员提供了一个参考。