btree - método de acceso a bases de datos árbolB
Biblioteca Estándar C (libc, -lc)
#include <sys/types.h> #include <db.h>
Note well: This page documents interfaces provided up until
glibc 2.1. Since glibc 2.2, glibc no longer provides these interfaces.
Probably, you are looking for the APIs provided by the libdb library
instead.
La rutina dbopen(3) es la interfaz de biblioteca para los
ficheros de bases de datos. Uno de los formatos de fichero soportado es el
de los ficheros árbolB. La descripción general de los
métodos de acceso a las bases de datos se encuentra en
dbopen(3), esta página de manual describe únicamente
información especifíca de árbolB.
La estructura de datos árbolB es una estructura de
árbol balanceado y ordenado que almacena pares clave/datos
asociados.
La estructura de datos específica del método de
acceso a árbolB proporcionada por dbopen(3) se define en el
fichero cabecera <db.h> como sigue:
typedef struct {
unsigned long flags;
unsigned int cachesize;
int maxkeypage;
int minkeypage;
unsigned int psize;
int (*compare)(const DBT *key1, const DBT *key2);
size_t (*prefix)(const DBT *key1, const DBT *key2);
int lorder;
} BTREEINFO;
Los elementos de esta estructura son de la siguiente manera:
- flags
- El valor de las opciones se especifica mediante una operación
O-lógica de cualquiera de los siguientes valores:
- R_DUP
- Permite claves duplicadas en el árbol, es decir, permite la
inserción si la clave a ser insertada ya existen en el
árbol. El comportamiento por defecto, como se describe en
dbopen(3), es sobrescribir una clave coincidente cuando se inserta
una nueva clave o fallar si se especifica la opción
R_NOOVERWRITE. La opción R_NOOVERWRITE predomina
sobre la opción R_DUP y si se especifica la opción
R_NOOVERWRITE, los intentos de insertar claves duplicadas en el
árbol fracasarán.
- Si la base de datos contiene claves duplicadas, el orden de
recuperación de los pares clave/datos es indefinido si se usa la
rutina get sin embargo, las llamadas a la rutina seq con la
opción R_CURSOR activa siempre devolverá el primero
"lógico" de cualquier grupo de claves duplicadas.
- cachesize
- Un tamaño máximo sugerido (en bytes) de la memoria
caché. Este valor es sólo consultivo y el
método de acceso reservará más memoria antes que
fallar. Ya que toda búsqueda examina la página raíz
del árbol, ocultar en caché las páginas más
recientemente usadas mejorará sustancialmente el tiempo de acceso.
Además, las escrituras físicas se demorarán tanto
como sea posible, por lo que una caché moderada puede reducir el
número de operaciones de E/S de forma significativa. Obviamente,
usar una caché incrementa (pero sólo incrementa) la
probabilidad de corrupción o de pérdida de datos si el
sistema cae mientras se está modificando un árbol. Si
cachesize es 0 (no se especifica un tamaño) se utiliza un
tamaño de caché por defecto.
- maxkeypage
- El número máximo de claves que se almacenarán en una
única página. No implementado actualmente.
- minkeypage
- El número mínimo de claves que se almacenarán en una
única página. Este valor se usa para determinar qué
claves se almacenarán en páginas de overflow, es decir, si
una clave o elementos de datos es mayor que el tamaño de
página dividido por el valor de minkeypage, se almacenará en
páginas de overflow en lugar de en la propia página. Si
minkeypage es 0 (no se especifica un número mínimo de
claves) se usa un valor de 2.
- psize
- Es el tamaño (en bytes) de las páginas usadas por los nodos
del árbol. El tamaño mínimo de página es 512
bytes y el tamaño máximo de página es 64 KiB.
Si psize es 0 (no se especifica un tamaño de página)
se selecciona un tamaño de página basado en el tamaño
de bloque de E/S del sistema de ficheros subyacente.
- compare
- Es la función de comparación de claves. Debe devolver un
entero menor, igual o mayor que cero si se considera que el argumento de
la primera clave es, respectivamente, menor, igual o mayor que el
argumento de la segunda clave. Se debe usar la misma función de
comparación para un árbol dado cada vez que se abre. Si
compare es NULL (no se especifica un función de
comparación), las claves se comparan léxicamente,
considerando las claves más cortas menores que las claves
más largas.
- prefix
- Es la función de comparación de prefijos. Si se especifica,
esta rutina debe devolver el número de bytes del argumento de la
segunda clave que se necesitan para determinar que es mayor que el
argumento de la primera clave. Si las claves son iguales, se
debería devolver la longitud de la clave. Dese cuenta que la
utilidad de esta rutina es muy dependiente de los datos pero, en algunos
conjuntos de datos, puede producir unos tamaños de árbol y
tiempos de búsqueda reducidos de forma significativa. Si
prefix es NULL (no se especifica una función de prefijo)
y no se especifca una función de comparación, se usa
por defecto una rutina de comparación léxica. Si
prefix es NULL y se especifica una función de
comparación, no se hace comparación de prefijos.
- lorder
- El orden de los bytes para los enteros de los metadatos almacenados en la
base de datos. El número debería representar el orden como
un entero; por ejemplo, el orden `el byte de mayor peso el último'
(orden ascendente) sería el número 4321. Si lorder es
0 (no se especifica un orden) se utiliza el orden del anfitrión
actual.
If the file already exists (and the O_TRUNC flag is not
specified), the values specified for the arguments flags,
lorder, and psize are ignored in favor of the values used when
the tree was created.
Los recorridos secuenciales hacia adelante de un árbol van
desde la clave más pequeña a la más grande.
El espacio liberado al borrar los pares clave/datos del
árbol nunca se recupera, aunque normalmente se pone a
disposición para su reutilización. Esto significa que la
estructura de almacenamiento árbolB es de sólo crecimiento.
Las únicas soluciones son evitar excesivas eliminaciones o crear
periódicamente un árbol nuevo recorriendo el que ya
existe.
Todas las búsquedas, insercciones y eliminaciones de un
árbolB se terminarán en un orden O(logaritmo en base N) donde
`base' es el factor medio de relleno. Con frecuencia, la inserción de
datos ordenados en un árbolB produce un factor de relleno bajo. Esta
implementación se ha modificado para hacer las inserciones ordenadas
el caso mejor, produciendo un factor de relleno de páginas mucho
mejor de lo normal.
Las rutinas del método de acceso árbolB
pueden fracasar y asignar a errno cualquiera de los errores
especificados en la rutina de biblioteca dbopen(3).
Sólo se soportan los órdenes de bytes ascedente (el
byte de mayor peso el último) y descendente (el byte de menor peso el
último).
dbopen(3), hash(3), mpool(3),
recno(3)
The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv. 11,
2 (June 1979), 121-138.
Prefix B-trees, Bayer and Unterauer, ACM Transactions on
Database Systems, Vol. 2, 1 (March 1977), 11-26.
The Art of Computer Programming Vol. 3: Sorting and
Searching, D.E. Knuth, 1968, pp 471-480.
La traducción al español de esta página del
manual fue creada por Juan Piernas <piernas@ditec.um.es>
Esta traducción es documentación libre; lea la
GNU General
Public License Version 3 o posterior con respecto a las condiciones de
copyright. No existe NINGUNA RESPONSABILIDAD.
Si encuentra algún error en la traducción de esta
página del manual, envíe un correo electrónico a
debian-l10n-spanish@lists.debian.org.