Árvores-B: Estruturas de Dados

Prévia do material em texto

Árvore-B 
 
 
Wirth, N. Algoritmos e Estruturas de Dados, Prentice 
Hall, 1986. 
 
Cormen, T.H.; Leiserson, C. E. Rivest, R. L. Stein, C. 
Algoritmos: Teoria e Prática. 2a. ed. Editora Campus, 
2002 (Caps. 18) 
2 
Árvore de Multivias 
Árvore de multivias T de ordem n: 
 
(1) É uma árvore em que cada nó possui n ou menos sub-árvores 
e contém uma chave a menos do que o número sub-árvores. 
 
(2) Se T1,T2,…,Tm são m sub-árvores de um nó, este contém m-1 
chaves k1,k2,…,km-1 em ordem ascendente (descendente), 
k1≤k2 ≤ … ≤ km-1. 
12 50 85 
6 10 37 100 120 150 60 70 80 
25 62 65 69 110 
Árvore de Multivias 
de ordem 4 
3 
Árvore - B 
Árvore – B: Árvore de pesquisa balanceada projetada com 
objetivos: 
(1) Indexação em grandes índices para armazenamento em 
memória secundária 
(2) manter a árvore balanceada após operações de inserção e de 
remoção 
(3) Utilizar melhor espaço dentro de um nó, 
 à custa de maior complexidade nos algoritmos de inserção e 
deleção 
 
 Introduzida por 
R. Bayer e E. McCreight: “Organization and Maintenance of 
Large Ordered Indexes”, Acta Informatica, 1(3), Feb 1972 
4 
Árvore - B 
Árvore B de ordem n: É uma árvore de multivias de ordem n que 
satisfaz as seguintes condições: 
(1) Todo nó possui n ou menos sub-árvores (árv. multivias) 
 
(2) Todo nó, exceto a raiz, possui ou mais sub-árvores 
 
(3) A raiz possui, no mínimo, duas sub-árvores não vazias, exceto 
no caso em que é uma folha 
 
(4) Todas as folhas estão no mesmo nível (e todas as suas sub-
árvores são vazias) 
 
(5) Um nó com k sub-árvores armazena k-1 registros (árv. multivias) 
 
(6) Todo os nós de derivação (não-folhas) possuem exclusivamente 
sub-árvores não vazias 






2
n
5 
Exemplo de uma Árvore B – Ordem 4 
P 
D M 
T 
A B C 
G I 
N U W 
R S 
6 
Exemplo Árvore – B (cont.) 
Ordem # sub-arv. 
Raiz 
# sub-arv. 
Outros nós 
# elem. 
Raiz 
#elem. 
Outros nós 
3 2..3 2..3 1..2 1..2 
4 2..4 2..4 1..3 1..3 
5 2..5 3..5 1..4 2..4 
Tamanho de um nó (sua ordem) é escolhido para 
preencher um bloco do disco 
Árvore-B é uma generalização de árvore 2-3, i.e, árvore 2-3 
é uma árvore-B de ordem 3 
7 
Altura de uma Árvore - B 
O número de acessos a disco requeridos 
nas operações em uma árvore-B é 
proporcional a altura da árvore 
 
 1.000 
 1.000 1.000 1.000 
 1.000 1.000 1.000 
1 nó, 1.000 chaves 
1.001 nós, 1.001.000 chaves 
1.002.001 nós, 1.002.001.000 chaves 
Árvore-B de ordem 
1.001 e altura 2 
Árvore-B de ordem 
1.001 e altura 2 
Mais de um bilhão de 
chaves 
8 
Representação: Estrutura encadeada - 
alocação dinâmica 
Estrutura da Árvore-B de ordem n: ponteiro para um nó 
Nó - composto por: 
(1) Vetores [1..q-1..n-1] de chaves de pesquisa 
(2) Vetores [1..q..n] de ponteiros para as sub-árvores 
(3) contador: [q-1]: número de chaves no nó 
Árvore-B: ponteiro tipono 
tipono: contador: inteiro 
 K[1..n-1]: tipochave 
 P[1..n]: ponteiro tipono 
 
 
 
9 
Exemplo da Representação 
10 20 
5 7 12 30 
cnt k1 k2 p1 p2 p3 
1 12 -1 -1 
Árvore-B: ponteiro tipono 
tipono: contador: inteiro 
 K[1..n-1]: tipochave 
 P[1..n]: ponteiro tipono 
 
 
 
Árvore-B ordem 3 
10 
Operações Básicas 
 Busca 
 
 Inserção 
 
 Remoção 
11 
Algoritmo Busca em Árvore B 
Algoritmo BuscaArvoreB (k, v) 
 se v = nulo 
 então imprimir(“chave não existe”) 
 senão i ← 1; eqto (i ≤ cnt ˄ v.K[i] < k ) i ← i + 1 
 se (i ≤ cnt ˄ k = v.K[i]) 
 então return(v,i) 
 senão BuscaArvoreB(k, v.P[i]) 
 
