Usuário:Aexpedito/Btree

Na ciência da computação uma árvore B é uma estrutura de dados projetada para funcionar especialmente em memória secundária como um disco magnético ou outros dispositivos de armazenamento secundário. Dentre suas propriedades ela permite a inserção, remoção e busca de chaves numa complexidade de tempo logarítmica e, por esse motivo, é muito empregada em aplicações que necessitam manipular grandes quantidades de informação tais como um banco de dados ou um sistema de arquivos.

Inventada por Rudolf Bayer e Edward M. McCreight no ano de 1971 enquanto trabalhavam no Boeing Scientific Research Labs, a origem do nome (árvore B) não foi definida por estes. Especula-se que o B venha da palavra balanceamento, do nome de um de seus inventores Bayer ou de Boeing, nome da empresa.

Se analisarmos as árvores-B, elas são uma generalização das árvores binária de busca, pois cada nó de uma árvore binária armazena uma única chave de busca, enquanto as árvores-B armazenam um número maior do que um de chaves de busca em cada nó, ou no termo mais usual para essa árvore, em cada página. Como a idéia principal das árvores B é trabalhar com dispositivos de memória secundária, quanto menos acessos a disco a estrutura de dados proporcionar, melhor será o desempenho do sistema na operação de busca sobre os dados manipulados.

Visão geral

Árvore-B de ordem 5

Os dispositivos de memória de um computador consiste em memória principal e secundária sendo cada uma delas com suas características. A memória primária é mais conhecida como memória volátil de endereçamento direto (RAM), esta por sua vez apresenta baixo tempo de acesso, porém armazena um volume relativamente pequeno de informação e altos custos. Já a memória secundária, possui um endereçamento indireto, armazena um grande volume de informação e possui um acesso (seek) muito lento quando comparada com a memória primária. As árvores-B é uma solução para cenários em que o volume de informação é alto (e este não pode ser armazenado diretamente em memória primária) e, portanto, apenas algumas páginas da árvore podem ser carregadas em memória primária.

As árvores-B são organizadas por nós, tais como os das árvores binárias de busca, mas estes apresentam um conjunto de chaves maior do que um e são usualmente chamados de páginas. As chaves em cada página são, no momento da inserção, ordenadas de forma crescente e para cada chave há dois endereços para páginas filhas, sendo que, o endereço à esquerda é para uma página filha com um conjunto de chaves menor e o à direita para uma página filha com um conjunto de chaves maior. A figura acima demonstra essa organização de dados característica.

Vale lembrar que todo este endereçamento esta gravado em arquivo (memória secundária) e que um acesso a uma posição do arquivo é uma operação muito lenta. Através da paginação é possível carregar em memória primária uma grande quantidade de registros contidos numa única página e assim decidir qual a próxima página que o algoritmo de busca irá carregar em memória primária caso esta chave buscada não esteja na primeira página carregada. Após carregada uma página em memória primária, a busca de chave pode ser realizada linearmente sobre o conjunto de chaves ou através de busca binária.

Definição

Para definir uma árvore B devemos esclarecer os conceitos de ordem e página folha de acordo com cada autor. Bayer e McCreight^[1], Comer^[2], dentre outros, definem a ordem como sendo o número mínimo de chaves que uma página pode conter, ou seja, com excessão da raiz todas devem conter esse número mínimo de chaves, mas essa definição pode causar ambiguidades quando se quer armazenar um número máximo ímpar de chaves^[3]. Por exemplo, se uma árvore B é de ordem 3, uma página estará cheia quando tiver 6 ou 7 chaves^[3]? Ou ainda, se queremos armazenar no máximo 7 chaves em cada página qual será a ordem da árvore, uma vez que, o mínimo de chaves é k e o máximo 2k?^[1]

Knuth propôs que a ordem de uma árvore B fosse o número máximo de páginas filha que toda página pode conter. Dessa forma o número máximo de chaves por página ficou estabelecido como a ordem menos um^[4].

O termo página folha também é inconsistente, pois é referenciado diferentemente por vários autores. Bayer e McCreight referem-se a estas como as páginas mais distantes da raiz, ou aquelas que contém chaves no nível mais baixo da árvore.^[1] Já Knuth define o termo como as páginas que estão abaixo do ultimo nível da árvore, ou seja, páginas que não contém nenhuma chave.^[4]

