Provided by:
manpages-pt-dev_20040726-2_all 
NOME
btree - método de acesso a banco de dados btree
SINOPSE
#include <sys/types.h>
#include <db.h>
DESCRIÇÃO
A rotina dbopen é a interface de biblioteca para arquivos de banco de
dados. Um dos formatos de arquivo suportados são os arquivos btree. A
descrição geral dos métodos de acesso a banco de dados está em
dbopen(3), esta página de manual descreve somente informações
específicas de btree.
A estrutura de dados btree é uma estrutura de árvore ordenada e
balanceada que armazena pares associados chave/dados.
A estrutura de dados específica do método de acesso btree, fornecida
para dbopen , é definida no arquivo de inclusão <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 são como segue:
flags O valor do flag é especificado por qualquer um dos seguintes
valores:
R_DUP Permite chaves duplicadas na árvore, isto é, permite
inserção se a chave a ser inserida já existe na árvore.
O comportamento padrão, como descrito em 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á.
Se o banco de dados contém chaves duplicadas, a ordem de
recuperação dos pares chave/dados é indefinido se a
rotina get é usada, porém, chamadas de rotinas seq com a
flag R_CURSOR setada sempre retornará o ’’primeiro’’
lógico ou qualquer grupo de chaves duplicadas.
cachesize
Um tamanho máximo sugerido (em bytes) do cache de memória. Este
valor é somente para consulta, e o método de acesso alocará mais
memória em vez de falhar. Como cada busca examina a página raiz
da árvore, fazer um cache das páginas mais recentemente usadas
melhorará substancialmente o tempo de acesso. Além disso,
escritas físicas são atrasadas tanto quanto possível, de forma
que um cache moderado pode reduzir o número de operações de I/O
significativamente. Obviamente, o uso de cache aumenta (mas
somente aumenta) a probabilidade de corrupçao ou perda de dados,
se o sistema falhar enquanto a árvore está sendo modificada. Se
cachesize é 0 (nenhum tamanho é especificado), um cache padrão é
usado.
maxkeypage
O número máximo de chaves que serão armazenadas em uma única
página. Não implementado atualmente.
minkeypage
O número mínimo de chaves que serão armazenadas em uma única
página. Este valor é usado para determinar quais chaves serão
armazenadas em páginas de sobrecarga, isto é, se uma chave ou
item de dado é maior que o tamanho da página dividido pelo valor
de minkeypage, será armazenado em páginas de sobrecarga, em vez
de armazenar na própria página. Se minkeypage é 0 (nenhum
número mínimo de chaves é especificado), é usado o valor 2.
psize árvore. O tamanho mínimo da página é de 512 bytes, e o máximo é
de 64K. Se psize é 0 (nenhum tamanho de página é especificado),
um tamanho de página é 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 é considerado,
respectivamente, menor, igual ou maior que o argumento da
segunda chave. O mesma função de comparação deve ser usada em
uma dada árvore toda vez que ela for aberta. Se compare é NULL
(nenhuma função de comparação é especificada), as chaves são
comparadas lexicamente, com chaves mais curtas consideradas
menores do que chaves mais longas.
prefix retornar um número de bytes do argumento da segunda chave, que é
necessário para se determinar que é maior que o argumento da
primeira chave. Se as chaves são 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 prefix é NULL (nenhuma funcção de prefixo é
especificada), e nenhuma função de comparação é especificada, é
usada uma rotina padrão de comparação léxica. Se prefix é NULL
e uma rotina de comparação é especificada, nenhuma comparação de
prefixo é feita.
lorder A ordem dos bytes para inteiros nos metadados do banco de dados
armazenado. O número deve representar a ordem como um inteiro;
por exemplo, a ordem "big endian" deveria ser o número 4,321.
Se lorder é 0 (nenhuma ordem é especificada), é usada a ordem
corrente do host.
Se o arquivo já existe (e a flag O_TRUNC não está especificada), os
valores especificados para as flags de parâmetros, ’lorder’ e ’psize’
são ignorados em favor destes valores usados quando a árvore foi
criada.
Buscas sequenciais para frente de uma árvore, da menor chave para a
maior.
O espaço liberado pela eliminação dos pares chave/dado da árvore nunca
é reivindicado, apesar de ele normamente se tornar disponível para
reuso. Isto significa que a estrutura de armazenagem ’btree’ é
somente-crescente. As únicas soluções são evitar eliminações
excessivas, ou criar uma árvore fresca periodicamente a partir da busca
de uma árvore existente.
Buscas, inserções e eliminações em uma ’btree’ se completarão todas em
O lg base N, onde ’base’ é o fator médio de preenchimento.
Frequentemente a inserção de dados ordenados em ’btrees’ resultam em um
fator de preenchimento baixo. Esta implementação foi modificada para
fazer a inserção ordenada no melhor caso, resultando em um fator de
preenchimento de página muito melhor que o normal.
ERROS
As rotinas de método de acesso a btree pode falhar e setar errno para
qualquer um dos erros especificados para a rotina de biblioteca
dbopen(3).
VEJA TAMBÉM
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, Transações ACM em Sistemas de
Banco de Dados, Vol. 2, 1 (Março de 1977), 11-26.
A Arte da Programao de Computador Vol. 3: Ordenao e Busca, D.E.
Knuth, 1968, pp 471-480.
BUGS
Only big and little endian byte order is supported.
TRADUÇÃO PARA A LÍNGUA PORTUGUESA
RUBENS DE JESUS NOGUEIRA <darkseid99@usa.net> (tradução) XXXXXX XX
XXXXX XXXXXXXX <xxxxxxxxxx@xxx.xxx> (revisão)
18 de agosto de 1994 BTREE(3)