c - 如果将所有数据都放入内存，那么执行“SELECT ...WHERE ...”的最快方法是什么？

Question

如果所有数据都放入内存，这意味着媒体速度要快得多，那么执行“SELECT .. WHERE ..”查询（过滤数据）的最快方法是什么？到目前为止，我脑海中的选项：

1) b 树状算法，但可能仍需要索引和更大的空间

2）固定长度数组，尺寸更小但可能更慢。

如果速度和大小都是问题，还有其他更好的方法吗

Answer 1

这取决于您的具体情况 - 您需要快速进行哪些操作，确切的大小是多少等等。一些例子：

1. 对于AND查询，通常维护一组排序列表（每个特征的列表）。这种数据结构称为倒排索引，搜索引擎经常使用它从给定查询中获取相关文档。（例如，Apache Lucene 使用这种数据结构）。
2. 如果可以使用数组- 并且需要对数据进行迭代 - 这是一种非常有效的方法，因为数组基本上是缓存效率最高的数据结构。在大多数情况下，从数组中顺序读取比任何其他 DS 都要快得多，因为它可以让您获得最少的“命中未命中”，这通常是迭代数据时的瓶颈。
3. 例如，如果您的数据是字符串，并且您将使用为字符串设计的数据结构（例如trie或基数树）根据某些字符串属性（例如前缀）进行过滤- 可能会为您带来最佳性能。

底线：如果你打算做一些定制的事情来提高默认库的性能，你应该在设计你选择的数据结构之前考虑具体的问题细节。