De acordo com a definição de Knuth de ordem e página folha de Bayer e McCreight, uma árvore B de ordem d (número máximo de páginas filhas para uma página pai) deve satisfazer as seguintes propriedades:

Cada página contém no máximo d páginas filhas
Cada página, exceto a raiz e as folhas, tem pelo menos ⌈d/2⌉ páginas filhas
A página raiz tem ao menos duas páginas filhas (ao menos que ela seja uma folha)
Toda página folha possui a mesma profundidade, na qual é equivalente à altura da árvore
Uma página não folha com k páginas filha contem k-1 chaves
Uma página folha contém pelo menos ⌈d/2⌉-1 chaves e no máximo d-1 chaves

Página raiz

A página raiz das árvores B possuem o limite superior de d-1 chaves armazenadas, mas não apresentam um número mínimo de chaves, ou seja, elas podem ter um número inferior a ⌈d/2⌉-1 de chaves. Na figura acima, essa página é representada pelo nó que possui o registro 7 e 16.

Páginas internas

As páginas internas são as páginas em que não são folhas e nem raiz, estas devem conter o número mínimo (⌈d/2⌉-1) e máximo (d-1) de chaves.

Páginas folha

Estes são os nós que possuem a mesma restrição de máximo e mínimo de chaves das páginas internas, mas estes não possuem apontadores para páginas filhas. Na figura acima são todos os demais nós exceto a raiz.

Estrutura da página

Uma possível estrutura de dados para uma página de árvore B na linguagem C:

#define D 5 //árvore de ordem 5

typedef struct BTPage{
	//armazena numero de chaves na pagina
	short int totalChaves;
	
	//vetor de chaves
	int chaves[D-1];
	
	//endereços das paginas filhas, -1 aponta para NULL
	int filha[D];	
}Page;

Operações básicas

Exemplo de inserção em árvore B da sequência de 1 a 7. Os nós dessa árvore possuem no máximo 3 filhos

As operações básicas sobre um árvore B são a busca, inserção e remoção de chaves.

Busca

A busca de uma chave k em uma árvore B é muito parecido com uma busca em árvore binária, porém, agora a cada nó carregado em memória primária temos várias vias para o nó seguinte da busca e não apenas duas. Caso a chave k não esteja na página carregada em memória primária basta carregar a próxima página apontada pelo intervalo que a chave k corresponde na página atual.

Inserção

A operação de inserção, inicialmente com a árvore vazia, deve garantir que o nó raiz será criado. Criado o nó raiz, a inserção das próximas chaves seguem o mesmo procedimento: busca-se a posição correta da chave em um nó folha e insere a chave garantindo a ordenação destas. Após feito isso podem ocorrer duas situações:

Página folha está com um número menor de chaves do que o máximo permitido (d-1): Nesse caso apenas inserimos a chave de maneira ordenada na página
Página folha completa ou com o número máximo de chaves permitido (d-1): Nesse caso ocorre o overflow da página em questão e é necessário a operação de split para manter o balanceamento da árvore.
1. Primeiramente escolhe-se um valor intermediário na sequência ordenada de chaves da página incluindo-se a nova chave que deveria ser inserida. Este valor é exatamente uma chave que ordenada com as chaves da página estará no meio da sequência.
2. Cria-se uma nova página e os valores maiores do que a chave intermediária são armazenados nessa nova página e os menores continuam na página anterior (operação de split).
3. Esta chave intermediária escolhida deverá ser inserido na página pai, na qual poderá também sofrer overflow ou deverá ser criada caso em que é criada uma nova página raiz. Esta série de overflows pode se propagar para toda a árvore B, o que garante o seu balanceamento na inserção de chaves.

Remoção

Figura 1: Remoção da chave 8 e posterior reorganização da estrutura

O algoritmo de remoção de uma árvore B deve garantir que as propriedades da árvore sejam mantidas, pois uma chave pode ser eliminada de qualquer página e não apenas de páginas folha. Nessa operação podem ocorrer underflows nas páginas, ou seja, quando há um número abaixo do mínimo permitido (⌈d/2⌉-1) de chaves em uma página. Na remoção há vários casos a se analisar, as seguintes figuras apresentam alguns casos numa árvore de ordem 5:

