Provided by: manpages-pt-dev_20040726-4_all bug

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)