Как реализовать B + Tree для файловых систем?

Question

У меня есть текстовый файл, который содержит некоторую информацию об экстентах всех файлов в файловой системе, как показано ниже C: \ Program Files \ abcd.txt 12345 100 23456 200 C: \ Program Files \ bcde.txt 56789 50 26746 300 ...

Теперь у меня есть еще один бинарный файл, который пытается узнать об экстентах для всех файлов. Сейчас в настоящее время я использую линейный поиск, чтобы найти информацию об экстентах для файлов в вышеупомянутом текстовом файле. Это трудоемкий процесс. Есть ли лучший способ кодирования этого? Как реализация любой хорошей структуры данных, такой как BTree. Если используется B + Tree, какой ключ, фактор ветвления мне нужно использовать?

Answer 1

Использовать базу данных.

Ключевыми моментами при реализации дерева в файле являются фиксированная длина записи и использование смещений файлов вместо указателей.

Использовать базу данных. Хммм, SQL Lite.

Еще один момент, который следует учитывать при работе с файлами, заключается в том, что чтение по частям данных происходит быстрее, чем чтение отдельных элементов (независимо от того, есть ли на жестком диске кэш или ОС имеет кэш). Я реализовал дерево B +, которое использует страницы в качестве узлов.

Использовать базу данных . Базы данных уже написаны и проверены .

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

Использовать базу данных.

Я бросил писать реализацию B-Tree для своего приложения, потому что хотел сконцентрироваться на других функциях программы. Позже я узнал, что в реальном мире (мире, где программы должны быть завершены в соответствии с графиком), это время должно быть потрачено на «ядро» приложения, а не на аксессуары, которые уже были написаны и протестированы (то есть вне полки).

Answer 2

Это зависит от того, как вы хотите найти свой файл. Я предполагаю, что вы хотите посмотреть ваши данные по имени файла. Тогда хеш-таблица или Trie будет хорошей структурой данных для использования.

B-дерево возможно, но не самый удобный выбор, если ваши ключи являются строками.