Структура данных, которая позволяет эффективно искать объекты

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

Это решение, по крайней мере уменьшает проблему большого числа сравнений, но есть ли лучшие подходы? Обратите внимание, что у меня очень мало формальной подготовки в области компьютерных наук, поэтому я могу пропустить некоторые важные детали, упрощающие или доказывающие невозможность этой проблемы.

P.S. Это too broad? Если это так, я с удовольствием удалю его

Answer 1

Ваш комбинированный индекс больше подходит для полнотекстового поиска, но не указывает, в каком свойстве объекта находится это значение. Альтернативный метод, который предоставляет больше контекста, заключается в создании индекса для каждого свойства.

Это должно быть быстрее как при подготовке, так и при поиске поисковых запросов (например, a == 32), поскольку для n объектов и свойств p двоичный поиск (используемый как в вставках, так и в поиске) потребует сопоставления log (np) на объединенный индекс и log (n) в индексе единственной собственности.

В любом случае вам нужно следить за несколькими вхождениями того же значения. Вы можете хранить массив смещений как значение каждой записи индекса, а не только одно значение.

Например:

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