Есть ли в Python база данных или фреймворк B-Tree?

Question

Я слышал, что базы данных B-Tree быстрее, чем хэш-таблицы, поэтому я подумал об использовании базы данных B-Tree для своего проекта.Существуют ли какие-либо фреймворки в python, которые позволяют нам использовать такую ​​структуру данных, или мне придется кодировать с нуля?

Answer 1

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

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

Редактировать: У меня был повод, чтобы сказанное выше действительно было правдой; для этого пакет blist представляется наиболее полной реализацией отсортированной библиотеки контейнеров.

Answer 2

вы действительно должны проверить Zodb. http://www.zodb.org/en/latest/

я сделал монографию об этом долго, хотя на испанском http://sourceforge.net/projects/banta/files/Labs/zodb/Monografia%20-%20ZODB.pdf/download

Информация на английском повсюду.

Answer 3

Сначала запрограммируйте то, что вы пытаетесь сделать, а затем оптимизируйте, если это необходимо. Период.

EDIT:

http://pypi.python.org/pypi/blist

Падение в замен для встроенного списка Python.

Answer 4

Возможно, вы захотите взглянуть на mxBeeBase , которая является частью eGenix mx Base Distribution. Он включает в себя быструю реализацию B + Tree на диске и предоставляет классы хранения, которые позволяют создавать словари или базы данных на диске в Python.

Answer 5

SQLite3 использует деревья B + для внутреннего использования, но, похоже, вам может понадобиться хранилище значений ключей.Попробуйте Беркли DB для этого.Если вам не нужны транзакции, попробуйте HDF5.Если вы хотите распределенное хранилище значений ключей, есть также http://scalien.com/keyspace/,, но это система типа сервер-клиент, которая открыла бы все виды хранилищ значений ключей NoSQL.

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

Kyoto Cabinet предлагает хеш-дерево, так что может быть большетого, на что вы смотрите, так как для вставки и извлечения это должно быть O (1), но вы не можете выполнять обход в порядке, если вам это нужно (хотя, поскольку вы в настоящее время используете хеш-деревья, это не должно бытьпроблема).

http://fallabs.com/kyotocabinet/

Если вы ищете производительность, вам нужно будет реализовать критичные по скорости элементы в скомпилированном языке, а затем иметь API-оболочку в Python.

Answer 6

Здесь есть хорошая реализация на чистом Python. Вы можете адаптировать его при необходимости.