如何有效地存储 IP 地址和 CIDR 范围

Question

我有一个用例，我不知道如何解决。我在这里要求它获得一些关于我需要学习什么来解决这个问题的指导。

• 我需要存储 IP 地址（很多，可能是几亿）。这些可以是1.1.1.2或CIDR范围如1.1.1.1/24

要求如下

- Save all the IP address which comes as above format in-memory
- Search should work as following  
   - if I have IP address as 1.1.1.2 and 1.1.1.1/24, it should match the specific IP address 1.1.1.2 and not the CIDR range it falls into (1.1.1.1/24)
   - If specific IP address is not found but CIDR range is available, CIDR range is returned
   - if no match is found, return null/throw exception

问题
- 什么数据结构可以帮助我解决这个问题？尝试？- 你会采取什么方法？- 如何确保它不会消耗太多内存并且搜索速度很快（会有一些合理的权衡）

谢谢

Answer 1

我会使用二叉树（这种树称为基数树）：

1. IP 地址的位用于从 MSB 开始导航（例如 0 = 左子节点和 1 = 右子节点）
2. 所有特定的 IP 地址都是叶子，而 CIDR 范围是内部节点（使用虚拟叶子来指示“丢失”的 IP 地址，就像在红黑树中一样）
3. 一些节点将是您拥有的实际数据，其他只是“导航”节点（它们对应于您没有的 CIDR 范围，用标志标记它们）

搜索：只需使用您拥有的地址在树中导航。如果您最终处于叶子中，那么您将拥有该特定 IP 地址，否则带有标志的“最低”节点（参见第 3 点）是您拥有的最具体的 CIDR 范围。

示例：让我们使用 8 位 IP 和 2 位“部分”地址；插入 1.1.1.0/6 后，树将是（IP 后面的数字是“包含”标志，nils 是虚拟叶子）

    <root> -- nil
      |
00.00.00.00/1 (0) -- nil
      |
01.00.00.00/2 (0) -- nil
      |
01.00.00.00/3 (0) -- nil
      |
01.01.00.00/4 (0) -- nil
      |
01.01.00.00/5 (0) -- nil
      |
01.01.01.00/6 (1) --nil
      |
     nil

如果您查找 IP 地址 1.1.1.1，您将在 1.1.1.1/6 处停止，这是一个 CIDR 范围，因为它有 nil 子项，并且是最具体的（在树中）。如果您现在插入 1.1.1.1 树将是

    <root> -- nil
      |
00.00.00.00/1 (0) -- nil
      |
01.00.00.00/2 (0) -- nil
      |
01.00.00.00/3 (0) -- nil
      |
01.01.00.00/4 (0) -- nil
      |
01.01.00.00/5 (0) -- nil
      |
01.01.01.00/6 (1) -- nil
      |
01.01.01.00/7 (0) -- nil
      |
01.01.01.01 (1)

1.1.1.1 没有叶子，因为它是一个 IP 地址。最后让我们插入 1.1.2.1

    <root> -- nil
      |
00.00.00.00/1 (0) -- nil
      |
01.00.00.00/2 (0) -- nil
      |
01.00.00.00/3 (0) -- nil
      |
01.01.00.00/4 (0) --------------------+
      |                               |
01.01.00.00/5 (0) -- nil        01.01.10.00/5 (0) -- nil
      |                               |
01.01.01.00/6 (1) -- nil        01.01.10.00/6 (0) -- nil        
      |                               |
01.01.01.00/7 (0) -- nil        01.01.10.00/7 (0) -- nil
      |                               |
01.01.01.01 (1)                 01.01.10.01 (1)