Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Wikipédia

Árvore B

Em ciência da computação, uma árvore B é uma estrutura de dados em árvore, auto-balanceada, que armazena dados classificados e permite pesquisas, acesso sequencial, inserções e remoções em tempo logarítmico. A árvore B é uma generalização de uma árvore de pesquisa binária em que um nó pode ter mais que dois filhos.[1] Diferente das árvores de pesquisa binária auto-balanceadas, a árvore B é bem adaptada para sistemas de armazenamento que leem e escrevem blocos de dados relativamente grandes, como discos.

Árvore B
Tipo Árvore
Ano 1971
Inventado por Rudolf Bayer, Edward Meyers McCreight
Complexidade de Tempo em Notação big O
Algoritimo Caso Médio Pior Caso
Espaço O(n) O(n)
Busca O(log n) O(log n)
Inserção O(log n) O(log n)
Remoção O(log n) O(log n)
Exemplo de Árvore B

É normalmente usada em bancos de dados e sistemas de arquivos e foi projetada para funcionar especialmente em memória secundária como um disco magnético ou outros dispositivos de armazenamento secundário. As árvores B são semelhantes as árvores preto e vermelho, mas são melhores para minimizar operações de E/S de disco. Muitos sistemas de bancos de dados usam árvores B ou variações da mesma para armazenar informações. Dentre suas propriedades ela permite a inserção, remoção e busca de chaves numa complexidade temporal 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 sistemas de arquivos.

Inventada por Rudolf Bayer e Edward Meyers McCreight em 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.

Árvores B 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 ideia 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

editar
 
Árvore-B de ordem 2(Bayer & McCreight 1972) ou ordem 5 (Knuth 1998).

Os dispositivos de memória de um computador consistem na 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. A árvore 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. Se um nó interno x contém n[x] chaves, então x tem n[x] + 1 filhos. As chaves do nó x são usadas como pontos de divisão que separam o intervalo de chaves manipuladas por x em x[x] subintervalos, cada qual manipulado por um filho de x.

Vale lembrar que todo este endereçamento está 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

editar

Nó ou página

editar

Um nó ou página, geralmente é representado por um conjunto de elementos apontando para seus filhos. Alguns autores consideram a ordem de uma árvore B como sendo a quantidade de registros que a página pode suportar. Outros consideram a ordem como a quantidade de campos apontadores. Todo nó da árvore tem um mínimo de registros definido pela metade da ordem, arredondando-se para baixo, caso a árvore seja de ordem ímpar, exceto a raiz da árvore, que pode ter o mínimo de um registro. Por exemplo, os nós de uma árvore de ordem 5, podem ter, no mínimo  registros, ou seja, dois registros. A quantidade de filhos que um nó pode ter é sempre a quantidade de registros do nó mais 1 (V+1). Por exemplo, se um nó tem 4 registros, este nó terá obrigatoriamente 5 apontamentos para os nós filhos.

Para definir uma árvore B devemos esclarecer os conceitos de ordem e página folha de acordo com cada autor Bayer e McCreight,[2] Comer,[3] dentre outros, definem a ordem como sendo o número mínimo de chaves que uma página pode conter, ou seja, com exceçã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.[4] Por exemplo, se uma árvore B é de ordem 3, uma página estará cheia quando tiver 6 ou 7 chaves[4]? Ou ainda, se quisermos 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?[2]

Knuth propôs que a ordem de uma árvore B fosse o número máximo de páginas filhas 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.[5]

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.[2] 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.[5]

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:

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

Página raiz

editar

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

editar

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

editar

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

editar

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];

 //Ponteiros das paginas filhas, -1 aponta para NULL
 struct BTPage filha[D];
}Page;

Operações básicas

editar
 
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

Altura de uma árvore B

O número de acessos ao disco exigidos para a maioria das operações em uma árvore B é proporcional a altura da árvore B.

Como criar uma árvore vazia

