Индексация файлов (с помощью двоичных деревьев?) В Python

Question

Фон

У меня есть много (тысячи!) Файлов данных со стандартным форматом, основанным на полях (например, разделенные табуляцией, одни и те же поля в каждой строке, в каждом файле). Я обсуждаю различные способы сделать эти данные доступными для поиска. (Некоторые параметры включают RDBMS, NoSQL, использование grep / awk и друзей и т. Д.).

Предложение

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

Я понимаю, что это немного плохо, и решения приветствуются.

Дополнительные детали

• файлы длинные, не широкие
  • миллионов строк в час, более 100 файлов в час
  • табуляция разделена, не много столбцов (~ 10)
  • поля короткие (скажем, <50 символов на поле) </li>
• запросы относятся к полям, комбинациям полей и могут быть историческими

Недостатки различных решений:

(Все они основаны на моих наблюдениях и тестах, но я открыт для исправления)

BDB

• имеет проблемы с масштабированием до больших размеров файлов (по моему опыту, когда они составляют 2 ГБ или около того, производительность может быть ужасной)
• один писатель (если возможно обойти это, я хочу увидеть код!)
• сложно выполнить множественную индексацию, то есть индексацию сразу по разным полям (вы можете сделать это, копируя данные снова и снова).
• , поскольку он хранит только строки, существует шаг сериализации / десериализации

RDBMSes

Победы:

• модель с плоским столом отлично подходит для запросов, индексации

Потери:

• По моему опыту, проблема связана с индексацией. Из того, что я видел (и, пожалуйста, исправьте меня, если я ошибаюсь), проблема с rdbmses, которую я знаю (sqlite, postgres), поддерживает либо пакетную загрузку (затем индексация идет медленно в конце), либо загрузку строк за строкой (что низкий). Может быть, мне нужно больше настройки производительности.

Answer 1

Зачем изобретать велосипед?Обязательно индексируйте файлы, но используйте Whoosh или Lucene и т. Д.

Изменить: вы не указали свои требования к производительности на момент публикацииэтот ответВы не сможете индексировать «миллионы строк в час» с помощью готового программного обеспечения.

Answer 2

sqlite3 - это быстрая, небольшая часть Python (поэтому устанавливать нечего) и обеспечивает индексацию столбцов. Он записывает в файлы, поэтому вам не нужно устанавливать систему базы данных.

Answer 3

Существует ряд файловых СУБД, разработанных для того типа данных, который вы описываете. Одним из наиболее широко используемых является Berkeley DB . Это открытый исходный код, теперь принадлежащий Oracle, и поставляется в вариантах C и Java (с Python и другими языковыми обертками для версии C).

Поскольку ваши данные доступны только для чтения, существуют и другие варианты. На ум приходит CDB . Он также имеет интерфейсы Python, а также чистую переопределение Python.

Или, если вам действительно нравится реализовывать вещи самостоятельно, вы всегда можете реализовать SSTables из статьи Google Bigtable. ;)

Answer 4

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

Сценарий данных файла в базу данных, индексирование по вашему усмотрению и запрос данных любым сложным способом, поддерживаемым базой данных.

Это если вы не ищете крутой учебный проект. Тогда непременно придумайте интересную схему индексации файлов.

Answer 5

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

Чтобы сократить время ожидания ввода-вывода, лучше всего использовать сжатие.

Создайте огромный ZIP-архив со всеми вашими файлами. Один open, меньше читает. Вы потратите больше процессорного времени. Однако время ввода-вывода будет доминировать в вашей обработке, поэтому сократите время ввода-вывода, архивируя все.