Какой метод индексирования данных наиболее эффективен?

Как все мы знаем, существуют некоторые методы индексации данных, использующиеся известными приложениями индексирования, такими как Lucene (для java) или Lucene.NET (для .NET), MurMurHash, B + Tree и т. Д. Для No-Sql / Object Ориентированная база данных (которую я пытаюсь написать / немного поиграть с C #), какую технику вы предлагаете?

Я читал о MurMurhash-2 и особенно v3 комментарии говорят, что Murmur очень быстрый. Также Lucene.Net имеет хорошие комментарии по этому поводу. Но как насчет их следов памяти вообще? Есть ли какое-нибудь эффективное решение, которое использует меньше места (и, конечно, если предпочтительнее, чем быстрее), чем Lucene или Murmur? Или я должен написать специальную структуру индекса, чтобы получить лучшие результаты?

Если я попытаюсь написать свою собственную, то есть ли приемлемая шкала для хорошей индексации, например, 1% от узла данных или 5% от узла данных? Любая полезная подсказка будет оценена.

Я думаю, что вы перепутали некоторые вещи в своем вопросе. Lucene (я ничего не знаю о Lucene, NET, но полагаю, то же самое) - это библиотека, используемая для анализа, разделения токенов и хранения документов, чтобы иметь возможность запрашивать и получать их позже. У Lucene довольно старая, но эффективная модель, она использует перевернутые деревья для поиска и извлечения документов. Без дополнительных подробностей все документы разбиваются на токены (термины), и для каждого термина поддерживается структура данных, в которой хранятся все документы, содержащие данный термин. В качестве структуры данных можно использовать BTree, хеш-таблицу и в последних основных версиях вы даже можете подключить свои собственные структуры данных.

BTree (подробнее см. На странице Википедии ) - это своего рода древовидная структура данных, которая подходит для работы с большими кусками данных и часто используется для хранения древовидных упорядоченных структур на диске. В памяти другие деревья работают лучше.

Murmur hash (подробнее см. На странице Википедии ), это семейство хэш-функций, используемых в хэш-таблице. Реализация хеш-таблицы не важна, это может быть стандартная цепная реализация или более продвинутая схема адресации с открытым хешем. Идея состоит в том, что хеш-таблицы позволяют быстро получить ключ из неупорядоченного набора ключей и могут отвечать на такие задачи, как: является ли эта ключевая часть этого набора ключей? какое значение связано с этим ключом?

Теперь вернемся к вашей главной проблеме. У вас есть одна библиотека (Lucene) и для структур данных, обе структуры данных используются в Lucene. Теперь вы видите, что невозможно ответить на ваш вопрос в этих терминах, поскольку они несопоставимы.

Тем не менее, касательно вашего следа и производительности часть вопроса. Прежде всего вы должны знать, какие операции вам нужно выполнить.

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

Много ли у вас данных, которые не умещаются в памяти? Если да, то решение на основе диска может помочь (например, BTree). Если ваши данные умещаются в памяти, тогда используйте самое быстрое решение в памяти и используйте диск только как хранилище (с другой структурой, намного проще).