有效地查找表中不存在的第一个数字 - efficiently find first number that do not exist in a table?

efficiently find first number that do not exist in a table?

我有一个大约有528829行的表，它看起来像

CREATE TABLE `ips` (
  `id` INTEGER PRIMARY KEY AUTOINCREMENT,
  `ip` INTEGER NOT NULL DEFAULT NULL,
  `scantime` INTEGER NULL DEFAULT NULL,
  `pingable` INTEGER NULL DEFAULT NULL
);

现在我需要找到ip中不存在的第一个数字，从0开始，一直到4294967295（又名0xFFFFFFFF），

目前我只使用

function isScanned($ip){
    static $isScannedStm=false;
    static $boundip=0;
    if($isScannedStm===false){
    global $db;
    $isScannedStm=$db->prepare('SELECT 1 FROM `ips` WHERE `ip` = :ip LIMIT 1');
    $isScannedStm->bindParam(':ip',$boundip,PDO::PARAM_INT);
    return isScanned($ip);
    }
    $boundip=$ip;
    $isScannedStm->execute();
    //var_dump($isScannedStm->fetch(PDO::FETCH_NUM));
    return !!($isScannedStm->fetch(PDO::FETCH_NUM));
}
//~~~
    while(isScanned($i)){
        ++$i;
    }

它是有效的，但有528829行，在我的英特尔Atom C2750@2.4GHz上需要1小时30分钟。我如何更快地找到这个值？最好快得多？

我只在MySQL中测试过这一点，希望它也适用于SQLite

SELECT ips.ip+1 AS Missing 
FROM ips
LEFT JOIN ips AS next ON ips.ip+1 = next.ip
WHERE next.ip IS NULL 
ORDER BY ips.ip LIMIT 1;

Caspar和splatru的解决方案：https://stackoverflow.com/a/6464763/1078488

您可以考虑执行某种"二进制搜索"。从连续数字的前半部分开始[1, 2, 3, ... (n/2)]

如果结果的数量不等于当前列表中连续值的数量，那么您可以拆分初始列表并通过相同的逻辑重新运行，继续运行，直到获得第一个非连续id。

否则，如果计数匹配，则转到连续ID的另一半。

然后，您的查询将需要包含一个WHERE...IN子句。

这对你来说不会完全起作用，但也许这会有所帮助：

// Populate current set of consecutive integers
$list = array_fill(0, $count/2);
$listQuery = implode(',', $list);
global $db;
$isScannedStm = $db->prepare('
    SELECT 1 FROM `ips` 
    WHERE `ip` IN ('.$listQuery.') 
    GROUP BY `ip` 
    ORDER BY `ip` ASC
');
$isScannedStm->execute()
// Check num results 
if (count($list) !== $isScannedStm->fetch(PDO::FETCH_NUM)) {
    // Split the initial list in half 
    // OR loop through results and find when the ids are not consecutive   
}

可能有一种更简单的方法可以做到这一点，也许可以考虑看看这个问题