Provided by:
manpages-pt-dev_20040726-4_all 
NOME
btree - metodo de acesso a banco de dados btree
SINOPSE
#include <sys/types.h>
#include <db.h>
DESCRI,C~AO
A rotina dbopen e a interface de biblioteca para arquivos de banco de
dados. Um dos formatos de arquivo suportados sao os arquivos btree. A
descricao geral dos metodos de acesso a banco de dados esta em
dbopen(3), esta pagina de manual descreve somente informacoes
especificas de btree.
A estrutura de dados btree e uma estrutura de arvore ordenada e
balanceada que armazena pares associados chave/dados.
A estrutura de dados especifica do metodo de acesso btree, fornecida
para dbopen , e definida no arquivo de inclusao <db.h>, como segue:
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;
Os elementos desta estrutura sao como segue:
flags O valor do flag e especificado por qualquer um dos seguintes
valores:
R_DUP Permite chaves duplicadas na arvore, isto e, permite
insercao se a chave a ser inserida ja existe na arvore.
O comportamento padrao, como descrito em dbopen(3), e
sobreescrever uma chave encontrada quando se insere uma
nova chave, ou falhar se a flag R_NOOVERWRITE e
especificada. A flag R_DUP e sobreposta pela flag
R_NOOVERWRITE, e se a flag R_NOOVERWRITE e especificada,
uma tentativa de inserir chaves duplicadas na arvore
falhara.
Se o banco de dados contem chaves duplicadas, a ordem de
recuperacao dos pares chave/dados e indefinido se a
rotina get e usada, porem, chamadas de rotinas seq com a
flag R_CURSOR setada sempre retornara o ''primeiro''
logico ou qualquer grupo de chaves duplicadas.
cachesize
Um tamanho maximo sugerido (em bytes) do cache de memoria. Este
valor e somente para consulta, e o metodo de acesso alocara mais
memoria em vez de falhar. Como cada busca examina a pagina raiz
da arvore, fazer um cache das paginas mais recentemente usadas
melhorara substancialmente o tempo de acesso. Alem disso,
escritas fisicas sao atrasadas tanto quanto possivel, de forma
que um cache moderado pode reduzir o numero de operacoes de I/O
significativamente. Obviamente, o uso de cache aumenta (mas
somente aumenta) a probabilidade de corrupcao ou perda de dados,
se o sistema falhar enquanto a arvore esta sendo modificada. Se
cachesize e 0 (nenhum tamanho e especificado), um cache padrao e
usado.
maxkeypage
O numero maximo de chaves que serao armazenadas em uma unica
pagina. Nao implementado atualmente.
minkeypage
O numero minimo de chaves que serao armazenadas em uma unica
pagina. Este valor e usado para determinar quais chaves serao
armazenadas em paginas de sobrecarga, isto e, se uma chave ou
item de dado e maior que o tamanho da pagina dividido pelo valor
de minkeypage, sera armazenado em paginas de sobrecarga, em vez
de armazenar na propria pagina. Se minkeypage e 0 (nenhum
numero minimo de chaves e especificado), e usado o valor 2.
psize arvore. O tamanho minimo da pagina e de 512 bytes, e o maximo e
de 64K. Se psize e 0 (nenhum tamanho de pagina e especificado),
um tamanho de pagina e escolhido com base no tamanho de bloco de
I/O do sistema-base de arquivos.
compare
igual ou maior que zero se o primeiro argumento e considerado,
respectivamente, menor, igual ou maior que o argumento da
segunda chave. O mesma funcao de comparacao deve ser usada em
uma dada arvore toda vez que ela for aberta. Se compare e NULL
(nenhuma funcao de comparacao e especificada), as chaves sao
comparadas lexicamente, com chaves mais curtas consideradas
menores do que chaves mais longas.
prefix retornar um numero de bytes do argumento da segunda chave, que e
necessario para se determinar que e maior que o argumento da
primeira chave. Se as chaves sao iguais, o comprimento da chave
deve ser retornado. Note, a utilidade desta rotina e muito
dependente dos dados, mas, em alguns conjuntos de dados pode
produzir tamanhos de arvore e tempos de busca significativamente
reduzidos. Se prefix e NULL (nenhuma funccao de prefixo e
especificada), e nenhuma funcao de comparacao e especificada, e
usada uma rotina padrao de comparacao lexica. Se prefix e NULL
e uma rotina de comparacao e especificada, nenhuma comparacao de
prefixo e feita.
lorder A ordem dos bytes para inteiros nos metadados do banco de dados
armazenado. O numero deve representar a ordem como um inteiro;
por exemplo, a ordem "big endian" deveria ser o numero 4,321.
Se lorder e 0 (nenhuma ordem e especificada), e usada a ordem
corrente do host.
Se o arquivo ja existe (e a flag O_TRUNC nao esta especificada), os
valores especificados para as flags de parametros, 'lorder' e 'psize'
sao ignorados em favor destes valores usados quando a arvore foi
criada.
Buscas sequenciais para frente de uma arvore, da menor chave para a
maior.
O espaco liberado pela eliminacao dos pares chave/dado da arvore nunca
e reivindicado, apesar de ele normamente se tornar disponivel para
reuso. Isto significa que a estrutura de armazenagem 'btree' e
somente-crescente. As unicas solucoes sao evitar eliminacoes
excessivas, ou criar uma arvore fresca periodicamente a partir da busca
de uma arvore existente.
Buscas, insercoes e eliminacoes em uma 'btree' se completarao todas em
O lg base N, onde 'base' e o fator medio de preenchimento.
Frequentemente a insercao de dados ordenados em 'btrees' resultam em um
fator de preenchimento baixo. Esta implementacao foi modificada para
fazer a insercao ordenada no melhor caso, resultando em um fator de
preenchimento de pagina muito melhor que o normal.
ERROS
As rotinas de metodo de acesso a btree pode falhar e setar errno para
qualquer um dos erros especificados para a rotina de biblioteca
dbopen(3).
VEJA TAMB'EM
dbopen(3), hash(3), mpool(3), recno(3)
The Ubiquitous B-tree, Douglas Comer, ACM Comput. Surv. 11, 2 (June
1979), 121-138.
B-trees de prefixo, Bayer and Unterauer, Transacoes ACM em Sistemas de
Banco de Dados, Vol. 2, 1 (Marco de 1977), 11-26.
A Arte da Programa,c~ao de Computador Vol. 3: Ordena,c~ao e Busca, D.E.
Knuth, 1968, pp 471-480.
BUGS
Only big and little endian byte order is supported.
TRADU,C~AO PARA A L'INGUA PORTUGUESA
RUBENS DE JESUS NOGUEIRA <darkseid99@usa.net> (traducao) XXXXXX XX
XXXXX XXXXXXXX <xxxxxxxxxx@xxx.xxx> (revisao)
18 de agosto de 1994 BTREE(3)