Search next (bigger) key with SQL efficiently

Search next (bigger) key with SQL efficiently

I have a table with tuples where timestamps (time) are not consecutive but
(we can assume for simplicity) unique.
time | value
------------
0 |4
3 |2
5 |6
8 |10
9 |5
13 |-1
15 |-3
... |...
I am faced with the problem of finding the "next tuple given some time T"
( <- next(T);), e.g. next(4) -> <5,6>, or next(5) -> <8,10>. Further,
since this data is hold in a MySQL database I would prefer to realize this
with SQL. However, time constraints require to find the respective tuple
in O (log n).
At first glance, I tried the following SQL statement (I hope my
Pseudo-code is understandable):
<time, value> = next(T) {
return (select * from table
where time = (select min(time) from table
where time > T))
}
However, this does not give the result in meaningful time. I guess that
"select min(time) from table where time > find" takes O(n) time. Of
course, I know performing a search in an ordered list takes only O(log n)
time but I have no clue how to do that in SQL. Is this even possible? If
so, how does it work?
Thanks!



For your information:
(1) At the moment my solution caches the respective data in memory and
orders it initially. This way I can then find the next tuple in O(log n)
time. However, this consumes lots of memory and I would prefer to do it
kind of "in-line" in the DBMS which is surely highly optimized regarding
caching etc.
(2) I could imagine a solution where data is hold ordered by time in the
database, but I don't know how to ensure ordering or to implement a
respective search algorithm in SQL. :-/
(3) I am aware of indexing etc. and that it improves performance if I
declare time as primary key but I don't know how it could help to find
next in O(log n).