Para construir uma árvore B, primeiro criamos um nó raiz vazio,e depois inserimos novas chaves. Esses procedimentos alocam uma página de disco para ser usada como um novo nó no tempo O(1)

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

Busca

editar

A busca de uma chave k em uma árvore B é muito parecido com uma busca em árvore binária, exceto pelo fato de que, em vez de tomar uma decisão de ramificação binária ou de “duas vias” em cada nó, tomamos uma decisão de ramificação de várias vias, de acordo com o número de filhos do nó. Em cada nó interno x, tomamos uma decisão de ramificação de (n[x] + 1) vias.

Esse método toma como entrada um ponteiro para o nó de raiz de uma subárvore e uma chave k a ser pesquisada.

Inserção

editar

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, considerando a abordagem de inserção de baixo para cima (Bottom-up) na árvore B, podem ocorrer duas situações:

  1. 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
  2. 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.

Uma abordagem melhorada para a inserção é a de cima para baixo (Top-down) que utiliza uma estratégia parecida com a inserção de baixo para cima, a lógica para a inserção das próximas chaves (levando em consideração que a raiz já está criada) é a seguinte: busca-se a posição correta da chave em um nó, porém durante a busca da posição correta todo nó que estiver com o número máximo de chaves (d-1) é feita a operação de split, adicionando o elemento intermediário na sequência ordenada de chaves da página no pai e separando os elementos da página em outras duas novas páginas, onde uma vai conter os elementos menores que o elemento intermediário e a outra os elementos maiores que ele, a inserção será feita em um nó folha somente após todo o processo de split e insere a chave garantindo a ordenação destas. Esta abordagem melhorada previne de ter que ficar fazendo chamadas sucessivas ao pai do nó, o que pode ser caro se o pai estiver na memória secundária.

Split

editar
 
Trecho de uma árvore que tem ordem m = 3, sendo 10 o valor_central no nó que sofre o split.

A função do split é dividir o nó em duas partes e "subir" o valor central do nó para um nó acima ou, caso o nó que sofreu o split seja a raiz, criar uma nova raiz com um novo nó. O que ocorre quando é feito um split:

  • Primeiramente calcula-se qual a mediana dos valores do nó, no caso o valor central do nó. Sendo tamanho = quantidade de elementos no nó, mediana = tamanho/2 e usamos a mediana para acessar o elemento que se encontra no centro do nó, no caso valor_central = valores[mediana];
  • É testado se o nó que sofreu split tem pai, caso não, cria-se um novo nó apenas com o valor valor_central e o define como a nova raiz. São criados mais dois nós, cada um irá conter os valores do nó que estavam antes da mediana e depois da mediana. Um nó terá os valores menores que o valor_central e ficará na primeira posição dos filhos da nova raiz, e o outro nó terá os valores maiores que o valor_central e ficará na segunda posição dos filhos da nova raiz;
  • Caso o nó tenha pai, adicionamos o valor_central ao nó pai. Caso o nó pai já esteja cheio, este também vai sofrer split após a inserção do valor nele. E da mesma forma que criamos dois nós para o caso do nó não ter pai, criaremos dois nós que conterão os valores menores e maiores que o valor_central. O nó com os menores valores ficará posicionado como filho do lado esquerdo do valor_central e o nó com os maiores valores ficará posicionado como filho do lado direito do valor_central. Por exemplo: Caso o valor_central seja inserido na posição 0 do array de valores do nó pai, o nó filho com os menores valores ficará na posição 0 do array de filhos, e o nó com os maiores valores ficará na posição 1 do array de filhos.

Remoção

editar

A remoção é análoga a inserção, sendo que 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. A remoção de um nó interno exige que os filhos do nó sejam reorganizados. Como na inserção, devemos nos resguardar contra a possibilidade da eliminação produzir uma árvore cuja estrutura viole as propriedades de árvores B. Lembrando que devemos assegurar que um nó não ficará pequeno demais durante a eliminação (a não ser pelo fato da raiz pode ter essa pequena quantidade de filhos).

