Loading AI tools
Da Wikipédia, a enciclopédia livre
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 | |||||||||||||||||||||
| |||||||||||||||||||||
É 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.
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.
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:
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.
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.
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.
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;
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.
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.
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:
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.
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:
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];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;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.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:
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:
 |
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. |
 |
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. |
 |
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. |
 |
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. |
 |
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. |
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))
}
}
}
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);
}
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)
}
}
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);
}
}
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);
}
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 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:
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.
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.
Se compararmos as árvores B com suas variações podemos enumerar algumas características importantes para a escolha de implementação destas:
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
