.\" Copyright (c) 1990, 1993
.\"	The Regents of the University of California.  All rights reserved.
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in the
.\"    documentation and/or other materials provided with the distribution.
.\" 3. All advertising materials mentioning features or use of this software
.\"    must display the following acknowledgement:
.\"	This product includes software developed by the University of
.\"	California, Berkeley and its contributors.
.\" 4. Neither the name of the University nor the names of its contributors
.\"    may be used to endorse or promote products derived from this software
.\"    without specific prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\"	@(#)btree.3	8.4 (Berkeley) 8/18/94
.\"
.\" Translated into Spanish on Wed Apr 14 1999 by
.\" 	Juan Piernas Cnovas <piernas@ditec.um.es>
.\"
.TH BTREE 3 "18 agosto 1994"
.\".UC 7
.SH NONMBRE
btree \- mtodo de acceso a bases de datos rbolB
.SH SINOPSIS
.nf
.ft B
#include <sys/types.h>
#include <db.h>
.ft R
.fi
.SH DESCRIPCIN
La rutina
.IR 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 descripcin
general de los mtodos de acceso a las bases de datos se encuentra en
.IR dbopen (3),
esta pgina de manual describe nicamente informacin especifca de rbolB.
.PP
La estructura de datos rbolB es una estructura de rbol balanceado y
ordenado que almacena pares clave/datos asociados.
.PP
La estructura de datos especfica del mtodo de acceso a rbolB proporcionada
por
.I dbopen
se define en el fichero cabecera <db.h> como sigue:
.PP
typedef struct {
.RS
u_long flags;
.br
u_int cachesize;
.br
int maxkeypage;
.br
int minkeypage;
.br
u_int psize;
.br
int (*compare)(const DBT *key1, const DBT *key2);
.br
size_t (*prefix)(const DBT *key1, const DBT *key2);
.br
int lorder;
.RE
} BTREEINFO;
.PP
Los elementos de esta estructura son los siguientes:
.TP
flags
El valor del campo de opciones se especifica mediante un
.IR O -lgico
de cualquiera de los siguientes valores:
.RS
.TP
R_DUP
Permite claves duplicadas en el rbol, es decir, permite la insercin si la
clave a ser insertada ya existen en el rbol.
El comportamiento por defecto, como se describe en
.IR dbopen (3),
es sobrescribir una clave coincidente cuando se inserta una nueva clave o
fallar si se especifica la opcin R_NOOVERWRITE.
La opcin R_NOOVERWRITE predomina sobre la opcin R_DUP y si se especifica la
opcin R_NOOVERWRITE, los intentos de insertar claves duplicadas en el rbol
fracasarn.
.IP
Si la base de datos contiene claves duplicadas, el orden de recuperacin de
los pares clave/datos es indefinido si se usa la rutina
.I get
sin embargo, 
las llamadas a la rutina
.I seq
con la opcin R_CURSOR activa siempre devolver el primero ``lgico'' de
cualquier grupo de claves duplicadas.
.RE
.TP
cachesize
Un tamao mximo sugerido (en bytes) de la memoria cach.
Este valor es
.B slo
consultivo y el mtodo de acceso reservar ms memoria antes que fallar.
Ya que toda bsqueda examina la pgina raz del rbol, ocultar en cach las
pginas ms recientemente usadas mejorar sustancialmente el tiempo de
acceso.
Adems, las escrituras fsicas se demorarn tanto como sea posible, por lo
que una cach moderada puede reducir el nmero de operaciones de E/S de
forma significativa.
Obviamente, usar una cach incrementa (pero slo incrementa) la probabilidad
de corrupcin o de prdida de datos si el sistema cae mientras se est
modificando un rbol.
Si
.I cachesize
es 0 (no se especifica un tamao) se utiliza un tamao de cach por defecto.
.TP
maxkeypage
El nmero mximo de claves que se almacenarn en una nica pgina. No
implementado actualmente.
.\" El nmero mximo de claves que se almacenarn en una nica pgina.
.\" Debido a la forma en que la estructura de datos rbolB trabaja,
.\" .I maxkeypage
.\" siempre debe ser mayor o igual que 2.
.\" Si
.\" .I maxkeypage
.\" es 0 (no se especifica un nmero mximo de claves) el factor de relleno de
.\" la pgina se har tan grande como sea posible (que es casi
.\" invariablemente lo que se quiere).
.TP
minkeypage
El nmero mnimo de claves que se almacenarn en una nica pgina. Este
valor se usa para determinar qu claves se almacenarn en pginas de
overflow, es decir, si una clave o elementos de datos es mayor que el tamao
de pgina dividido por el valor de minkeypage, se almacenar en pginas de
overflow en lugar de en la propia pgina.
Si
.I minkeypage
es 0 (no se especifica un nmero mnimo de claves) se usa un valor de 2.
.TP
psize
Es el tamao (en bytes) de las pginas usadas por los nodos del rbol. El
tamao mnimo de pgina es 512 bytes y el tamao mximo de pgina es 64K.
Si
.I psize
es 0 (no se especifica un tamao de pgina) se selecciona un tamao de
pgina basado en el tamao de bloque de E/S del sistema de ficheros
subyacente.
.TP
compare
Es la funcin de comparacin 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 funcin de comparacin para un rbol dado cada vez que
se abre.
Si
.I compare
es NULL (no se especifica un funcin de comparacin), las claves se comparan
lxicamente, considerando las claves ms cortas menores que las claves ms
largas.
.TP
prefix
Es la funcin de comparacin de prefijos.
Si se especifica, esta rutina debe devolver el nmero 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 debera 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 tamaos de rbol y
tiempos de bsqueda reducidos de forma significativa.
Si
.I prefix
es NULL (no se especifica una funcin de prefijo)
.B y
no se especifca una funcin de comparacin, se usa por defecto una rutina de
comparacin lxica.
Si
.I prefix
es NULL y se especifica una funcin de comparacin, no se hace comparacin
de prefijos.
.TP
lorder
El orden de bytes para los enteros de los metadatos almacenados en la base
de datos. El nmero debera representar el orden como un entero; por
ejemplo, el orden `el byte de mayor peso el ltimo' (orden ascendente)
sera el nmero 4321.
Si
.I lorder
es 0 (no se especifica un orden) se utiliza el orden del anfitrin actual.
.PP
Si el fichero ya existe (y no se ha especificado la opcin O_TRUNC), se
ignoran los valores indicados para las opciones de los parmetros, lorder y
psize, en favor de los valores usados cuando se cre el rbol.
.PP
Los recorridos secuenciales hacia adelante de un rbol van desde la clave
ms pequea a la ms grande.
.PP
El espacio liberado al borrar los pares clave/datos del rbol nunca se
recupera, aunque normalmente se pone a disposicin para su reutilizacin.
Esto significa que la estructura de almacenamiento rbolB es de slo
crecimiento.
Las nicas soluciones son evitar excesivas eliminaciones o crear
peridicamente un rbol nuevo recorriendo el que ya existe.
.PP
Todas las bsquedas, insercciones y eliminaciones de un rbolB se terminarn
en un orden O(logaritmo en base N) donde `base' es el factor medio de
relleno.
Con frecuencia, la insercin de datos ordenados en un rbolB produce un
factor de relleno bajo.
Esta implementacin se ha modificado para hacer las inserciones ordenadas el
caso mejor, produciendo un factor de relleno de pginas mucho mejor de lo
normal.
.SH ERRORES
Las rutinas del mtodo de acceso
.I rbolB
pueden fracasar y asignar a
.I errno
cualquiera de los errores especificados en la rutina de biblioteca
.IR dbopen (3).
.SH "VASE TAMBIN"
.IR dbopen (3),
.IR hash (3),
.IR mpool (3),
.IR recno (3)
.sp
.IR "The Ubiquitous B-tree" ,
Douglas Comer, ACM Comput. Surv. 11, 2 (June 1979), 121-138.
.sp
.IR "Prefix B-trees" ,
Bayer and Unterauer, ACM Transactions on Database Systems, Vol. 2, 1
(March 1977), 11-26.
.sp
.IR "The Art of Computer Programming Vol. 3: Sorting and Searching" , 
D.E. Knuth, 1968, pp 471-480.
.SH FALLOS
Slo se soportan los rdenes de bytes ascendente (el byte de mayor peso el
ltimo) y descente (el bytes de menor peso el ltimo).