12 
Busca em uma Árvore-B 
•Problema 1: Buscar L 
•Problema 2: Buscar S 
P 
D M 
T 
A B C 
G I 
N U W 
R S 
Busca retorna um ponteiro x para um nó com chave 
k se existir algum senão retorna NULL 
13 
Inserção em Árvore - B 
Inserção em Árvore-B: 
(1) Pesquisa o registro com chave k 
(2) Caso não se encontre 
(1) Inserir x na folha 
(2) Se o nó NÃO excedeu o limite → FIM 
(3) Senão (overflow) o nó é dividido em 2 e o nó 
pai tem que acomodar o registro excedente 
(4) Se o pai tb. estiver cheio então o processo de 
divisão é aplicado novamente 
(5) No pior caso, propaga-se até a raiz da árvore 
e ela aumenta sua altura com a divisão da 
raiz 
 
14 
Inserção em Árvore – B - Exemplo 
Árvore-B de ordem 3. 
Inserção: 10 20 5; 7 12 30; 15 40 17 
10 10 20 5 10 20 
10 
 5 20 
10 
 5 7 20 
10 
 5 7 12 20 
10 
 5 7 12 20 30 
10 20 
 5 7 12 30 
10 20 
 5 7 12 15 30 
10 20 
 5 7 12 15 30 40 
15 
Inserção em Árvore – B – Exemplo (cont.) 
Árvore-B de ordem 3. 
Inserção: 10 20 5; 7 12 30; 15 40 17 
10 20 
 5 7 12 15 30 40 
10 20 
 5 7 12 15 17 30 40 
10 15 20 
 5 7 12 30 40 17 
10 
 5 7 12 30 40 17 
20 
15 
16 
Notação da Árvore-B 
Notação da árvore-B em níveis 
{[(15)] [(10) (20)] [(5, 7) (12) (17) (30,40)]} 
 
{} – árvore-B 
[] – nível 
() = nó 
10 
 5 7 12 30 40 17 
20 
15 
17 
Remoção em Árvore B 
Remoção em Árvore-B: 
(1) Eliminação normal: remoção de um item em um nó 
folha e esse permanece com o nro. mínimo de sub-
árvores 
(2) Eliminação com rotação: se a remoção de um item 
torna o nó com menos que a sua capacidade 
mínima, ocorre – 
(1) rotação à esquerda (com o máximo de sua sub-
árvore à esquerda) 
(2) rotação à direita (com o mínimo de sua sub-
árvore à direita) 
 
18 
Remoção em Árvore B 
Remoção em Árvore-B: 
(3) Remoção com aglutinação: (caso a remoção normal 
e com rotação não sejam possíveis). Nesse caso as 
sub-árvores à esquerda e à direita já estão com o 
nro. mínimo de elementos – 
 (3.1) aglutinação usando a sub-árvore da esquerda 
 (3.2) aglutinação usando a sub-árvore da direita 
 (3.3) o nó aglutinado é formado no nível inferior, e se 
ainda ficarem nós com menos que a capacidade 
mínima, aglutinações recursivas são necessárias 
podendo a árvore diminuir sua altura de um. 
 
 
19 
Remoção em Árvore – B – Exemplo 
Árvore-B de ordem 3. 
Remoção: 58 65 55 50 40 
30 
 10 40 65 55 58 
60 70 
50 
75 80 
30 
 10 40 65 55 
60 70 
50 
75 80 
30 
 10 40 70 55 
60 75 
50 
80 
30 
 10 40 60 70 
75 
50 
80 
20 
Remoção em Árvore – B – Exemplo 
Árvore-B de ordem 3. 
Remoção: 58 65 55 50 40 
30 
 10 40 60 70 
75 
50 
80 
30 
 10 40 70 
75 
60 
80 
 
 10 30 70 
75 
60 
80 
 10 30 70 
60 75 
80 
21 
Implementação 
Estrutura de Dados: 
 
#define ORDEM 5 
 
typedef struct no { 
 int cnt, chave[ORDEM-1]; 
 struct no *ptr[ORDEM]; 
 } no; 
 
no *raiz; 
22 
Exercícios 
1. Considere o seguinte grupo de chaves: (50) (80 10 60 20) 
(70 7 56 48 52) (57) 
a) Ilustre graficamente como fica uma árvore B de ordem 4 
após a inserção (na mesma seqüência) de cada grupo de 
chaves (um desenho após a inserção de cada grupo). 
b) Ilustre graficamente como fica a mesma árvore B após a 
remoção (nessa seqüência, e após a remoção de cada 
grupo) dos seguintes grupos de chaves (7) (70 57) (60) (52) 
 
2. Executar o programa btree.c para um conjunto de 
elementos escolhidos entre 1..1.000. Teste as operações de 
inclusão e exclusão de forma que ocorram ações de 
divisão e concatenação de páginas, bem como alteração 
da altura da árvore (aumento e diminuição). Mostrar os 
resultados das simulações realizadas.