.\" 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 \- método de acesso a banco de dados btree .SH SINOPSE .nf .ft B #include #include .ft R .fi .SH DESCRIÇÃO A rotina .IR 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 .IR dbopen (3), esta página de manual descreve somente informações específicas 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 específica do método de acesso btree, fornecida para .I dbopen , é definida no arquivo de inclusão , 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 são 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 inserção se a chave a ser inserida já existe na árvore. O comportamento padrão, 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 contém chaves duplicadas, a ordem de recuperação dos pares chave/dados é indefinido se a rotina .I get é usada, porém, chamadas de rotinas .I seq com a flag R_CURSOR setada sempre retornará o ''primeiro'' lógico ou qualquer grupo de chaves duplicadas. .RE .TP cachesize Um tamanho máximo sugerido (em bytes) do cache de memória. Este valor é .B 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 .I cachesize é 0 (nenhum tamanho é especificado), um cache padrão é usado. .TP maxkeypage O número máximo de chaves que serão armazenadas em uma única página. Não 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 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 .I minkeypage é 0 (nenhum número mínimo de chaves é especificado), é usado o valor 2. .TP psize 'Page size' é o tamanho (em bytes) das páginas usadas para os nós da árvore. O tamanho mínimo da página é de 512 bytes, e o máximo é de 64K. Se .I 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. .TP compare 'Compare' é a função de comparação 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 função de comparação deve ser usada em uma dada árvore toda vez que ela for aberta. Se .I 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. .TP prefix 'Prefix' é a função de comparação de prefixo. Se especificada, esta rotina deve 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 .I prefix é NULL (nenhuma funcção de prefixo é especificada), .B e nenhuma função de comparação é especificada, é usada uma rotina padrão de comparação léxica. Se .I prefix é NULL e uma rotina de comparação é especificada, nenhuma comparação de prefixo é feita. .TP 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 .I lorder é 0 (nenhuma ordem é especificada), é usada a ordem corrente do host. .PP 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. .PP Buscas sequenciais para frente de uma árvore, da menor chave para a maior. .PP 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. .PP 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. .SH ERROS As rotinas de método 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 TAMBÉM" .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, Transações ACM em Sistemas de Banco de Dados, Vol. 2, 1 (Março de 1977), 11-26. .sp .IR "A Arte da Programação de Computador Vol. 3: Ordenação e Busca" , D.E. Knuth, 1968, pp 471-480. .SH BUGS Only big and little endian byte order is supported. .SH TRADUÇÃO PARA A LÍNGUA PORTUGUESA \&\fR\&\f(CWRUBENS DE JESUS NOGUEIRA (tradução)\fR \&\fR\&\f(CWXXXXXX XX XXXXX XXXXXXXX (revisão)\fR