BTREE

NOMBRE

SINOPSIS

#include <sys/types.h>#include <db.h>

DESCRIPCIÓN

La estructura de datos árbolB es una estructura de árbol balanceado yordenado que almacena pares clave/datos asociados.

La estructura de datos específica del método de acceso a árbolB proporcionadapordbopense 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;

Los elementos de esta estructura son los siguientes:

flags

El valor del campo de opciones se especifica mediante unO-lógicode cualquiera de los siguientes valores:

R_DUP

Permite claves duplicadas en el árbol, es decir, permite la inserción si laclave a ser insertada ya existen en el árbol.El comportamiento por defecto, como se describe endbopen(3),es sobrescribir una clave coincidente cuando se inserta una nueva clave ofallar si se especifica la opción R_NOOVERWRITE.La opción R_NOOVERWRITE predomina sobre la opción R_DUP y si se especifica laopción R_NOOVERWRITE, los intentos de insertar claves duplicadas en el árbolfracasarán.

Si la base de datos contiene claves duplicadas, el orden de recuperación delos pares clave/datos es indefinido si se usa la rutinagetsin embargo, las llamadas a la rutinaseqcon la opción R_CURSOR activa siempre devolverá el primero ``lógico'' decualquier grupo de claves duplicadas.

cachesize

Un tamaño máximo sugerido (en bytes) de la memoria caché.Este valor essóloconsultivo 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é laspáginas más recientemente usadas mejorará sustancialmente el tiempo deacceso.Además, las escrituras físicas se demorarán tanto como sea posible, por loque una caché moderada puede reducir el número de operaciones de E/S deforma significativa.Obviamente, usar una caché incrementa (pero sólo incrementa) la probabilidadde corrupción o de pérdida de datos si el sistema cae mientras se estámodificando un árbol.Sicachesizees 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. Noimplementado actualmente.

minkeypage

El número mínimo de claves que se almacenarán en una única página. Estevalor se usa para determinar qué claves se almacenarán en páginas deoverflow, es decir, si una clave o elementos de datos es mayor que el tamañode página dividido por el valor de minkeypage, se almacenará en páginas deoverflow en lugar de en la propia página.Siminkeypagees 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. Eltamaño mínimo de página es 512 bytes y el tamaño máximo de página es 64K.Sipsizees 0 (no se especifica un tamaño de página) se selecciona un tamaño depágina basado en el tamaño de bloque de E/S del sistema de ficherossubyacente.

compare

Es la función de comparación de claves.Debe devolver un entero menor, igual o mayor que cero si se considera que elargumento de la primera clave es, respectivamente, menor, igual o mayor queel argumento de la segunda clave.Se debe usar la misma función de comparación para un árbol dado cada vez quese abre.Sicomparees NULL (no se especifica un función de comparación), las claves se comparanléxicamente, considerando las claves más cortas menores que las claves máslargas.

prefix

Es la función de comparación de prefijos.Si se especifica, esta rutina debe devolver el número de bytes del argumentode la segunda clave que se necesitan para determinar que es mayor que elargumento 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 datospero, en algunos conjuntos de datos, puede producir unos tamaños de árbol ytiempos de búsqueda reducidos de forma significativa.Siprefixes NULL (no se especifica una función de prefijo)yno se especifca una función de comparación, se usa por defecto una rutina decomparación léxica.Siprefixes NULL y se especifica una función de comparación, no se hace comparaciónde prefijos.

lorder

El orden de bytes para los enteros de los metadatos almacenados en la basede datos. El número debería representar el orden como un entero; porejemplo, el orden `el byte de mayor peso el último' (orden ascendente)sería el número 4321.Silorderes 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), seignoran los valores indicados para las opciones de los parámetros, lorder ypsize, en favor de los valores usados cuando se creó el árbol.

Los recorridos secuenciales hacia adelante de un árbol van desde la clavemás pequeña a la más grande.

El espacio liberado al borrar los pares clave/datos del árbol nunca serecupera, aunque normalmente se pone a disposición para su reutilización.Esto significa que la estructura de almacenamiento árbolB es de sólocrecimiento.Las únicas soluciones son evitar excesivas eliminaciones o crearperiódicamente un árbol nuevo recorriendo el que ya existe.

Todas las búsquedas, insercciones y eliminaciones de un árbolB se terminaránen un orden O(logaritmo en base N) donde `base' es el factor medio derelleno.Con frecuencia, la inserción de datos ordenados en un árbolB produce unfactor de relleno bajo.Esta implementación se ha modificado para hacer las inserciones ordenadas elcaso mejor, produciendo un factor de relleno de páginas mucho mejor de lonormal. 

ERRORES

VÉASE TAMBIÉN

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

Index

NONMBRE

SINOPSIS

DESCRIPCIÓN

ERRORES

VÉASE TAMBIÉN

FALLOS