Лучший способ создать основанное на диске B-дерево из данного файла?

Question

Знаете ли вы быстрый алгоритм для создания B-дерева из существующего (несортированного) файла, содержащего целые числа через пробел. Как правило, размер файла будет на несколько порядков больше доступной оперативной памяти.

Вы можете предположить, что B-дерево впоследствии не будет изменено, то есть оно будет использоваться только для индексации информации в файле (скажем, файл содержит строки, разделенные запятыми). Кроме того, является ли B-дерево наилучшей идеей для индекса, можете ли вы предложить другие структуры?

Answer 1

Это зависит от того, как вы хотите получить доступ к вашим данным.Если вы используете хеш-таблицу, вы можете получить доступ к элементам только по их первичному ключу в O (1), который быстрее, чем с деревом (log (n))

Вы не можете выбирать диапазоны (все, что находится между10 и 20), что поддерживается древовидными алгоритмами в Log (n), где в качестве хеш-индекса может быть получено полное сканирование O (n).также постоянные издержки хеш-индексов обычно больше (что не является фактором в тэта-нотации, но все еще существует), тогда как древовидные алгоритмы обычно проще поддерживать, расширять с помощью данных, масштабировать и т. д.таблица, если вам не нужен порядок, и двоичное дерево (сбалансированное) в противном случае.