Provided by: manpages-es_1.55-3_all bug

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)