Caso da figura 1: Neste caso a remoção da chave 8 não causa o underflow na página folha em que ela está, portanto ela é simplesmente apagada e as outras chaves são reorganizadas mantendo sua ordenação.

Figura 2: Remoção da chave 18 e posterior redistribuição das chaves

Caso da figura 2: O caso da figura 2 é apresentado a técnica de redistribuição de chaves. Na remoção da chave 18, a página que contém essa chave possui uma página irmã à direita com um número superior ao mínimo de chaves (página com chaves 24, 25 e 26) e, portanto, estas podem ser redistribuídas entre elas de maneira que no final nenhuma delas tenha um número inferior ao mínimo permitido.

Figura 3: Remoção da chave 5 e posterior concatenação com página irmã à esquerda

Caso da figura 3: Nesta figura foi removido a chave 5, como não foi possivel utilizar a técnica de redistribuição, pois as páginas irmãs possuem o número mínimo de chaves, então foi necessário concatenar o conteúdo da página que continha a chave 5 com sua página irmã à esquerda e a chave separadora pai. Ao final do processo a página pai fica com uma única chave (underflow) e é necessário diminuir a altura da árvore de maneira que o conteúdo da página pai e sua irmã, juntamente com a raiz, sejam concatenados para formar uma página única.

Figura 4: Remoção da chave 13 e promoção da menor chave da subárvore à direita de 13

Caso da figura 4: A remoção da chave 13 nesse caso foi realizado com a substituição do 13 pelo menor número da subárvore à direita de 13 que era o 14. Essa troca não causou o underflow da página em que estava o 14 e, portanto não gerou grandes alterações na árvore.

Figura 5: Chave 14 é promovida para a raiz o que causa underflow em sua página

Caso da figura 5: Caso semelhante ao anterior, mas esse ocorre o underflow da página que contém a menor chave da subárvore à direita de 13. Com isso, como não é possivel a redistribuição, concatena-se o conteúdo dessa página com sua irmã à direita o que gera também underflow da página pai. O underflow da página pai também é resolvido com a concatenação com sua irmã e a raiz, resultando na diminuição da altura da árvore.

Algoritmos

Busca

Neste algoritmo recursivo os parâmetros recebidos inicialmente devem ser a chave buscada e um ponteiro para a página raiz da árvore B.

Busca(k, ponteiroRaiz) 
{
	se(ponteiroRaiz == -1)
	{
		return (chave nao encontrada)
	}
	senao
	{
		carrega em memoria primaria pagina apontado por ponteiroRaiz
		procura k na pagina carregada
		se(k foi encontrada)
		{
			return (chave encontrada)
		}
		senao
		{
			ponteiro = ponteiro para a próxima página da possível ocorrência de k
			return (Busca (k, ponteiro))
		}
	}
}

Inserção

O algoritmo de inserção em árvore B é um procedimento recursivo que inicialmente ponteiroRaiz aponta para a raiz da árvore em arquivo, key é a chave a ser inserida e chavePromovida representa a chave promovida após um split de uma página qualquer.

Inserçao(ponteiroRaiz, key, chavePromovida)
{
	se(ponteiroRaiz == -1)//se ponteiroRaiz nao aponta para nenhuma pagina
	{
		chavePromovida = key
		return(flag que indica que houve promoção de chave)
	}
	senao
	{
		carregue a página P apontada por ponteiroRaiz em memoria primária
		busque por key nessa página P
		posicao = página no qual key poderia estar 
	}
	
	se(key foi encontrada)
	{
		//chave ja esta na arvore, retorne uma flag de erro
		return(flag de erro)
	}
	
	flagRetorno = Inserçao(posicao, key, chavePromovida)//procedimento recursivo
	
	se(flagRetorno indica que nao houve promoçao de chave ou que ocorreu um erro)
	{
		return(conteudo de flagRetorno)
	}
	senao se(há espaço na página P para chavePromovida)
	{
		insere chavePromovida na página P
		escreve página P em arquivo
		return(flag que indica que nao houve promocao de chave)
	}
	senao //nao ha espaço em P para key
	{
		realize operação de split em P
		escreva em arquivo  a nova página e a página P
		return(flag que indica que houve promoçao de chave)
	}	
}

Remoção

