teste

Árvores B

Prof. Flávio Humberto Cabral Nunes

Conteúdo
1.
2.
3.
4.
5.
6.

Introdução
Busca
Inserção
Remoção
B*
B+
Capítulo: 8 (APOSTILA).

Introdução
Em muitas aplicações, a tabela considerada é muito grande
–

As chaves não podem ser mantidas todas na memória principal

Assim, a tabela precisa ser mantida em memória secundária
–

Alto custo de acesso

Introdução
Necessidade de uma estrutura que minimize o tempo de acesso na tabela para
–
–
–

Buscas
Inserções
Remoções

Árvores B
As árvores B permitem manter mais de uma chave em cada nó da estrutura
Proporciona uma organização de ponteiros de forma que as operações são executadas rapidamente Sua construção assegura que todas as folhas se encontram no mesmo nível, não importando a ordem de entrada dos dados

Árvores B
Largamente utilizadas como forma de armazenamento em memória secundária
Diversos sistemas comerciais de banco de dados utilizam árvores B

Definição
Todo nó x tem os seguintes campos
–

–

–

n[x]: número de chaves atualmente armazenadas no nó x
N[x] chaves de modo que chave1 chave2 ... chaven[x] folha[x]: booleano indicando se o nó x é folha ou não

Definição
Cada nó interno contém n[x] + 1 ponteiros c1[x], c2[x], ..., cn[x]+1[x] para seus filhos
Nós folhas não têm filhos
–

Campos ci são indefinidos

As chaves chavei[x] separam os intervalos de chaves armazenadas em cada sub-árvore
–
–

Se ki é qualquer chave na sub-árvore k1 chave1[x] k2 chave2[x] ... chaven[x][x] kn[x]+1 Definição
Toda folha tem a mesma altura
O número de chaves em cada nó é limitado
–
–
–

Mínimo: m chaves
Máximo: 2m chaves m 2, exceto para raíz onde m pode ser 1

Representação de Uma Página
Número de chaves

n p1 k1 dados r1 p2 k2 dados r2 . . . p2m k2m dados r2m p2m+1

k1 dados

k2 dados

k2m dados

Representação Simplificada

k1 p1 k2 p2 ..... p3 k2m

p2m

P2m + 1

Exemplo
22 58