algorithm - 如何有效地存储 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

我会使用二叉树(这种树称为 Radix Trees ):

1. IP 地址的位用于从 MSB 开始导航它(例如 0 = 左 child 和 1 = 右 child )
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 范围，因为它没有子级并且是最具体的(在树中)。如果您现在插入 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)