为快速查询存储范围的最佳数据结构是什么？

Question

在这种情况下，我有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，二分法搜索将导致块(1，2)和(2，2)，这些块可以包含19，然后执行完全线性搜索来查找令牌19 (这里不可能在块内进行二分搜索，因为令牌具有不同的大小，并且还没有包含在任何数据结构中)。

谢谢!

编辑：我正在考虑使用包含所有时间间隔的间隔树。问题是，查询仍然会导致多个时间间隔。此外，与二进制搜索相比，它没有进行太多的优化。

Answer 1

您可以有一个t指针数组A指向对象，这些对象包含指向令牌、其时间线和块的指针。如果您可以使用您的语言喜欢的任何机制在数组中保存引用。如果你不能在块内进行二进制搜索，我不知道你能做什么。

Answer 2

在我看来，最简单的方法(如果不占用大量内存空间)是创建一个blob值数组，其中索引是您的查询令牌(在您的示例中是19)，值是对应于它的blob部分。数组应该是好的，因为您没有空白。构造这个数组是O(n)，搜索是O(1)。但是，只有在查询量相对较大的情况下，这才会带来一些好处，因为现有的结构已经很好地优化了。(实际上应该在这里进行测试，哪种方式更快。)

构造数组：

array = []
foreach ( timeline in timelines ){
  foreach ( block in timeline){
    foreach( token in block ){
      array[token.index] = token.value
    }
  }    
}

如果成本太高，请尝试只为令牌保存时间线号。这样，当查询出现时，您将不必搜索每个时间线。您所要做的就是获取时间线，二进制搜索一个块，并在一个块内进行简单的前向搜索。

Answer 3

也许你可以用稀疏的空间填充曲线？当您有索引时，它是一个降低维度的函数。一个空间填充曲线是相同的，但它也添加了一个空间信息的索引。空间填充曲线或空间索引的另一个数据结构是四叉树。因此，您可以使用四叉树或kd树进行搜索。