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).