在 MySQL table 中使用已删除的行 PHP 进行二进制搜索

Question

我有一个大的 MySQL table 数据排序。当我需要找到起点时，我会执行二进制搜索以找到下界 ID（自动递增）。唯一的问题是，一旦某些数据被删除，如果算法给出的 ID 不存在，我需要查看 ID 较低的第一个现有行。我应该如何修改此代码以实现此目的？

$l = 1;
$h = $max; //SELECT MAX(id)
while ($h - $l > 1){
  $m = ($h + $l) / 2;
  $q = mysqli_query($db, "SELECT col FROM tab WHERE id=". floor($m));
  $result = array();
  while($result[] = mysqli_fetch_row($q)){;}
  if ($result[0][0] < $val) $l = $m;
  else $h = $m;
}
echo round($m);

例如，我想查找哪些行的 col 值大于 12345，而 table 的最大 ID 为 10000。我首先查看第 5000 行，其中 col = 9000，然后是 7500（ col = 13000)，然后 6250 已被删除，所以我开始寻找 ID < 6250 的第一个现有行，我发现 6245 的 col = 10500。现在我正在寻找 ID 6873 和 7500 等

Answer 1

正确的做法

所以你有一个像这样的table：

| ID  | col |
---------------
| 1   | 15  |
| 3   | 155 |
| 18  | 9231|
| 190 |14343|
| 500 |16888|

您可以通过以下查询找到 14343：

SELECT ID, col FROM the_table WHERE col>12345 LIMIT 1;

为了让它更快，你需要添加一个索引（索引词值得谷歌搜索）

ALTER TABLE `the_table` ADD INDEX `col` (`col`);

之后 mysql 将在内部创建一个树结构并且 将为您对其进行二进制搜索。

这将工作得更快，因为您将避免多次网络往返 + 其他每个请求的费用（查询解析、优化、所有锁和互斥锁，...）

回答你的问题

I need to look at the first existing row with a lower ID

例如你想获得 ID < 300 的第一行，你这样做（限制是使查询 return 只有 1 个结果的原因）：

SELECT col FROM the_table WHERE ID < 300 LIMIT 1;

在 MySQL table 中使用已删除的行 PHP 进行二进制搜索

Binary search in a MySQL table with deleted rows PHP

mysql

binary-search

正确的做法

回答你的问题