cdb , abreviatura de "base de datos constante", se refiere tanto a una biblioteca como a un formato de datos creado por Daniel J. Bernstein . cdb actúa como una matriz asociativa en el disco , asigna claves a valores y permite almacenar varios valores para una sola clave. Una base de datos constante permite solo dos operaciones: creación y lectura. Ambas operaciones están diseñadas para ser muy rápidas y altamente confiables. Dado que la base de datos no cambia mientras está en uso, varios procesos pueden acceder a una sola base de datos sin bloquearse. Además, dado que todas las modificaciones crean una base de datos de reemplazo, puede aprovechar la semántica del sistema de archivos UNIX para proporcionar una garantía de confiabilidad.
Las posiciones de registro, las longitudes de clave y valor y los valores hash son cantidades de 32 bits y, por lo tanto, deben caber en 4 gigabytes. [1] CDB es utilizado por djbdns , fastforward , mess822 , qmail y ucspi-tcp para proporcionar acceso de datos altamente eficiente, fiable y simple.
Estructura
Una base de datos contiene un conjunto de datos completo (por ejemplo, una sola matriz asociativa) en un solo archivo de computadora . Consta de tres partes: un encabezado de tamaño fijo, datos y un conjunto de tablas hash . Las búsquedas están diseñadas solo para claves exactas, aunque se pueden realizar otros tipos de búsquedas escaneando toda la base de datos. Las búsquedas se realizan utilizando el siguiente algoritmo :
- Hash la clave.
- Determine en qué tabla hash y ranura debe ubicarse este registro .
- Pruebe la ranura indicada en la tabla hash.
- Si la ranura está vacía, el registro no existe. Abortar la búsqueda.
- Si el hash de la ranura coincide con el hash de la clave, busque el registro. Lea y compare la clave. Si coincide, se han encontrado los datos, así que finalice la búsqueda.
- El registro no está en este espacio. Continúe con la siguiente ranura, envolviendo hasta el comienzo de la tabla hash si es necesario.
Para búsquedas de claves con múltiples valores, se pueden encontrar valores adicionales simplemente reanudando la búsqueda en el siguiente espacio.
Formato
Todos los números (compensaciones, longitudes y valores hash) son enteros de 32 bits sin signo , almacenados en formato little endian . Las claves y los datos se consideran cadenas de bytes opacas y no tienen un tratamiento especial.
El encabezado de tamaño fijo al comienzo de la base de datos describe 256 tablas hash enumerando su posición dentro del archivo y su longitud en las ranuras. Los datos se almacenan como una serie de registros, cada uno de los cuales almacena la longitud de la clave, la longitud de los datos, la clave y los datos. No hay reglas de alineación o clasificación. Los registros van seguidos de un conjunto de 256 tablas hash de diferentes longitudes. Dado que cero es una longitud válida, puede haber menos de 256 tablas hash almacenadas físicamente en la base de datos, pero no obstante, se considera que hay 256 tablas. Las tablas hash contienen una serie de ranuras, cada una de las cuales contiene un valor hash y un desplazamiento de registro. Las "ranuras vacías" tienen un desplazamiento de cero.
Los hash son enteros de 32 bits sin signo y comienzan con un valor de 5381. Para cada byte de la clave, el hash actual se multiplica por 33, luego XOR 'ed con el byte actual de la clave. Los bits de desbordamiento se descartan. Las ranuras y las tablas se calculan trivialmente a partir de hashes. La tabla de destino es simplemente los ocho bits más bajos del hash (es decir, hash módulo 256), y la ranura dentro de la tabla son los bits restantes del hash módulo la longitud de la tabla (es decir, hash dividido por 256 módulo de longitud de la tabla).
Biblioteca
El código oficial de la biblioteca cdb es de dominio público : los archivos fuente individuales están marcados como tales y también están disponibles en el paquete djbdns de dominio público . Sin embargo, el resto del paquete cdb solía ser software sin licencia , lo que significa que debe distribuirse literalmente. La licencia inusual y la simplicidad del formato han llevado a otros a volver a implementar la biblioteca y publicarla en términos más comunes, como la biblioteca TinyCDB de Michael Tokarev, disponible bajo el dominio público. [2]
En 2009, toda la cdb pasó a ser de dominio público. [3]
En particular, el creador de cdb no tiene la intención de que cdb se utilice como una biblioteca compartida . Esto difiere de casi todas similares dBm -como bases de datos, tales como Berkeley DB .
Referencias
- ^ Especificación de CDB
- ^ "TinyCDB - una base de datos constante" . www.corpit.ru . Consultado el 12 de diciembre de 2016 .
- ^ "Preguntas frecuentes de distribuidores" .
enlaces externos
- cdb sitio web oficial de cdb
- Descripción detallada del formato interno de Constant Database (cdb)
- Benchmark QDBM que compara cdb con paquetes similares