.\" 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
.\"
.TH BTREE 3 "18 de agosto de 1994"
.\".UC 7
.SH NOME
btree \- mtodo de acesso a banco de dados btree 
.SH SINOPSE
.nf
.ft B
#include <sys/types.h>
#include <db.h>
.ft R
.fi
.SH DESCRIO
A rotina
.IR dbopen
 a interface de biblioteca para arquivos de banco de dados.
Um dos formatos de arquivo suportados so os arquivos btree. 
A descrio geral dos mtodos de acesso a banco de dados est em
.IR dbopen (3),
esta pgina de manual descreve somente informaes especficas de btree.
.PP
A estrutura de dados btree  uma estrutura de rvore ordenada e balanceada
que armazena pares associados chave/dados.
.PP
A estrutura de dados especfica do mtodo de acesso btree, fornecida para
.I dbopen
,  definida no arquivo de incluso <db.h>, como segue:
.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
Os elementos desta estrutura so como segue:
.TP
flags
O valor do flag  especificado por qualquer um dos seguintes valores:
.RS
.TP
R_DUP
Permite chaves duplicadas na rvore, isto , permite insero se a 
chave a ser inserida j existe na rvore.
O comportamento padro, como descrito em
.IR dbopen (3),
 sobreescrever uma chave encontrada quando se insere uma nova chave,
ou falhar se a flag R_NOOVERWRITE  especificada.
A flag R_DUP  sobreposta pela flag R_NOOVERWRITE, e se a flag
R_NOOVERWRITE  especificada, uma tentativa de inserir chaves duplicadas na
rvore falhar.
.IP
Se o banco de dados contm chaves duplicadas, a ordem de recuperao dos
pares chave/dados  indefinido se a rotina
.I get
 usada, porm, chamadas de rotinas
.I seq
com a flag R_CURSOR setada sempre retornar o ''primeiro''
lgico ou qualquer grupo de chaves duplicadas.
.RE
.TP
cachesize
Um tamanho mximo sugerido (em bytes) do cache de memria.
Este valor 
.B somente
para consulta, e o mtodo de acesso alocar mais memria em vez de falhar.
Como cada busca examina a pgina raiz da rvore, fazer um cache das pginas
mais recentemente usadas melhorar substancialmente o tempo de acesso.
Alm disso, escritas fsicas so atrasadas tanto quanto possvel, de forma que
um cache moderado pode reduzir o nmero de operaes de I/O significativamente.
Obviamente, o uso de cache aumenta (mas somente aumenta) a probabilidade de corrupao
ou perda de dados, se o sistema falhar enquanto a rvore est sendo modificada.
Se
.I cachesize
 0 (nenhum tamanho  especificado), um cache padro  usado.
.TP
maxkeypage
O nmero mximo de chaves que sero armazenadas em uma nica pgina.
No implementado atualmente.
.\" The maximum number of keys which will be stored on any single page.
.\" Because of the way the btree data structure works,
.\" .I maxkeypage
.\" must always be greater than or equal to 2.
.\" If
.\" .I maxkeypage
.\" is 0 (no maximum number of keys is specified) the page fill factor is
.\" made as large as possible (which is almost invariably what is wanted).
.TP
minkeypage
O nmero mnimo de chaves que sero armazenadas em uma nica pgina.
Este valor  usado para determinar quais chaves sero armazenadas em 
pginas de sobrecarga, isto , se uma chave ou item de dado  maior que o
tamanho da pgina dividido pelo valor de minkeypage, ser armazenado em
pginas de sobrecarga, em vez de armazenar na prpria pgina.
Se
.I minkeypage
 0 (nenhum nmero mnimo de chaves  especificado),  usado o valor 2.
.TP
psize
'Page size'  o tamanho (em bytes) das pginas usadas para os ns da
rvore. O tamanho mnimo da pgina  de 512 bytes, e o mximo  de 64K.
Se
.I psize
 0 (nenhum tamanho de pgina  especificado), um tamanho de pgina  escolhido
