Mostrar código-fonte de Árvore B

{{Infocaixa estrutura de dados
|nome=Árvore B
|tipo=Árvore
|inventado_por=[[Rudolf Bayer]], [[Edward Meyers McCreight]]
|ano=1971
|
|espaco_med= O(''n'')
|espaco_pior= O(''n'')
|busca_med= O(log ''n'')
|busca_pior= O(log ''n'')
|insert_med= O(log ''n'')
|insert_pior= O(log ''n'')
|delete_med= O(log ''n'')
|delete_pior= O(log ''n'')
}}

[[Imagem:B-tree-definition.png|thumb|400px|direita|Exemplo de Árvore B]]

Em [[ciência da computação]], uma '''árvore B''' é uma [[Árvore (estrutura de dados)|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 binária de busca|árvore de pesquisa binária]] em que um nó pode ter mais que dois filhos.<ref name="Comer">{{citar periódico|último1 =Comer|primeiro1 =Douglas|título=The Ubiquitous B-Tree|periódico=Computing Surveys|data=Junho de 1979|volume=11|número=2|página=123–137|doi=10.1145/356770.356776}}</ref> Diferente das [[Árvore binária de busca balanceada|á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.

É normalmente usada em [[Banco de dados|bancos de dados]] e [[Sistema de arquivos|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 [[Sistema de arquivos|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 ==
[[Imagem:B-tree.svg|thumb|400px|direita|Á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 ==

=== Nó ou página ===
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<math>\lfloor5/2\rfloor</math> 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,<ref name="bayer" /> Comer,<ref name="comer" /> 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.<ref name="ambiguidade" /> Por exemplo, se uma '''árvore B''' é de ordem 3, uma página estará cheia quando tiver 6 ou 7 chaves<ref name="ambiguidade" />? 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?<ref name="bayer" />

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.<ref name="knuth"/>

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.<ref name="bayer"/> 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.<ref name="knuth"/>

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]]:
<syntaxhighlight lang = "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;

</syntaxhighlight>

== Operações básicas ==
[[Imagem:B tree insertion example.png|thumb|direita|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 ===
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 ===
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:
# '''''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.
## 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.
## 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).
## 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 ====
[[Ficheiro:Split gif.gif|miniaturadaimagem|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 <code>tamanho = quantidade</code> de elementos no nó, <code>mediana = tamanho/2</code> e usamos a mediana para acessar o elemento que se encontra no centro do nó, no caso <code>valor_central = valores[mediana]</code>;
* É testado se o nó que sofreu split tem pai, caso não, cria-se um novo nó apenas com o valor <code>valor_central</code> 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 <code>valor_central</code> e ficará na primeira posição dos filhos da nova raiz, e o outro nó terá os valores maiores que o <code>valor_central</code> e ficará na segunda posição dos filhos da nova raiz;
* Caso o nó tenha pai, adicionamos o <code>valor_central</code> 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 <code>valor_central</code>. O nó com os menores valores ficará posicionado como filho do lado esquerdo do <code>valor_central</code> e o nó com os maiores valores ficará posicionado como filho do lado direito do <code>valor_central</code>. Por exemplo: Caso o <code>valor_central</code> 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 ===

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:
# Se a chave k está no nó x e x é uma folha, elimine a chave k de x.
# Se a chave k está no nó x e x é um nó interno:
## 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.
## 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.
## 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.
# 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:
## 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]
## 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:

{| class="wikitable"
|-
| [[Imagem:Delete-key-from-Btree-1.png|thumb|239x239px|centro|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.
|-
|[[Imagem:Delete-key-from-Btree-2.png|thumb|233x233px|centro|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.
|-
| [[Imagem:Delete-key-from-Btree-3.png|thumb|245x245px|centro|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.
|-
| [[Imagem:Delete-key-from-Btree-5.png|thumb|245x245px|centro|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.
|-
| [[Imagem:Delete-key-from-Btree-4.png|thumb|256x256px|centro|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.
<syntaxhighlight lang="text">
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))
        }
    }
}
</syntaxhighlight>
==== Algoritmo de Busca em Java  ====
<syntaxhighlight lang="java">
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);
}
</syntaxhighlight>

=== 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.
<syntaxhighlight lang="text">
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)
     }
}
</syntaxhighlight>

==== Inserção Recursiva. ====
<syntaxhighlight lang="java">
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);
		}
	}
</syntaxhighlight><syntaxhighlight lang="text">
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
}
</syntaxhighlight>

<syntaxhighlight lang="java">
	// 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);
		}	
	}
</syntaxhighlight>

=== Remoção ===
=== Algoritmo  split em Java ===
<syntaxhighlight lang="java">
 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);
     }
</syntaxhighlight>

=== Imprimir em Ordem em C ===
<syntaxhighlight lang="text">
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]);
}

</syntaxhighlight>

'''<big>Algoritmo Split dentro da Classe Node em Java</big>''' <syntaxhighlight lang="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);
		}
	}
</syntaxhighlight>

== Árvores 2-3-4 ==
[[Imagem:Árvore B.png|thumb|Representação genérica de árvore B com três chaves e, consequentemente, quatro filhos.|190x190px]]
[[Imagem:Árvore preta e vermelha.png|thumb|Árvore preta e vermelha resultante de uma transformação de uma árvore B.|186x186px]]

