給定一個ACL列表中有10十億的IPv4的CIDR notiation範圍或兩個IP地址之間：索引範圍的IP搜索算法地址
x.x.x.x/y
x.x.x.x - y.y.y.y
什麼是用於測試的effecient搜索/索引算法，給定的IP地址符合一個或多個ACL範圍的標準？
讓我們假設大多數ACL範圍定義跨越大量的C類塊。
通過散列表的索引點很容易，但嘗試一下，因爲我可能無法想出一個合理的方法來檢測哪些點被大量「行」所覆蓋。
有一些想法，如索引提示在一定程度上的細節 - 說預先計算在C級別的每個ACL覆蓋那個點，但表會太大..或某種類型的KD樹動態設置詳細程度。
也有這樣的想法，也許有碰撞檢測算法可以解決這個問題。
正確方向的任何提示或指針？
您可以查看Interval tree以查找與任何給定間隔或點重疊的所有間隔。
對於不重疊的ip範圍，可以使用b-tree或compact-tries（如Judy arrays (64-bits)）進行索引和搜索（將start-ip存儲爲key並將end-ip存儲爲值）。
在longest prefix match Internet路由查找中使用的簡單Radix Tree可以縮放，以保存代表較大的CIDR子網的節點，這些節點可以與其他較小的CIDR子網重疊。最長匹配查找將遍歷這些節點，這些節點也將被選中以獲取與IP地址匹配的整個CIDR子網組。
現在，要把IP範圍保存在同一棵樹上，我們可以convert each range into a set of CIDR subnets。儘管可能有很多子網（甚至一些主機IP - 即IP/32種CIDR地址），但這總是可以完成的。
你有100億條規則來匹配40億個可能的地址嗎？
製作一個包含40億個地址的表格。對於100億條規則中的每一條，「塗抹」它適用的地址，當兩個或更多的規則適用於相同的地址時做一些合理的事情。