com base no tamanho de bloco de I/O do sistema-base de arquivos.
.TP
compare
'Compare'  a funo de comparao de chaves. Ela deve retornar um inteiro menor,
igual ou maior que zero se o primeiro argumento  considerado, respectivamente, 
menor, igual ou maior que o argumento da segunda chave.
O mesma funo de comparao deve ser usada em uma dada rvore toda vez que ela
for aberta.
Se
.I compare
 NULL (nenhuma funo de comparao  especificada), as chaves so comparadas
lexicamente, com chaves mais curtas consideradas menores do que chaves mais longas.
.TP
prefix
'Prefix'  a funo de comparao de prefixo. Se especificada, esta rotina deve 
retornar um nmero de bytes do argumento da segunda chave, que  necessrio
para se determinar que  maior que o argumento da primeira chave.
Se as chaves so iguais, o comprimento da chave deve ser retornado. Note, a 
utilidade desta rotina  muito dependente dos dados, mas, em alguns conjuntos de
dados pode produzir tamanhos de rvore e tempos de busca significativamente reduzidos.
Se
.I prefix
 NULL (nenhuma funco de prefixo  especificada),
.B e
nenhuma funo de comparao  especificada,  usada uma rotina padro 
de comparao lxica.
Se
.I prefix
 NULL e uma rotina de comparao  especificada, nenhuma comparao de
prefixo  feita.
.TP
lorder
A ordem dos bytes para inteiros nos metadados do banco de dados armazenado.
O nmero deve representar a ordem como um inteiro; por exemplo, 
a ordem "big endian" deveria ser o nmero 4,321.
Se
.I lorder
 0 (nenhuma ordem  especificada),  usada a ordem corrente do host.
.PP
Se o arquivo j existe (e a flag O_TRUNC no est especificada), os valores
especificados para as flags de parmetros, 'lorder' e 'psize' so ignorados
em favor destes valores usados quando a rvore foi criada.
.PP
Buscas sequenciais para frente de uma rvore, da menor chave para a maior.
.PP
O espao liberado pela eliminao dos pares chave/dado da rvore nunca  reivindicado,
apesar de ele normamente se tornar disponvel para reuso.
Isto significa que a estrutura de armazenagem 'btree'  somente-crescente. As nicas 
solues so evitar eliminaes excessivas, ou criar uma rvore fresca periodicamente
a partir da busca de uma rvore existente.
.PP
Buscas, inseres e eliminaes em uma 'btree' se completaro todas em
O lg base N, onde 'base'  o fator mdio de preenchimento. Frequentemente
a insero de dados ordenados em 'btrees' resultam em um fator de preenchimento baixo.
Esta implementao foi modificada para fazer a insero ordenada no melhor caso, 
resultando em um fator de preenchimento de pgina muito melhor que o normal.
.SH ERROS
As rotinas de mtodo de acesso a
.I btree
pode falhar e setar
.I errno
para qualquer um dos erros especificados para a rotina de biblioteca 
.IR dbopen (3).
.SH "VEJA TAMBM"
.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 "B-trees de prefixo" ,
Bayer and Unterauer, Transaes ACM em Sistemas de Banco de Dados, Vol. 2, 1
(Maro de 1977), 11-26.
.sp
.IR "A Arte da Programao de Computador Vol. 3: Ordenao e Busca" , 
D.E. Knuth, 1968, pp 471-480.
.SH BUGS
Only big and little endian byte order is supported.
.SH TRADUO PARA A LNGUA PORTUGUESA
\&\fR\&\f(CWRUBENS DE JESUS NOGUEIRA <darkseid99@usa.net> (traduo)\fR
\&\fR\&\f(CWXXXXXX XX XXXXX XXXXXXXX <xxxxxxxxxx@xxx.xxx> (reviso)\fR