1  Busque a chave k
2  Busque a menor chave M na página folha da sub-árvore à direita de k
3  Se a chave k não está numa folha
4  {	
5 	 Substitua k por M
6  }
7  Apague a chave k ou M da página folha
8  Se a página folha não sofrer underflow
9  {
10 	 fim do algoritmo
11 }
12 Se a página folha sofrer underflow, verifique as páginas irmãs da página folha
13 {
14    Se uma das páginas tiver um número maior do que o mínimo redistribua as chaves
15    Senão concatene as páginas com uma de suas irmãs e a chave pai separadora
16 }
17 Se ocorrer concatenação de páginas aplique o trecho das linhas 8 até 17 para a página pai da folha

Variações

As árvores B não são as únicas estruturas de dados usadas em aplicações que demandam a manipulação de grande volume de dados, também existem variações desta que proporcionam determinadas características como as árvores B+ e B*. Estas, por sua vez, se assemelham muito com as árvores B, mas possuem propriedades diferentes.

As árvores B+ possuem seus dados armazenados somente em seus nós folha e, seus nós internos e raiz, são apenas referências para as chaves que estão em nós folha. Assim é possivel manter ponteiros em seus nós folha para um acesso sequencial ordenado das chaves contidas no arquivo.
Árvores B* diferem das árvores B em relação ao particionamento de suas páginas. A estratégia dessa variação é realizar o particionamento de duas páginas irmãs somente quando estas estiverem completamente cheias e, claro, isso somente é possível através da resdistribuição de chaves entre estas páginas filhas. Estando completamente cheias, as chaves são redistribuídas entre três páginas diferentes que são as duas irmãs anteriores e uma nova criada.

Comparação com as variações

Se compararmos as árvores B com suas variações podemos enumerar algumas características importantes para a escolha de implementação destas:

Árvores B+:

A principal característica proporcionada por esta variação é o fato de permitir o acesso sequencial das chaves por meio de seu sequence set de maneira mais eficiente do que o realizado em árvores B .^[5]
Além do mais, as páginas utilizadas em seu index set podem conter mais apontadores para páginas filha permitindo reduzir a altura da árvore.^[5]

Árvores B*:

A principal vantagem decorrente dessa variação é o fato desta apresentar suas páginas com no mínimo 2/3 do número máximo de chaves, ou seja, esta variação apresenta no pior caso um índice de utilização do arquivo de 66%, enquanto em árvores B esse índice de pior caso cai para 50%.^[2]

Ver também

Wikilivros

O wikilivro Algoritmos e Estruturas de Dados tem uma página intitulada Árvores B

Referências

↑ ^a ^b ^c Bayer, R.; McCreight, E. (1972). «Organization and Maintenance of Large Ordered Indexes» (PDF). Acta Informatica. 1: 173-189
↑ ^a ^b Comer, Douglas (Junho 1979). «The Ubiquitous B-Tree». Computing Surveys. 11: 123–137. ISSN 0360-0300. doi:10.1145/356770.356776
↑ ^a ^b Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 363
↑ ^a ^b Knuth, Donald (1998). The Art of Computer Programming. Sorting and Searching (em inglês). 3 2 ed. [S.l.]: Addison-Wesley
↑ ^a ^b Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 433

Bibliografia

Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2001). «18». Introduction to Algorithms (em inglês) 2 ed. [S.l.]: MIT Press and McGraw-Hill. ISBN 0-262-03293-7

Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. 590 páginas. ISBN 0-201-55713-4

Knuth, Donald (1998). The Art of Computer Programming. Sorting and Searching (em inglês). 3 2 ed. [S.l.]: Addison-Wesley. ISBN 0-201-89685-0

Ligações externas

Categoria:Estruturas de dados

[bayer-1] Bayer, R.; McCreight, E. (1972). «Organization and Maintenance of Large Ordered Indexes» (PDF). Acta Informatica. 1: 173-189

[comer-2] Comer, Douglas (Junho 1979). «The Ubiquitous B-Tree». Computing Surveys. 11: 123–137. ISSN 0360-0300. doi:10.1145/356770.356776

[ambiguidade-3] Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 363

[knuth-4] Knuth, Donald (1998). The Art of Computer Programming. Sorting and Searching (em inglês). 3 2 ed. [S.l.]: Addison-Wesley

[arvoreb+-5] Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 433

[1]

[2]

[3]

[4]

[5]