用何種數據結構存儲大量IP四元組能夠獲得較高的查詢效率？

12-28

我們知道如果是存儲一組IP地址的話，Radix Tree可以獲得非常好的查找效率，但是如果是存儲IP四元組（srcip, srcport, dstip, dstport，也可能加上協議號成為五元組）的話，Radix Tree的深度擴大一倍，容量也跟著擴大，在空間和時間上的效率還是否能夠保證呢？對四元組作Hash以後存進Hash表也是一種選擇，但是查詢速度應該是不如Radix Tree的，應該是由於Hash的碰撞導致的吧？

Linux kernel 用的是一個 hash table (Linux/include/net/inet_hashtables.h)，插入函數 inet_ehash_insert，其 hash function 是 __inet_ehashfn。注意 local port 是 host endian，其餘是 network endian。ehash 的初始化在 Linux/net/ipv4/tcp.c，注意其buckets數目是kernel啟動時設置的 thash_entries，沒有rehash功能。

這是取決於你做什麼樣的查找啊，你如果要五元組精確匹配，那肯定是Hash效率最高。但是前綴樹是用來解決前綴查找的問題的，給一個CIDR然後查找所有匹配的IP地址，或者反過來，給一堆CIDR然後查找IP對應的CIDR，這些你用Hash是解決不了的。字典樹前綴查找的效率最壞情況下也是常數，無非常數大小的問題，其實沒有什麼變壞的問題。
問題還是在於需求，如果是五元組，某些需求其實不是前綴查找，比如說防火牆源IP和目的IP都是CIDR，然後跟給定的源IP、目的IP匹配，這並不是個前綴查找的問題，因為可能有多個源CIDR都跟給定的源IP匹配，這種時候就需要設計新的演算法來配合這些數據結構了。

hash碰撞率高的話重新設計一下hash函數就好……不存在不能用的。

然後來估算效率。ip一個32位，埠16位，兩組共96位的狀態空間。2^96很大，私以為大多數應用中幾乎不可能用到超過2^30組的情況。如果用任何搜索樹進行處理，複雜度與節點總數直接相關；用hash的話則與hash方法有關，然而總計12個位元組的狀態描述進行hash，在上述規模2^30條記錄的情況下，與任何搜索樹的性能差應當是不大的。

redix tree也是個logn級的時間複雜度；hash是常數級與hash函數複雜度有關。如果只是用庫，自己試試就好。如果願意研究演算法，建議學會分析時間複雜度。

近期（約過去一年）在做的一個項目是（和題主的描述非常類似）：對於一個巨大的要求嚴格匹配的表，特別是name非常長、查詢出來的value非常短的情況下，如何盡量快地執行查詢。
===============
已有的做Forwarding Information Base的方案大致可以歸為如下幾類
1. 用樹之類的結構（sigcomm 2014 中科院那一篇SAIL，2015 日本那篇Portire）
2. 用Bloom filter之類的方案（如BUFFALO）
3. 用比較牛逼的hash table的方案（如CMU組發了一堆文的 CuckooSwitch以及ScaleBricks）

對於這個具體的問題，1大概不適合。所以大概就是2或者3啦。
===============
然而我們有一個（在我們的實驗平台上可以獲得差不多是上述方案4到5倍的查詢速度的）（我認為還是有點意思的）方案。具體細節私信題主啦。
===============

等等……
IPv4地址難道不是四位元組的無符號整數嗎？埠號是unsigned short類型
為什麼需要動用樹和hash來存儲和搜索？

IPv4地址分四段，每段一個位元組，完全是範圍很窄的整數排序查找問題。
IPv6稍微複雜點，分八段，每段兩個位元組，但是還是整數排序查找問題。

補充一些信息
我比較難以理解的是，hash排序是利用一組數據的hash值進行排序，哈市值一般是整型。
IP地址已經是整型了，再hash一遍毫無意義啊？
自定義數據結構，要麼在每次插入時排序，要麼在數據插入完之後一次性排序，總之避免不了排序，排好序才好查找。
我的建議是別想什麼自定義數據結構了，使用Sqlite，分五個列插入，IP是unsigned int，埠是unsigned short，協議號看你需要的範圍了，五個列全部index。空間和時間全部有保證。sqlite既可以使用內存資料庫也可以使用文件資料庫，比你這種方法靠譜多了。

Fast IP Routing with LC-Tries

https://github.com/torvalds/linux/blob/master/net/ipv4/fib_trie.c

https://www.kernel.org/doc/Documentation/networking/fib_trie.txt

其實一個一個比較查詢效率肯定夠用，如果一定要用高大上的數據結構，個人感覺上hash最快，這個是肯定的，一共才20來bytes大小，網上找個快點的hash方法是沒問題的。

存資料庫

ip地址實際上是int32……

這個可以用空間來換時間。

32bit的IP地址，一共4G個數量，每個IP地址的數據（SrcIP, DstIP, SrcPort, DstPort）佔用了 4+4+2+2= 12位元組內存，因此最大佔用 4G*12=48G位元組的內存。

把伺服器的內存加到64G，分配一個48G位元組的內存塊。

BYTE* pBase = new BYTE(48G)

用SrcIP作為索引，存儲地址數據：
memcpy( pBase+srcIP*12, pSrcData, 12)

檢索地址數據：
pSrcData = pBase+srcIP*12

這個檢索速度是最最快的，哈哈。