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

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)