如何在C#中高效索引和搜索IPv4地址范围

Question

我有大约90000个IPv4地址范围，每个范围都有相关的数据。

例如：

1.0.0.0 - 1.1.0.0 ->  "foo"
2.0.0.0 - 10.0.0.0 -> "bar"

给定一个IP地址，我需要检索相关的数据。我该如何以高效的方式实现这个功能？

我想通过将地址转换为单个整数来简化事情，但是使用什么数据结构来存储这个数据以实现快速搜索最好呢？

澄清一下 - 我正在搜索单个IP，而不是范围（例如“192.168.0.1”）。

谢谢。

- Andrew Bullock

---

IPv4地址只是32位整数。将它们存储为这样的整数，搜索变得非常简单。 - Marc B

这些范围没有重叠，对吗？ - Sergey Kalinichenko

@AndrewBullock，代码中目前如何表示范围和数据？ - SimpleVar

Answer 1

将单个数组中不重叠区间的端点排序。使用标记表示每个端点是区间的开始还是结束，例如：

1.0.0.0 1.1.0.0 2.0.0.0 10.0.0.0
 start   end     start    end

现在使用目标地址运行二分搜索，例如3.2.1.0。插入点落在2.0.0.0上，标记为start。这意味着3.2.1.0是其中一个区间。

现在考虑搜索1.2.3.4。它的插入点落在1.1.0.0上，标记为end。由于1.2.3.4不等于1.1.0.0，我们知道1.2.3.4不是其中一个区间。

搜索的成本是Log(N)，其中N是区间数。

如果你感到有冒险精神，请考虑实现一个区间树。但对于非重叠区间来说，这可能并不值得。

- Sergey Kalinichenko

---

我喜欢这个，看起来很有道理 :) - Andrew Bullock

Answer 2

如果您只需要支持IPv4地址而不是IPv6地址，您可以将每个地址存储为UInt32。这将使它们之间的比较非常容易和高效。

如果IP范围不重叠，并且您可以将它们按顺序排列在列表中，那么您可以使用二分搜索的变体来快速查找范围。

- Guffa

---

如果你有一组10000个连续的IP地址，你会存储10000个整数吗？其实你只需要存储2个整数（范围的第一个和最后一个）。这样虽然检索速度快且适当建立索引，但并不是内存高效的做法。 - SimpleVar

非常可能。你只是在谈论如何存储IP本身吗？如果是的话，那并没有真正回答OP的问题。 - SimpleVar

能否再详细解释一下呢？我了解二分查找，但它怎么帮助我找到我的IP属于哪个范围呢？ - Andrew Bullock

啊，我想我真正需要找到的只是范围的起始位置，因为如果列表已经排序，下一个范围的起始位置将大于我的值。是的...一切变得清晰了。 - Andrew Bullock

@AndrewBullock：要找到范围，你可以简单地循环遍历范围并检查地址是否在范围内。使用二分搜索只会改变您将地址与哪些范围进行比较，将平均比较次数从45000减少到最多17次。 - Guffa

Answer 3

找出0到20（包括20）之间的数字，分别在以下范围内：

2-5 -> "a"
6-7 -> "b"
9-11 -> "c"
12-12 -> "d"
15-18 -> "e"
19-19 -> "f"

在一个循环中执行1000000次，包括1次RangeCollection的创建和初始化：仅需3秒钟！

你需要做的就是准备一个Tuple的IEnumerable，其中第一个int是最小IP int值，第二个是最大值，TValue是与该min~max范围相关联的数据。

这是我的实现：

public class RangeCollection<TValue>
{
    private readonly int[] _mins;
    private readonly int[] _maxs;
    private readonly TValue[] _values;

    public RangeCollection(params Tuple<int, int, TValue>[] input)
        : this((IEnumerable<Tuple<int, int, TValue>>)input)
    {
    }

    public RangeCollection(IEnumerable<Tuple<int, int, TValue>> input)
    {
        var tuples = input.OrderBy(tuple => tuple.Item1).ToArray();

        for (var i = 1; i < tuples.Length; i++)
        {
            if (tuples[i].Item1 <= tuples[i - 1].Item2)
            {
                throw new ArgumentException("Ranges should not overlap.");
            }
        }

        this._mins = new int[tuples.Length];
        this._maxs = new int[tuples.Length];
        this._values = new TValue[tuples.Length];

        for (var i = 0; i < tuples.Length; i++)
        {
            var tuple = tuples[i];

            this._mins[i] = tuple.Item1;
            this._maxs[i] = tuple.Item2;
            this._values[i] = tuple.Item3;
        }
    }

    public bool TryGetValue(int key, out TValue value)
    {
        if (this.Contains(key, out key))
        {
            value = this._values[key];
            return true;
        }

        value = default(TValue);
        return false;
    }

    public bool Contains(int key)
    {
        return this.Contains(key, out key);
    }

    private bool Contains(int key, out int index)
    {
        index = 0;

        if (this._mins.Length == 0 || key < this._mins[0] || key > this._maxs[this._maxs.Length - 1])
        {
            return false;
        }

        var low = 0;
        var high = this._mins.Length - 1;

        while (high >= low)
        {
            index = (low + high) / 2;

            var cmp = this._mins[index].CompareTo(key);

            if (cmp == 0)
            {
                return true;
            }

            if (cmp == 1)
            {
                high = index - 1;
            }
            else
            {
                low = index + 1;
            }
        }

        if (this._mins[index] > key)
        {
            index--;
        }
        else if (this._mins[index + 1] <= key)
        {
            index++;
        }

        return this._maxs[index] >= key;
    }
}

使用方法：

var collection = new RangeCollection<string>(new Tuple<int, int, string>(2, 5, "a"),
                                             new Tuple<int, int, string>(6, 7, "b"),
                                             new Tuple<int, int, string>(9, 11, "c"),
                                             new Tuple<int, int, string>(12, 12, "d"),
                                             new Tuple<int, int, string>(15, 18, "e"),
                                             new Tuple<int, int, string>(19, 19, "f"));

for (var i = 0; i <= 20; i++)
{
    string val;
    if (collection.TryGetValue(i, out val))
    {
        Debug.WriteLine("Contains {0}. Value: {1}", i, val);
    }
    else
    {
        Debug.WriteLine("Doesn't contain " + i);
    }
}

/* Output:

Doesn't contain 0
Doesn't contain 1
Contains 2. Value: a
Contains 3. Value: a
Contains 4. Value: a
Contains 5. Value: a
Contains 6. Value: b
Contains 7. Value: b
Doesn't contain 8
Contains 9. Value: c
Contains 10. Value: c
Contains 11. Value: c
Contains 12. Value: d
Doesn't contain 13
Doesn't contain 14
Contains 15. Value: e
Contains 16. Value: e
Contains 17. Value: e
Contains 18. Value: e
Contains 19. Value: f
Doesn't contain 20

*/

- SimpleVar