Á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. Além disso, servem como base para o desenvolvimento do código de [[Árvore rubro-negra|árvores preto e vermelho]].<ref>{{citar periódico|ultimo=Sedgewick|primeiro=Robert|data=|titulo=Left-leaning Red-Black Trees|jornal=|doi=|url=|acessadoem=}}</ref>

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 ==
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.
* [[Árvore B*|Á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 ==
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''' .<ref name="arvoreb+"/>
*# 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.<ref name="arvoreb+"/>

* [[Árvore B*|Á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%.<ref name="comer"/>

==Em sistema de arquivos==

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 <math>i</math> em um endereço de bloco de disco (ou talvez para um [[CHS|cilindro-cabeça-sector]]).

O sistema de arquivos da Apple [[HFS+]], [[NTFS]] da Microsoft,<ref name="insidewin2kntfs" /> AIX ([[JFS|JFS2]]) e alguns sistemas de arquivos [[Linux]], como [[btrfs]] e [[Ext4]], usam árvores B.

Árvores B<sup>*</sup> são usadas nos [[Sistema de arquivos|sistemas de arquivos]] [[Hierarchical File System|HFS]] e [[Reiser4]].


== Ver também ==
{{Wikilivros|Algoritmos e Estruturas de Dados|Árvores B}}
* [[Árvore de busca binária]]
* [[Árvore binária]]
* [[Árvore B+]]
* [[Árvore B*]]
* [[Árvore AVL]]

{{Referências|col=2|refs =

<ref name="insidewin2kntfs">
{{citar web
 | url = http://msdn2.microsoft.com/en-us/library/ms995846.aspx
 | titulo = Inside Win2K NTFS, Part 1
 | autor = [[Mark Russinovich]]
 | publicado = [[MSDN|Microsoft Developer Network]]
 | acessodata = 18 de Abril de 2008
 | arquivourl = https://web.archive.org/web/20080413181940/http://msdn2.microsoft.com/en-us/library/ms995846.aspx
 | arquivodata= 13 de Abril de 2008 <!--DASHBot-->
 |urlmorta= não}}
</ref>

<ref name="bayer">
{{citar periódico
| ultimo = Bayer
 | primeiro = R.
 | coautores = McCreight, E.
 | titulo = Organization and Maintenance of Large Ordered Indexes
 |jornal = Acta Informatica
 | volume = 1
 | numero =
 | páginas = 173-189
 | editora =
 |ano= 1972
 | issn =
 | url = http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf
}}</ref>
<ref name="comer">
{{citar periódico
| ultimo = Comer
 | primeiro = Douglas
 | ano = 1979
 | mes = Junho
 | titulo = The Ubiquitous B-Tree
 | jornal = Computing Surveys
 | volume = 11
 | paginas = 123–137
 | issn = 0360-0300
 | doi = 10.1145/356770.356776
}}</ref>
<ref name="ambiguidade">
{{citar livro
|sobrenome= Folk
|nome= Michael
|coautor= Zoellick, Bill
|título= File Structures
|idioma= inglês
|edição= 2
|editora= Addison-Wesley
|ano= 1992
|página= 363
}}</ref>
<ref name="arvoreb+">
{{citar livro
|sobrenome= Folk
|nome= Michael
|coautor= Zoellick, Bill
|título= File Structures
|idioma= inglês
|edição= 2
|editora= Addison-Wesley
|ano= 1992
|página= 433
}}</ref>
<ref name="knuth">
{{citar livro
|sobrenome= Knuth
|nome= Donald
|título= The Art of Computer Programming
|subtítulo= Sorting and Searching
|idioma= inglês
|edição= 2
|editora= Addison-Wesley
|volume= 3
|ano= 1998
}}</ref>
}}

== Bibliografia ==
* {{Citar livro
|sobrenome= Cormen
|nome= Thomas
|autorlink =
|autor2= Leiserson, Charles
|autor3= Rivest, Ronald
|autor4= Stein, Clifford
|título= Introduction to Algorithms
|subtítulo =
|idioma= inglês
|edição= 2
|local =
|editora= MIT Press and McGraw-Hill
|editor =
|ano= 2001
|páginas =
|página =
|capítulo= 18
|volume =
|coleção =
|isbn= 0-262-03293-7
|ref= cormen}}

* {{Citar livro
|sobrenome= Folk
|nome= Michael
|coautor= Zoellick, Bill
|título= File Structures
|idioma= inglês
|edição= 2
|páginas= 590
|editora= Addison-Wesley
|ano= 1992
|isbn= 0-201-55713-4
|ref= folk
 }}

* {{citar livro
|sobrenome= Knuth
|nome= Donald
|título= The Art of Computer Programming
|subtítulo= Sorting and Searching
|idioma= inglês
|edição= 2
|editora= Addison-Wesley
|volume= 3
|ano= 1998
|isbn= 0-201-89685-0
}}

== Ligações externas ==
* [http://slady.net/java/bt/view.php Applet de uma árvore B segundo a definição de Bayer & McCreight (1972)]
* [https://web.archive.org/web/20120626143441/http://ats.oka.nu/b-tree/b-tree.manual.html Animação em Flash de uma árvore B]
* [https://web.archive.org/web/20120223163741/http://groups.engin.umd.umich.edu/CIS/course.des/cis350/treetool/ Applet de uma árvore B, árvore AVL, árvore binária]
* [http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html Código em C++ de uma árvore B]
* [https://web.archive.org/web/20170331115357/http://www.inf.ufrgs.br/~pmdusso/works/Relatorio_CPD_Disk_Guru.htm Aplicação em MS Visual C# que implementa um árvore B orientada a objetos]
*[https://www.cs.usfca.edu/~galles/visualization/BTree.html Visualizador de árvores B pelo departamento de Ciência da Computação da Universidade de São Francisco]
{{Estrutura de dados}}
{{Árvores (estrutura de dados)|uncollapsed}}
{{DEFAULTSORT:Arvore B}}
[[Categoria:Estruturas de dados]]