0

我有一个带有元组的表，其中时间戳（时间）不是连续的，但（为了简单起见，我们可以假设）是唯一的。

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

我面临着寻找“给定时间 T 的下一个元组”（<- next(T);) 的问题，例如 next(4) -> <5,6> 或 next(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))
}

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

谢谢！

供你参考：

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

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

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

4

1 回答 1

3

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

    show index from table;

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

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

  2. 按时间排序结果，然后使用limit关键字从结果集中仅获取第一个结果：

    select * from table
    where time > T
    order by time
    limit 1
于 2013-09-08T11:54:36.833 回答