O método para remover a chave k da subárvore com raiz em x deve estar estruturado para garantir que quando ele for chamado recursivamente em um nó x, o número de chaves em x seja pelo menos o grau mínimo t. Essa condição exige uma chave além do mínimo exigido pelas condições normais da árvore B, de forma que, quando necessário, uma chave seja movida para dentro do nó filho.

Descrição de como a eliminação funciona:

  1. Se a chave k está no nó x e x é uma folha, elimine a chave k de x.
  2. Se a chave k está no nó x e x é um nó interno:
    1. Se o filho y que precede k no nó x tem pelo menos t chaves, então encontre o predecessor k’ de k na subárvore com raiz em y. Elimine recursivamente k’, e substitua k por k’ em x.
    2. Simetricamente, se o filho z que segue k no nó x tem pelo menos t chaves, então encontre o sucessor k’ de k na subárvore com raiz em z. Elimine recursivamente k’ e substitua k por k’ em x.
    3. Caso contrário, se tanto y quanto z tem apenas t-1 chaves, faça a intercalação de k e todos os seus itens z em y, de modo que x perca tanto k quanto o ponteiro para z, e y contenha agora 2t-1 chaves.
  3. Se a chave k não estiver presente no nó interno x, determine a raiz c[x] da subárvore apropriada  que deve conter k, se k estiver absolutamente na árvore. Se c[x] tiver somente t - 1 chaves:
    1. Se c[x] tiver somente t-1 chaves, mas tiver um irmão com t chaves, forneça a c[x] uma chave extra, movendo uma chave de x  para baixo até c[x], movendo uma chave do irmão esquerdo ou direito imediato de c[x] para dentro de x, e movendo o ponteiro do filho apropriado do irmão para c[x]
    2. Se c[x] e todos os irmão de c[x] têm t-1 chaves, faça a intercalação de c[x] com um único irmão, o que envolve mover uma chave de x para baixo até o novo nó intercalado, a fim de se tornar a chave mediana para esse nó

Nessas operações 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:

 
Figura 1: Remoção da chave 8 e posterior reorganização da estrutura
 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

editar

Busca

editar

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))
        }
    }
}

Algoritmo de Busca em Java

editar 
public BNodePosition<T> search(T element) {
	return searchAux(root, element);
}

private BNodePosition<T> searchAux(BNode<T> node, T element) {
	int i = 0;
	BNodePosition<T> nodePosition = new BNodePosition<T>();
	while (i <= node.elements.size() && element.compareTo(node.elements.get(i)) > 0) {
		i++;
	}
	if (i <= node.elements.size() && element.equals(node.elements.get(i))) {
		nodePosition.position = i;
		nodePosition.node = node;
		return nodePosition;
	}
	if (node.isLeaf()) {
		return new BNodePosition<T>();
	}
	return searchAux(node.children.get(i), element);
}

Inserção

editar

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)
     }
}

Inserção Recursiva.

editar 
public void insertRec(BNode<T> node, T element) {
		if (node.isLeaf()) {
			node.addElement(element);
			if (node.elements.size() > node.getMaxKeys()) {
				node.split();
			}
		} else {
			int position = searchPositionInParent(node.getElements(), element);
			insertRec(node.getChildren().get(position), element);
		}
	}

Busque a chave k
Busque a menor chave M na página folha da sub-árvore à direita de k
Se a chave k não está numa folha
{
    Substitua k por M
}

