Provided by:
manpages-es_1.55-8_all 
NONMBRE
btree - método de acceso a bases de datos árbolB
SINOPSIS
#include <sys/types.h>
#include <db.h>
DESCRIPCIÓN
La rutina dbopen 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 se define en el fichero cabecera <db.h> como
sigue:
typedef struct {
u_long flags;
u_int cachesize;
int maxkeypage;
int minkeypage;
u_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 los siguientes:
flags El valor del campo de opciones se especifica mediante un O-
lógico 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 64K. 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 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.
Si el fichero ya existe (y no se ha especificado la opción O_TRUNC), se
ignoran los valores indicados para las opciones de los parámetros,
lorder y psize, en favor de los valores usados cuando se creó el árbol.
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.
ERRORES
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).
VÉASE TAMBIÉN
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.
FALLOS
Sólo se soportan los órdenes de bytes ascendente (el byte de mayor peso
el último) y descente (el bytes de menor peso el último).
18 agosto 1994 BTREE(3)