Я слышал, что базы данных B-Tree быстрее, чем таблицы Hash, поэтому я подумал об использовании базы данных B-Tree для моего проекта. Существует ли какая-либо существующая структура в python, которая позволяет нам использовать такую структуру данных или мне придется писать код с нуля?Есть ли база данных B-Tree или фреймворк в Python?
Единственная причина, по которой выбрать B-Tree над хэш-таблицей, либо в памяти, либо в блочном хранилище (как в базе данных), - это поддерживать запросы, отличные от равных. B-дерево позволяет выполнять запросы диапазона с хорошей производительностью. Многие хранилища с ключевыми значениями (например, berkley db) не делают это внешне видимым, хотя, поскольку они все еще содержат хэширование ключей, но это все же позволяет быстро и стабильно перебирать весь набор данных (итераторы остаются в силе, даже если есть добавление или удаляет, или дерево необходимо перебалансировать).
Если вам не нужны запросы диапазона, и вам не нужна параллельная итерация, вам не нужны b-деревья, используйте хеш-таблицу, она будет быстрее в любом масштабе.
Редактировать: У меня был случай для вышеупомянутого, чтобы на самом деле быть правдой; для этого пакет blist представляется наиболее полной реализацией сортированной библиотеки контейнеров.
Berkeley DB, конечно, позволяет вам задавать запросы с помощью курсоров. См. Http://docs.oracle.com/cd/E17076_02/html/gsg/CXX/Positioning.html – Gurgeh
Характеристика «единственная причина выбора B-дерева по хеш-таблице, либо в памяти, либо в блочном хранилище ... для поддержки запросов, отличных от равных ", неверно. В дополнение к свойствам диапазона, b-деревья обеспечивают эффективный упорядоченный обход. Это может быть очень важно. – Christopher
«упорядоченный обход» - это концепция, тесно связанная с запросами на диапазон, и поэтому я собираю их вместе в своем ответе. – SingleNegationElimination
Запрограммируйте то, что вы пытаетесь сделать первым, затем оптимизируйте, если необходимо. Период.
EDIT:
http://pypi.python.org/pypi/blist
Падение замены для питона, построенный в списке.
Технически это часть моей программы, я не хочу использовать обычную БД, такую как MySQL .. и мне сказали иметь в виду, что вставка данных будет в больших наборах – Rahul
Таким образом, постоянное время поиска/доступа, предлагаемое хэш-таблицами, недостаточно быстро для того, что вы делаете, и вы смотрите к b-деревьям, чтобы ускорить процесс? Я предлагаю прочитать о b-деревьях и хешах, прежде чем задавать вопросы о них. – user318904
хорошо, я сделал несколько основных обзоров литературы и наткнулся на это http://www.igvita.com/2009/02/13/tokyo-cabinet-beyond-key-value-store/ , что упомянутая статистика обманывала меня, чтобы пойти на B -Trees, к сожалению, не существует реализации программы на Python. – Rahul
SQLite3 использует B + Trees внутренне, но похоже, что вам может понадобиться хранилище ключей. Попробуйте Berkeley DB для этого. Если вам не нужны транзакции, попробуйте HDF5. Если вы хотите иметь распределенное хранилище ключей, то также есть http://scalien.com/keyspace/, но это система типа сервер-клиент, которая откроет всевозможные магазины ключей NoSQL.
Все эти системы должны быть O (log (n)) для вставки и извлечения, поэтому они, вероятно, будут медленнее, чем используемые хэш-таблицы.
Kyoto Cabinet предлагает хеш-дерево, так что может быть больше того, что вы ищете, поскольку оно должно быть O (1) для вставки и извлечения, но вы не можете совершать обход в порядке, если вам это нужно (хотя, поскольку в настоящее время вы используете хэш-деревья, это не должно быть проблемой).
http://fallabs.com/kyotocabinet/
Если вы ищете производительность, вам необходимо будет иметь скорость критических элементов, реализованных в скомпилированный языке, а затем иметь оболочку API в Python.
Возможно, вы захотите взглянуть на mxBeeBase, который является частью базового распределения eGenix mx. Он включает быструю реализацию B + Tree на диске и предоставляет классы хранения, которые позволяют создавать словари или базы данных на диске в Python.
Here есть хорошая реализация python btree pure. Вы можете при необходимости адаптировать его.
вы должны действительно проверить зодб. http://www.zodb.org/en/latest/
я сделал монографию о его долго идти, хотя его по-испански http://sourceforge.net/projects/banta/files/Labs/zodb/Monografia%20-%20ZODB.pdf/download
Информация на английском языке повсюду.
Это хороший повод избежать преждевременной оптимизации вашего приложения. Просто получите рабочее приложение, а затем вы посмотрите на возможности улучшить производительность, если это оправдано. Кстати, вы всегда можете попробовать поставить «python b-tree» в Google для ответа на ваш вопрос. –
Ну, у меня есть прототип моего приложения, но проблема в том, что набор данных, который мне приходится обрабатывать, буквально ближе к миллиону, обычное хеширование не может получить меня такими высокими скоростями .. так что подумал о том, чтобы отправиться в B-Trees. – Rahul
Что случилось со всеми downvotes? (i upvoted только для того, чтобы противостоять.) Если вы считаете, что этот вопрос и ответы не соответствуют действительности, прокомментируйте. –