ビッグデータのアーカイブ(LTO)を検索したいかも
ビッグデータの時系列データをアーカイブでとっていたときに、ある範囲のデータをとりたいと思うことはあるでしょう。ごくたまにしか使わないデータの場合は、巨大なCSV（100Gぐらいから）でそのままとっておいて、テープにいれておくことはあるでしょう。100Gぐらいになると、CSVそのまま検索するのは、ハードディスクでもややつらいことがあります。さらにテープで、１TのCSVといったらもっとつらいでしょう。そこでデータを保存するときに、別途インデックスをつくってあげて、バイナリレベルでこのアドレスからこのアドレスまでとってきてとできるなら、テープでもそこそこいけるのではないでしょうか？ このアイデアのもとは、ある特許なのですが、その特許をとった人たちには、LTO向けには作ってもしょうがないと言われのですが、いやできそうだと思って、思考実験的に書いてみました。時間があればのろいですが、python で書いてみるつもりです。可能なら、Rust の方に書いてもらえるといいなと思っています。
どでかいCSVでも、バイナリで記憶媒体の位置指定できれば、とってこれるのではないでしょうか？
それでどんなインデックスをつくって位置指定するかです。
前提条件は、時系列でデータが並んでいること。 行番号インデックスがつくれます。
行番号の位置にある一行のバイナリ始点、終点がわかっていると、5100万行目から、5110万行目までとってくることが可能ですね。行番号インデックスをつかって２個の値を拾ってくればいいです。このインデックスを 行番号インデックス と呼びましょう。
時系列が等間隔（重複がない）でかつ抜けがなく、一行の長さが固定長なら更に楽 行番号インデックスすら不要です。計算するだけですぐに取り出せます。さすがこれは条件がきつすぎるので、時系列にならんでいるだけで我慢しましょう。
実際のデータが時系列順にならんでいるかでも、実際はかなりきつい条件ではあります。でも運良く並んでいる場合があるとして考えていきます。
まず、行番号インデックスをつくります。行番号インデックスは、バイナリで見ると、行の開始位置、終了位置がならんでいるだけです。データの範囲を64bitとすると、8バイト＋8バイトのデータがならんでいるだけです。100行目をとっていくるときは、バイナリデータ上で、16バイト×100のoffset をかませばとってこれます。 ハッシュをつかったインデックスに比べると簡単ですね。固定長だと位置がインデックスになるので便利です。
位置がインデックスになっているので位置インデックスと仮に呼びましょう。固定長のデータだとバイナリ的に詰めて位置インデックスにすることが可能です。もちろん、データの位置がインデックスとして意味がある場合に限定されます。今回のように時系列でソートされていると位置をインデックスとすると便利な性質がでてきます。
値から、行番号を割り出すのはどうしたらいいか
行番号インデックス(実装は位置インデックス)をつくっておけば、何番目から何番目のデータという指定が簡単にできるなら、該当の範囲のデータは簡単にとってこれます。そこで値から行番号を割り出す仕組みが必要になります。
行番号割り出しのためにでもう一個、インデックスをつくります、ソート済み値行番号インデックスという名前にしましょう。時系列データの値を、ソートして、時系列の実際の値と、開始のソート結果の行番号の２つの値でつくったインデックスです。ここでもともとデータが時系列で、ソートされている前提なので、ソート済み行番号と行番号インデックスの行番号は同じものになります。時系列データを順番にチェックしていき、重複しない時系列データがでてきたら、その時系列の値と行番号を保存し、ソート済み値行番号インデックスをつくっていきます。アルゴリズム的には簡単です、また、当たり前ですが、このソート済み値行番号インデックスノ行数は元データの行数を超えることはないです。
２個並んでいるので、行番号インデックスに近い構造ですね。バイナリ上は、時系列データの表現に必要なバイト数＋８バイト（行番号なんで64bitで十分でしょう）の 固定長にできますので、ソート済み値行番号インデックスも位置インデックスにできます。
ソート済み値行番号インデックスで、特定の時系列の値がどのデータなのかというのは、二分探索木で特定できます。ソート済み値行番号インデックスは、何行あるかわかっているので、半分のところからはじめていきます。最初に、何回か二分探索木やっておいてもいいかもしれません。ヘッドの移動回数や距離がへるので、データサイズが大きい場合ややっておいたほうがいいですね。二分探索木なので、そこそこ速いはずです。データの行数が増えても、比例的に時間がかかるだけです。
まとめ ２個インデックス（そこそこ大きいけどしょうがない）をつくれば、時刻範囲の取り出しは、そこそこ意味ある時間ないで可能ではないでしょうか？
ソート済み値行番号インデックス で行番号特定 -> 行番号インデックスで、実データ取得になります。
疑問点（すでにみんなやっているのでは）
-
あまりに簡単な発想なので、時系列アーカイブでよく使われている実践ではないかと思われます。詳しい人教えてください。
-
等間隔の時系列（時系列の抜けや重複がない）で、１行を固定長にしてしまえば、２つのインデックスすら不要です。実践している人がたくさんいるんじゃないだろうか？
-
元データが時系列にソートされていなくても、もう１個インデックスを加えればなんとかなります。。。興味ある人いるだろうか？