最快的过滤数据结构 schema-less collections

Question

假设我有一个 collection

var data = [
  { fieldA: 5 },
  { fieldA: 142, fieldB: 'string' },
  { fieldA: 1324, fieldC: 'string' },
  { fieldB: 'string', fieldD: 111, fieldZ: 'somestring' },
  ...
];

假设字段在元素之间不统一，但我事先知道唯一字段的数量，并且 collection 不是动态的。

我想用 _.findWhere 之类的东西过滤它。这很简单，但是如果我想优先考虑速度而不是方便怎么办？有没有更好的数据结构总是能最大限度地减少要检查的元素的数量？也许是某种树？

Answer 1

是的，如果您的查询属于 "give me all records with fieldX=valueY" 类型，则速度会更快。但是，它确实有开销。

对于每个字段，构建一个倒排索引，列出具有每个值的所有记录 ID（= 原始 data 中的行位置）：

var indexForEachField = {
    fieldA: { "5": [0], "142": [1], "1324": [2]},
    ...
}

当有人要求 "records where fieldX=valueY" 时，你 return

indexForEachField["fieldX"]["valueY"]; // an array with all results

因此查找时间是恒定的（并且只需要在表中查找 2 次），但您确实需要使索引保持最新。

这是搜索引擎使用特定术语查找网页的策略的概括；在那种情况下，它被称为 inverted index.

编辑：如果你想找到 fieldX=valueX and fieldY=valueY 的所有记录怎么办？

您将使用以下代码，它需要所有输入数组待排序：

var a = indexForEachField["fieldX"]["valueX"];
var b = indexForEachField["fieldY"]["valueY"];
var c = []; // result array: all elements in a AND in b
for (var i=0, j=0; i<a.length && j<b.length; /**/) {
    if (a[i] < b[j]) {
       i++;
    } else if (a[i] > b[j]) {
       j++;
    } else {
       c.push(a[i]);
       i++; j++;
    }
}

可以看到，在最坏的情况下，总复杂度正好是a.length + b.length；而且，在最好的情况下，只有一半。您可以使用非常相似的东西来实现 OR。

最快的过滤数据结构 schema-less collections

Fastest datastructure for filtering schema-less collections

javascript

algorithm

collections

data-structures