Árvores B

Árvore B

Motivações para implementação de árvores B. Manter mais de uma chave em cada nó. Manter todas as folhas no mesmo nível Como cada nó agora terá mais de uma chave haverá uma economia de tempo. A estrutura da árvore B será sempre regular, já que, todas as folhas serão mantidas no mesmo nível. Regras: Seja d um número natural, uma árvore B de ordem d é um árvore ordenada  que satisfaz as seguintes propriedades: se a raiz não é uma folha, possui no mínimo 2 filhos. cada nó interno diferente da raiz possui no mínimo d+1 filhos. d controla o número de filhos. cada nó possui no máximo 2d+1 filhos. todas as folhas estão no mesmo nível.

Nomenclatura Os nós da árvore B são chamados de páginas. Cada página armazena diversas chaves.   se uma página P não folha possui m chaves então P possui m+1 filhas. a raiz possui entre 1 e 2d chaves cada página diferente da raiz possui entre d e 2d chaves. em cada página P com m chaves, as chaves estão ordenadas: s1 < s2 < s3 < ... < sm P contém m+1 ponteiros  p0, p1, p2 , ... , pm apontando para os seus filhos ( nas folhas estes ponteiros são indicados por lambda).  

Exemplificação

T[0] é um ponteiro que irá apontar para um filho maior que a chave 50 e T[ 1 ] será o ponteiro que aponta para valores maiores que 50. Perguntas: Qual o número máximo de páginas que uma árvore B de ordem d e altura h pode conter?   Qual o número máximo de chaves que uma árvore B de ordem d e altura h pode conter?   Qual o número mínimo de páginas e chaves que uma árvore B de ordem d e altura h podem ter?

Manipulação de Árvores B

Busca de uma chave em uma árvore B Seja s a chave procurada Inicialmente, percorremos a lista de chaves ordenadas na página-raiz. Se s for encontrada, o processo termina Caso contrário, continua-se a busca na página filha apontada pelo ponteiro adequado Se s<s1 ( usar p0), se si < s < s i+1  ( 1 <= i <= m-1 ), se s > sm usar pm. Repete-se a busca na página filha, e assim por diante: se s seja encontrada. ou atinja-se um ponteiro nulo. A busca faz um percurso de páginas e chaves fazendo a escolha ideal do ponteiro.

Inserção de uma chave em uma árvore B Seja s a chave a ser inserida Inicialmente, fazemos a busca da chave s na árvore B. Se s for encontrada, nada a fazer ( pois nesse caso a inserção seria inválida). Se s não for encontrada, insere-se s na página folha onde a busca se encerrou, mantendo a ordenação correta da lista de chaves. Se eventualmente a página folha contem mais de 2d chaves, é preciso efetuar sua cisão. Dividi-la em duas novas chaves. Verificar esse método de inserção.

Remoção de uma chave em uma árvore B Seja s a chave a ser removida. Inicialmente. fazemos a busca da chave s na árvore B. Se s não for encontrada, nada a fazer ( pois nesse caso a remoção seria inválida) Se s for encontrada numa folha, remova-a Se s for encontrada numa página não-folha, remova-a e coloque no seu lugar a chave x imediatamente maior que s ( x sempre se encontra numa folha ). A remoção se restringe portanto sempre a uma página  folha. Sa a página-folha P onde foi realizada a remoção ficou com menos do que d chaves, é preciso fazer concatenação ou redistribuição. Vejamos em que casos aplicamos concatenação ou redistribuição. Concatenação  - Mas a raiz não tem de ter no mínimo 2 filhos. Redistribuição; Toda remoção restringe-se no caso de P folha.

fonte: http://videoaula.rnp.br/v.php?f=/cederj/sistemas_comp/ead05007/Aula_027/Aula_027.xml