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 Programação de Computador Vol. 3: Ordenação 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)