それぞれブロックを含むN 個のタイムラインがあるという状況があります。ブロックには特定のインデックスを持つトークンが含まれており、最大および最小のトークン インデックスを認識しています。ブロックの最初のインデックスを (タイムライン、ブロック) ペアにマッピングするインデックスもあります。次に例を示します。
Timeline 1: [1 2 5 8 9 11] [14 17 18 21] [22 23 25 26] ...
Timeline 2: [3 4 6 7 10 12] [13 15 16 19 20 24] [27 28 34 45] ...
Index:
1 -> timeline 1, block 1
3 -> timeline 2, block 1
13 -> timeline 2, block 2
14 -> timeline 1, block 2
22 -> timeline 1, block 3
27 -> timeline 2, block 3
ご覧のとおり、トークンの欠落はありません (ギャップはありません)。
これらのデータ構造は、私が最初に持っているものです。特定のトークン インデックスのクエリを最適化するための最良の代替データ構造は何でしょうか? トークン 19 を取得したいとします。ここで行う必要があるのは、インデックス内で二分検索を行って各タイムラインの適切なブロックを見つけ、次に各ブロック内で完全検索を行うことです。トークン 19 を使用すると、二分検索の結果、19 を含むブロック (1, 2) と (2, 2) が得られ、完全な線形検索を実行してトークン 19 を見つけます (ブロック内の二分検索は、トークンがさまざまなサイズであり、まだどのデータ構造にも含まれていません)。
ありがとうございました!
編集:すべてのタイムラインの間隔を含む間隔ツリーを使用することを考えています。問題は、クエリが依然として多くの間隔になることです。さらに、バイナリ検索に比べてあまり最適化されません。