python - b tree c++
¿Hay una base de datos B-Tree o un marco en Python? (6)
Escuché que las bases de datos B-Tree son más rápidas que las tablas Hash, así que pensé en usar una base de datos B-Tree para mi proyecto. ¿Existe algún framework en Python que nos permita usar dicha estructura de datos o tendré que codificar desde cero?
Es posible que desee echar un vistazo a mxBeeBase que forma parte de la distribución base de eGenix mx. Incluye una implementación rápida de B + Tree en el disco y proporciona clases de almacenamiento que permiten construir diccionarios o bases de datos en el disco en Python.
La única razón para elegir un árbol B sobre una tabla hash, ya sea en la memoria o con el almacenamiento de bloques (como en una base de datos) es para admitir consultas que no sean iguales. Un b-tree le permite realizar consultas de rango con un buen rendimiento. Sin embargo, muchas tiendas de valor-clave (como berkley db) no hacen que esto sea visible externamente, porque aún contienen las claves, pero esto aún le permite recorrer de forma rápida y estable todo el conjunto de datos (los iteradores siguen siendo válidos incluso si hay agregados o elimina, o el árbol debe ser rebalanceado).
Si no necesita consultas de rango y no necesita iteración concurrente, entonces no necesita b-trees, use una tabla hash, será más rápida en cualquier escala.
Edit: He tenido ocasión para que lo anterior sea verdad; para esto, el paquete blist parece ser la implementación más completa de una biblioteca de contenedores ordenados.
Programe lo que está tratando de hacer primero, luego optimice si es necesario. Período.
EDITAR:
Descenso en reemplazo de la lista incorporada de python.
Realmente deberías echarle un vistazo a zodb. http://www.zodb.org/en/latest/
Hice una monografía sobre el tema desde hace tiempo, aunque está en español http://sourceforge.net/projects/banta/files/Labs/zodb/Monografia%20-%20ZODB.pdf/download
La información en inglés está por todo el lugar.
SQLite3 usa B + Trees internamente, pero suena como si quisieras una tienda de valor-clave. Prueba Berkeley DB para eso. Si no necesita transacciones, intente HDF5. Si desea un almacén de valor-clave distribuido, también hay http://scalien.com/keyspace/ , pero ese es un sistema de tipo servidor-cliente que abriría todo tipo de almacenes de valor-clave NoSQL.
Todos estos sistemas serán O (log (n)) para la inserción y recuperación, por lo que probablemente serán más lentos que las tablas hash que está utilizando actualmente.
El Gabinete de Kyoto ofrece un árbol hash, por lo que puede ser más de lo que está viendo ya que debería ser O (1) para la inserción y recuperación, pero no puede hacer un recorrido en orden si lo necesita (aunque ya que Actualmente estamos utilizando árboles hash, esto no debería ser un problema).
http://fallabs.com/kyotocabinet/
Si busca rendimiento, deberá tener implementados los elementos críticos de velocidad en un lenguaje compilado y luego tener una API de envoltura en Python.
Here hay una buena implementación de btree python puro. Se puede adaptar si es necesario.