数据结构，允许对对象进行有效搜索

Question

我有一个非常大的对象数据库（读取键/值对数组，如标准 C 表示法中的[{}, {}, {}]），我需要能够搜索该组对中任何键的任何值并找到包含它的对象（我将使用模糊搜索或类似的字符串比较算法）。我能想到的一种方法是创建一个巨大的主对象，其中有一个键引用对象内每个值的原始对象：

DB = [
 {
   "a": 45,
   "b": "Hello World"
 },
 {
   "a": 32,
   "b": "Testing..."
 }
]
// ... Generation Code ... //
search = {
  45: {the 0th object},
  "Hello World": {the 0th object},
  32: {the 1st object},
  "Testing...": {the 1st object}
}

这种解决方案至少将问题减少到大量的比较，但是有更好的方法吗？请注意，我几乎没有接受过正式的计算机科学培训，所以我可能会错过一些简化或证明不可能解决这个问题的主要细节。

附言这是不是太宽泛了？如果是这样，我很乐意删除它

Answer 1

组合索引更适合全文搜索，但不指示在对象的哪个属性中找到该值。提供更多上下文的替代方法是为每个属性构建一个索引。

在准备和查找特定属性的搜索者时，这应该更快（例如 a == 32 ），因为对于 n 个对象和 p 属性，二叉搜索（用于插入和查找）将需要对组合索引进行 log（np） 比较，对单属性索引进行 log（n） 比较。

无论哪种情况，您都需要注意同一值的多次出现。您可以将偏移量数组存储为每个索引条目的值，而不仅仅是单个值。

例如：

search = {
  "a": {
    45: [0],
    32: [1]
  },
  "b": {
    "Hello World": [0],
    "Testing...": [1]
  }
}