sql - 有效地查找子网内可用 IP 地址的列表/范围

Question

我正在尝试确定下一个可用的 IP 地址是哪个子网(基本上是一个开始的 IPv4 地址和一个结束的 IPv4 地址)和一个包含已分配的 IPv4 地址的 addresses 表。

表的简化架构:

CREATE TABLE addresses (
    address INET NOT NULL,
    -- OTHER INFORMATION ASSOCIATED WITH IP ADDRESSES --
);

当前的实现生成子网内所有可能的 IP 地址，并返回那些不在 addresses 表中的地址。

例如，给定一个起始 IP 为“192.0.0.0”且结束 IP 为“192.0.0.255”的子网，查询将如下所示:

SELECT * 
FROM (
  SELECT i + '0.0.0.0' :: inet as generated_address
  from generate_series('192.0.0.0' :: inet - '0.0.0.0' :: inet,
                       '192.0.0.255' :: inet - '0.0.0.0' :: inet) as i) as iprange
                       WHERE generated_address NOT IN (SELECT address FROM addresses);

这工作正常，但问题是对于/12 及更低的子网掩码，它开始变慢，并且对于/8 的子网掩码根本没有完成。

我正在尝试确定查找下一个可用 IP 地址的替代方法。
此外，如果我可以返回可用 IP 地址列表或范围列表(表示可用 IP 地址与不可用 IP 地址之间的差距)，那将是理想的。

在这个 post 上似乎有一些与此问题相关的好答案但我发现很难理解该帖子中的答案并将它们翻译成我在 postgres 中的情况(因为我对它还很陌生)。

数据

我不完全确定数据会是什么样子，但地址表填充方式的 3 种情况如下:

1. 稀疏(分配的 IP 地址非常少)
2. 断断续续(一半的子网已满，但之间有很多间隙)
3. 密集(使用的大多数 IP 地址)

最坏的情况可能是场景 3，因为它需要查看所有记录。

我提供了一个简单的 DB Fiddle演示了该场景。

Answer 1

我设法想出了这样的事情:

WITH gaps (start_ip, end_ip) as 
(
   SELECT
      address + 1 AS start_ip,
      next_address - 1 AS end_ip 
   FROM
      (
         SELECT
            address,
            LEAD(address) OVER (
         ORDER BY
            address) AS next_address 
         FROM
            addresses 
         where
            and address >= '192.0.0.0' :: INET -- Start Address
            and address <= '192.0.255.255' :: INET -- End Address
      )
      AS gaps 
   WHERE
      gaps.address + 1 <> gaps.next_address
)
SELECT
   generate_series(start_ip - '0.0.0.0' :: INET, end_ip - '0.0.0.0' :: INET) + '0.0.0.0'::INET as address 
FROM
   gaps

同样，其中大部分本质上是对这个 post 中答案的翻译。但我认为它仍然可以帮助其他人将它放在这里。

一般的想法是在 addresses 表(这里已经分配了地址)中寻找“差距”，这意味着两者之间的一切都是“免费的”。如果来自LEAD 的next_address 只比当前address 大1，则意味着下一个地址已被占用，没有间隙。 这是一个 DBFiddle

我仍在寻找更有效的解决方案，尤其是在地址表非常密集或已满的情况下，最坏的情况是子网中只有最后一个 IP 地址是空闲的...