Apague a chave k ou M da página folha
Se a página folha não sofrer underflow
{
    fim do algoritmo
}
Se a página folha sofrer underflow, verifique as páginas irmãs da página folha
{
    Se uma das páginas tiver um número maior do que o mínimo redistribua as chaves
    Senão concatene as páginas com uma de suas irmãs e a chave pai separadora
}
Se ocorrer concatenação de páginas
{ 
    aplique o trecho das linhas 8 até 17 para a página pai da folha
}

	// insert abordagem top-down
	public void insert(BNode<T> node, T element) {
		if(node.isFull()) {
			node = split(node); // Troque a referencia para o novo node.
			// split retorna a referencia do no que contem a mediana do no anterior.
		}
		if(node.isLeaf()) {
			node.addElement(element);
			this.size ++;
		} else {
	 	        int i = 0;
			while (i < node.size() && node.getElementAt(i).compareTo(element) < 0) {
				i ++;
			}

			insert(node.getChildren().get(i), element);
		}	
	}

Remoção

editar

Algoritmo split em Java

editar 
 protected void split() {
         int mediana = (size()) / 2;

         BNode<T> leftChildren = this.copyLeftChildren(mediana);
         BNode<T> rightChildren = this.copyRightChildren(mediana);

         if (parent == null) {
             parent = new BNode<T>(maxChildren);
             parent.children.addFirst(this);
         }

         BNode<T> parent = this.parent;

         int index = parent.indexOfChild(this);
        parent.removeChild(this);

         parent.addChild(index, leftChildren);
         parent.addChild(index + 1, rightChildren);

         leftChildren.setParent(parent);
         rightChildren.setParent(parent);

         this.promote(mediana);

         if (parent.size() >= maxChildren) {
             parent.split();
         }
     }
     protected void promote(int mid) {
         T element = elements.get(mid);
         this.parent.addElement(element);
     }

Imprimir em Ordem em C

editar 
void emOrdem (tpaginaB raiz) {
    if(raiz==NULL)
        return;
 
    for(int i=0;i<raiz.n,i++){
        emOrdem(raiz→pont[i]);
        printf("%i",raiz→chv[i]);
    }
    emOrdem(raiz→pont[raiz.n]);
}

Algoritmo Split dentro da Classe Node em Java 

protected void split() {
		T mediana = this.getElementAt(elements.size() / 2);

		int posicao, esquerda, direita;

		BNode<T> maior = new BNode<>(this.getMaxChildren());
		BNode<T> menor = new BNode<>(this.getMaxChildren());

		LinkedList<BNode<T>> criancas = new LinkedList<BNode<T>>();

		this.armazenaElementos(mediana, maior, menor);

		if (this.getParent() == null && this.isLeaf()) {

			this.setElements(new LinkedList<T>());
			this.addElement(mediana);
			this.addChild(0, menor);
			this.addChild(1, maior);
		}

		else if (this.getParent() == null && !isLeaf()) {
			criancas = this.getChildren();

			this.setElements(new LinkedList<T>());
			this.addElement(mediana);

			this.setChildren(new LinkedList<BNode<T>>());
			this.addChild(0, menor);
			this.addChild(1, maior);

			this.reajustaFilhos(criancas, menor, 0, menor.size() + 1);
			this.reajustaFilhos(criancas, maior, maior.size() + 1, criancas.size());
		}

		else if (this.isLeaf()) {
			BNode<T> promote = new BNode<>(this.getMaxChildren());

			promote.getElements().add(mediana);
			promote.parent = this.getParent();

			menor.parent = this.getParent();
			maior.parent = this.getParent();

			posicao = buscaPosicaoNoPai(promote.getParent().getElements(), mediana);
			esquerda = posicao;
			direita = posicao + 1;

			this.getParent().getChildren().set(esquerda, menor);
			this.getParent().getChildren().add(direita, maior);
			promote.promote();
		}

		else {
			criancas = this.getChildren();

			BNode<T> paraPromote = new BNode<>(this.getMaxChildren());
			paraPromote.getElements().add(mediana);
			paraPromote.parent = this.getParent();

			menor.parent = this.getParent();
			maior.parent = this.getParent();

			posicao = buscaPosicaoNoPai(paraPromote.getElements(), mediana);
			esquerda = posicao;
			direita = posicao + 1;

			this.getParent().getChildren().add(esquerda, menor);
			this.getParent().getChildren().add(direita, maior);
		}
	}

