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 ツリー インデックスを使用します。これにより、ルックアップとシーケンシャル トラバースが両方とも対数時間で可能になります。つまり、MySQL がインデックスを正しく利用している場合、特定の時間の次に高い時間を見つけることは対数時間で行われます。これは常に当てはまるとは限らず、これを試す必要があります。うまくいかない場合は、MySQL 実行のヒントを与えて、インデックスを正しく利用できるようにする必要があります。

  2. 結果を時間順に並べてから、limitキーワードを使用して、結果セットから最初の結果のみを取得します。

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