Provided by:
manpages-es_1.55-10_all 
NONMBRE
btree - metodo de acceso a bases de datos arbolB
SINOPSIS
#include <sys/types.h>
#include <db.h>
DESCRIPCI'ON
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 arbolB. La descripcion general de los metodos de acceso a las
bases de datos se encuentra en dbopen(3), esta pagina de manual
describe unicamente informacion especifica de arbolB.
La estructura de datos arbolB es una estructura de arbol balanceado y
ordenado que almacena pares clave/datos asociados.
La estructura de datos especifica del metodo de acceso a arbolB
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-
logico de cualquiera de los siguientes valores:
R_DUP Permite claves duplicadas en el arbol, es decir, permite
la insercion si la clave a ser insertada ya existen en el
arbol. 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 opcion R_NOOVERWRITE. La opcion
R_NOOVERWRITE predomina sobre la opcion R_DUP y si se
especifica la opcion R_NOOVERWRITE, los intentos de
insertar claves duplicadas en el arbol fracasaran.
Si la base de datos contiene claves duplicadas, el orden
de recuperacion de los pares clave/datos es indefinido si
se usa la rutina get sin embargo, las llamadas a la
rutina seq con la opcion R_CURSOR activa siempre
devolvera el primero ``logico'' de cualquier grupo de
claves duplicadas.
cachesize
Un tamano maximo sugerido (en bytes) de la memoria cache. Este
valor es s'olo consultivo y el metodo de acceso reservara mas
memoria antes que fallar. Ya que toda busqueda examina la
pagina raiz del arbol, ocultar en cache las paginas mas
recientemente usadas mejorara sustancialmente el tiempo de
acceso. Ademas, las escrituras fisicas se demoraran tanto como
sea posible, por lo que una cache moderada puede reducir el
numero de operaciones de E/S de forma significativa.
Obviamente, usar una cache incrementa (pero solo incrementa) la
probabilidad de corrupcion o de perdida de datos si el sistema
cae mientras se esta modificando un arbol. Si cachesize es 0
(no se especifica un tamano) se utiliza un tamano de cache por
defecto.
maxkeypage
El numero maximo de claves que se almacenaran en una unica
pagina. No implementado actualmente.
minkeypage
El numero minimo de claves que se almacenaran en una unica
pagina. Este valor se usa para determinar que claves se
almacenaran en paginas de overflow, es decir, si una clave o
elementos de datos es mayor que el tamano de pagina dividido por
el valor de minkeypage, se almacenara en paginas de overflow en
lugar de en la propia pagina. Si minkeypage es 0 (no se
especifica un numero minimo de claves) se usa un valor de 2.
psize Es el tamano (en bytes) de las paginas usadas por los nodos del
arbol. El tamano minimo de pagina es 512 bytes y el tamano
maximo de pagina es 64K. Si psize es 0 (no se especifica un
tamano de pagina) se selecciona un tamano de pagina basado en el
tamano de bloque de E/S del sistema de ficheros subyacente.
compare
Es la funcion de comparacion 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
funcion de comparacion para un arbol dado cada vez que se abre.
Si compare es NULL (no se especifica un funcion de comparacion),
las claves se comparan lexicamente, considerando las claves mas
cortas menores que las claves mas largas.
prefix Es la funcion de comparacion de prefijos. Si se especifica,
esta rutina debe devolver el numero 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
deberia 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 tamanos de arbol
y tiempos de busqueda reducidos de forma significativa. Si
prefix es NULL (no se especifica una funcion de prefijo) y no se
especifca una funcion de comparacion, se usa por defecto una
rutina de comparacion lexica. Si prefix es NULL y se especifica
una funcion de comparacion, no se hace comparacion de prefijos.
lorder El orden de bytes para los enteros de los metadatos almacenados
en la base de datos. El numero deberia representar el orden como
un entero; por ejemplo, el orden `el byte de mayor peso el
ultimo' (orden ascendente) seria el numero 4321. Si lorder es 0
(no se especifica un orden) se utiliza el orden del anfitrion
actual.
Si el fichero ya existe (y no se ha especificado la opcion O_TRUNC), se
ignoran los valores indicados para las opciones de los parametros,
lorder y psize, en favor de los valores usados cuando se creo el arbol.
Los recorridos secuenciales hacia adelante de un arbol van desde la
clave mas pequena a la mas grande.
El espacio liberado al borrar los pares clave/datos del arbol nunca se
recupera, aunque normalmente se pone a disposicion para su
reutilizacion. Esto significa que la estructura de almacenamiento
arbolB es de solo crecimiento. Las unicas soluciones son evitar
excesivas eliminaciones o crear periodicamente un arbol nuevo
recorriendo el que ya existe.
Todas las busquedas, insercciones y eliminaciones de un arbolB se
terminaran en un orden O(logaritmo en base N) donde `base' es el factor
medio de relleno. Con frecuencia, la insercion de datos ordenados en
un arbolB produce un factor de relleno bajo. Esta implementacion se ha
modificado para hacer las inserciones ordenadas el caso mejor,
produciendo un factor de relleno de paginas mucho mejor de lo normal.
ERRORES
Las rutinas del metodo de acceso 'arbolB pueden fracasar y asignar a
errno cualquiera de los errores especificados en la rutina de
biblioteca dbopen(3).
V'EASE TAMBI'EN
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
Solo se soportan los ordenes de bytes ascendente (el byte de mayor peso
el ultimo) y descente (el bytes de menor peso el ultimo).
18 agosto 1994 BTREE(3)