Árvores 2-3-4

editar
 
Representação genérica de árvore B com três chaves e, consequentemente, quatro filhos.
 
Árvore preta e vermelha resultante de uma transformação de uma árvore B.

Árvores 2-3-4 são um tipo de árvore B que possuem uma, duas ou três chaves. E, consequentemente, dois, três ou quatro filhos. São utilizadas na implementação de dicionários.[6] Além disso, servem como base para o desenvolvimento do código de árvores preto e vermelho.[7]

Existem três situações na mudança de árvore B para árvore rubro-negra:

  • Caso o nó só possua uma chave, basta transformá-lo num nó de cor preta e ligá-lo aos seus filhos correspondentes.
  • Caso o nó possua duas chaves, a chave mais à esquerda será transformada num nó preto e a mais à direita, num nó vermelho. O nó preto terá como filho da esquerda o primeiro nó filho da antiga árvore e como filho da direita o novo nó vermelho. Este, por sua vez, terá como filhos os dois filhos restantes da lista de filhos da árvore original.
  • Caso o nó possua três chaves, a chave do meio será transformada num nó vermelho e terá como filhos as antigas chaves adjacentes que serão nós pretos com os antigos filhos da árvore B.

Aplicando essas situações, deve-se checar se as propriedades de árvores rubro-negra são mantidas como o valor do nó da esquerda ser menor que o nó atual.

Variações

editar

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 é possível 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 redistribuiçã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

editar

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

  • Árvores B+:
    1. 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 .[8]
    2. 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.[8]
  • Árvores B*:
    1. 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%.[3]

Em sistema de arquivos

editar

Além de sua utilização em bancos de dados, uma Árvore B (ou uma variante) também é usada em sistemas de arquivos para permitir acesso aleatório rápido a um bloco arbitrário em um arquivo particular. O problema básico consiste em transformar o bloco de arquivos   em um endereço de bloco de disco (ou talvez para um cilindro-cabeça-sector).

O sistema de arquivos da Apple HFS+, NTFS da Microsoft,[9] AIX (JFS2) e alguns sistemas de arquivos Linux, como btrfs e Ext4, usam árvores B.

Árvores B* são usadas nos sistemas de arquivos HFS e Reiser4.


Ver também

editar
 
Wikilivros

Referências

  1. ↑ Comer, Douglas (Junho de 1979). «The Ubiquitous B-Tree». Computing Surveys. 11 (2): 123–137. doi:10.1145/356770.356776 
  2. ↑ a b c Bayer, R.; McCreight, E. (1972). «Organization and Maintenance of Large Ordered Indexes» (PDF). Acta Informatica. 1: 173-189 
  3. ↑ a b Comer, Douglas (1979). «The Ubiquitous B-Tree». Computing Surveys. 11: 123–137. ISSN 0360-0300. doi:10.1145/356770.356776 
  4. ↑ a b Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 363 
  5. ↑ a b Knuth, Donald (1998). The Art of Computer Programming. Sorting and Searching (em inglês). 3 2 ed. [S.l.]: Addison-Wesley 
  6. ↑ «Dicionário de dados». Wikipédia, a enciclopédia livre. 14 de fevereiro de 2017 
  7. ↑ Sedgewick, Robert. «Left-leaning Red-Black Trees» 
  8. ↑ a b Folk, Michael; Zoellick, Bill (1992). File Structures (em inglês) 2 ed. [S.l.]: Addison-Wesley. p. 433 
  9. ↑ Mark Russinovich. «Inside Win2K NTFS, Part 1». Microsoft Developer Network. Consultado em 18 de Abril de 2008. Cópia arquivada em 13 de Abril de 2008 

Bibliografia

editar
  • 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

editar
Obtida de "https://pt.wikipedia.org/w/index.php?title=Árvore_B&oldid=67387203"