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

10

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

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

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

sihirbazzz
источник

Ответы:

10

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

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

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

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

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

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

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

rapaio
источник
Большое спасибо Rapaio :) Точки, которые вы мне дали, очень полезны и дают кое-что более ясное .. Так как я - разработчик .NET и любопытный человек на простом C (я начинаю учиться) и новый, быстрый, надежный, масштабируемый ancd конечно, полностью управляемый - в краткосрочной перспективе: очень взволнованный - методы .. Так что мне нужно очень много учиться .. Чтобы учиться, я стараюсь читать очень много документов, но, как вы можете догадаться, я на старте ... Я не знал, что у BTree есть преимущества на диске (В мире .Net многие авторы объясняют это следующим образом: иерархическая структура данных, такая как Linked-List. Больше нет!) Еще раз большое спасибо
sihirbazzz
И если вы позволите мне, пока не будет более качественного объяснения / ответа, чем ваш, я хочу принять это как ответ ... И, кстати, Lucene.NET - это .NET-реализация Java Lucene
sihirbazzz