我有一个带有元组的表,其中时间戳(时间)不是连续的,但(为了简单起见,我们可以假设)是唯一的。
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中进行"内联"操作,DBMS肯定在缓存等方面进行了高度优化。
(2)我可以想象一个解决方案,其中数据在数据库中按时间排序,但我不知道如何确保排序或在SQL中实现相应的搜索算法。
(3) 我知道索引等,如果我将时间声明为主键,它会提高性能,但我不知道它如何帮助在 O(log n) 中找到下一个。
-
您需要确保时间列存在索引。您可以通过检查此命令的结果来检查索引是否存在:
show index from table;
如果时间列是表的主键,则索引几乎肯定存在。索引对于在时间列中进行有效搜索是必需的。您将通过正确的索引获得 O(log n) 性能
按时间对结果进行排序,然后使用
limit
关键字仅从结果集中获取第一个结果:select * from table where time > T order by time limit 1
MySQL使用B树索引,它允许查找和顺序遍历,都是在对数时间内。这意味着在给定时间内查找下一个更高的时间是以对数时间完成的,前提是MySQL正确利用了索引。情况并非总是如此,您必须尝试一下。如果它不起作用,您必须为 MySQL 执行提示以使其正确使用索引。