mysql - 使用 SQL 高效地搜索下一个(更大的)键

Question

我有一个包含元组的表，其中时间戳(时间)不连续但(为简单起见我们可以假设)是唯一的。

time | value
------------
0    |4
3    |2
5    |6
8    |10
9    |5
13   |-1
15   |-3
...  |...

我面临着寻找“给定时间 T 的下一个元组”(<- next(T);)的问题，例如下一个 (4) -> <5,6>，或下一个 (5) -> <8,10>。此外，由于此数据保存在 MySQL 数据库中，我更愿意使用 SQL 来实现这一点。然而，时间限制需要在 O (log n) 中找到相应的元组。

乍一看，我尝试了以下 SQL 语句(我希望我的伪代码是可以理解的):

<time, value> = next(T) {

    return (select * from table
        where time = (select min(time) from table
            where time > T))
}

但是，这并没有在合理的时间内给出结果。我猜想“从表中选择 min(time) where time > find”需要 O(n) 时间。当然，我知道在有序列表中执行搜索只需要 O(log n) 时间，但我不知道如何在 SQL 中执行此操作。这可能吗？如果是这样，它是如何工作的？

谢谢!

---

供您引用:

(1) 目前我的解决方案将相应的数据缓存在内存中并对其进行初始排序。这样我就可以在 O(log n) 时间内找到下一个元组。然而，这会消耗大量内存，我更愿意在 DBMS 中以“内联”的方式进行操作，这肯定在缓存等方面进行了高度优化。

(2) 我可以想象一种解决方案，其中数据在数据库中按时间排序，但我不知道如何确保排序或在 SQL 中实现相应的搜索算法。 :-/

(3) 我知道索引等，如果我将时间声明为主键，它会提高性能，但我不知道它如何帮助在 O(log n) 中找到下一个。

Answer 1

1. 您需要确保时间列存在索引。您可以通过检查此命令的结果来检查索引是否存在:

   显示表中的索引；

   如果时间列是表的主键，那么索引几乎肯定存在。该索引对于在时间列中进行有效搜索是必需的。你将获得 O(log n) 的性能如果不是恒定时间查找，则使用正确的索引(只需阅读有关 btrees 的更多信息)。

   MySQL 使用 B 树索引，它允许在对数时间内进行查找和顺序遍历。这意味着如果 MySQL 正确使用索引，则在对数时间内为给定时间找到下一个更高的时间。情况并非总是如此，您必须尝试一下。如果它不起作用，则必须给 MySQL 执行提示以使其正确使用索引。

2. 按时间对结果进行排序，然后使用 limit 关键字只从结果集中取第一个结果:

   select * from table
       where time > T
       order by time
       limit 1