database - 允许有效搜索对象的数据结构

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}
}

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

附言这是too broad吗？如果是这样，我会很乐意将其删除

Answer 1

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

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

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

例如:

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