我想问一些SO'ers他们对用于索引时间序列的最佳数据结构的看法（也就是列式数据，也就是扁平线性） .
基于采样/离散特征存在两种基本类型的时间序列：
-
定期离散（每个样本采用共同频率）
-
不规则的离散化（样本在任意时间点进行）
需要的查询：
-
时间范围内的所有值[t0，t1]
-
时间范围[t0，t1]中的所有值都大于/小于v0
-
时间范围[t0，t1]中值范围为[v0，v1]的所有值
数据集包括汇总的时间序列（通过不规则离散化的那种）和多变量时间序列 . 所讨论的数据集大小约为15-20TB，因此处理以分布式方式执行 - 因为上述一些查询将导致数据集大于任何一个系统上可用的物理内存量 .
此上下文中的分布式处理还意味着调度所需的数据特定计算以及时间序列查询，以便计算可以尽可能接近数据发生 - 从而减少节点到节点的通信（有点类似于map /减少范式） - 在计算和数据的短暂接近是非常关键的 .
该指数应该能够应对的另一个问题是，绝大多数数据是静态/历史性的（99.999 ...％），但是每天都会添加新数据，想到“在现场传感器”或“市场数据” . 想法/要求是能够以尽可能低的延迟更新任何正在运行的计算（平均值，garch等），其中一些运行计算需要历史数据，其中一些将超过可以合理缓存的数据 .
我已经考虑过HDF5，它适用于较小的数据集，但随着数据集变大而开始拖动，前端也没有本机并行处理功能 .
寻找建议，链接，进一步阅读等（C或C解决方案，图书馆）
3 回答
您可能想要使用某种类型的大型 balancer 树 . 像托比亚斯提到的那样，B树将成为解决第一个问题的标准选择 . 如果您还关心快速插入和更新，那么在MIT和CMU这样的地方有很多新的工作要做到这些新的"cache oblivious B-trees" . 对于这些事情的实现的一些讨论，查看Tokutek DB，他们有很多很好的演示，如下所示：
http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf
问题2和3通常要困难得多，因为它们涉及更高维度范围的搜索 . 执行此操作的标准数据结构将是range tree（以O（n log ^ d（n））存储为代价提供O（log ^ （n））查询时间 . 你通常不希望使用k-d树来做这样的事情 . 虽然kd树确实具有最佳的O（n）存储成本，但事实是如果你有10 ^ 10个数据点（谁想要等待O（10 ^ 5），你就可以切断它 . ）磁盘读取完成一个简单的范围查询？）
幸运的是，这听起来像你的情况，你真的不需要担心一般情况 . 由于您的所有数据都来自时间序列，因此每个时间坐标最多只能有一个值 . 假设，您可以做的只是使用范围查询来拉出一些点间隔，然后在后期处理过程中逐点应用v约束 . 这将是我尝试的第一件事（在获得良好的数据库实现之后），如果它有效，那么你就完成了！如果你继续遇到[t0，t1] x [-infty，infty]中的点数大于[t0中的点数的数量级]的情况下，尝试优化后两个查询真的很有意义 . t1] x [v0，v1] .
一般想法：
问题1相当常见：创建一个适合RAM的索引，并且链接到二级存储上的数据（数据结构：B-Tree family） . 问题2/3非常复杂，因为您的数据太大了 . 您可以将数据划分为时间范围并计算该时间范围的最小值/最大值 . 使用该信息，您可以过滤掉时间范围（例如，范围的最大值为50，您搜索v0> 60，然后间隔结束） . 其余的需要通过浏览数据进行搜索 . 有效性在很大程度上取决于数据的变化速度 .
您还可以通过组合较低级别的时间范围来执行多个索引，从而更快地进行过滤 .
你自己实现这个将是非常耗时和复杂的 . 我建议你使用Cassandra . Cassandra可以为您提供水平可伸缩性，冗余，并允许您将来运行复杂的map reduce函数 . 要学习如何在cassandra的商店时间系列请看看：http://www.datastax.com/dev/blog/advanced-time-series-with-cassandra和http://www.youtube.com/watch?v=OzBJrQZjge0 .