ArvoreB inserir

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Inserção na Árvore B
Prof. Rafael de Santiago, MSc
Objetivo
Compreender o funcionamento do método de inserção em uma árvore B.
Introdução
HISTÓRICO
Nunca foi explicada a origem pelos autores R. Bayer e E. McCreight.
Trabalho desenvolvido no 
Boeing Scientific Research Labs.
Introdução
Antes de começar a descobrir como ocorrem inserções em árvores B, precisamos entender alguns aspectos fundamentais deste tipo de árvore.
Introdução
É uma árvore n-ária
Trabalhamos com páginas e registros
Trabalhamos com a ordem “m” 
no mínimo “m” registros por página
no máximo 2 x “m” por página
cada página deve ter no mínimo m + 1 descendentes
cada página deve ter no máximo 2 x “m” + 1 descendentes
Introdução
Quando uma inserção supera o número de 2m registros
deve-se dividir a página em 2 e sobe-se o valor no meio da página, para a página superior
40, 50, 60, 70
m=2
81
Introdução
Quando uma inserção supera o número de 2m registros
deve-se dividir a página em 2 e sobe-se o valor no meio da página, para a página superior
40, 50, 60, 70, 81
m=2
Violação
Introdução
Quando uma inserção supera o número de 2m registros
deve-se dividir a página em 2 e sobe-se o valor no meio da página, para a página superior
40, 50, 60, 70, 81
m=2
Sobe-se o valor do meio
Introdução
Quando uma inserção supera o número de 2m registros
deve-se dividir a página em 2 e sobe-se o valor no meio da página, para a página superior
40, 50
m=2
60
70, 81
Execução
Execução
A raiz é a única página que não é alvo de restrições de quantidade mínima
Execução
20
Execução
10, 20
Execução
10, 20, 40
Execução
10, 20, 30, 40
Execução
10, 20, 30, 40
50
Execução
10, 20, 30, 40
50
Ao inserir o 50 houve uma violação
Execução
10, 20, 30, 40, 50
Imagina-se a inserção e pega o valor do meio 
Execução
30
Criam-se duas páginas e divide-se os registros.
10, 20
40, 50
Execução
30
3, 10, 20
40, 50
Execução
30
3, 4, 10, 20
40, 50
Execução
30
3, 4, 10, 20
40, 50
11
Ao inserir o valor 11, há uma violação
Execução
30
3, 4, 10, 11, 20
40, 50
O valor do centro vai ser a nova raiz
Execução
30
3, 4
40, 50
Dividi-se a página 
10
11, 20
Execução
10, 30
3, 4
40, 50
Acomoda-se a nova raiz das páginas divididas
11, 20
Execução
10, 30
3, 4
40, 50
11, 13, 20
Execução
10, 30
3, 4
40, 50
11, 13, 20
25
Inserindo 25, não há violação
Execução
10, 30
3, 4
40, 50
11, 13, 20, 25
Execução
10, 30
3, 4
40, 50
11, 13, 20, 25
28
Inserindo 28, 
há violação
Execução
10, 30
3, 4
40, 50
11, 13, 20, 25, 28
O valor do centro vai ser a nova raiz
Execução
10, 30
3, 4
40, 50
11, 13
Dividi-se a página
20
25, 28
Execução
10, 20, 30
3, 4
40, 50
11, 13
25, 28
Acomoda-se a nova raiz das páginas divididas
Execução
10, 20, 30
3, 4
40, 50
11, 13
25, 28
17
Execução
10, 20, 30
3, 4
40, 50
11, 13, 17
25, 28
Execução
10, 20, 30
3, 4
40, 50
11, 13, 17
25, 28
55
Execução
10, 20, 30
3, 4
40, 50, 55
11, 13, 17
25, 28
Execução
10, 20, 30
3, 4
40, 50, 55
11, 13, 17
25, 28
52
Execução
10, 20, 30
3, 4
40, 50, 52, 55
11, 13, 17
25, 28
Execução
10, 20, 30
3, 4
40, 50, 52, 55
11, 13, 17
25, 28
36
Execução
10, 20, 30
3, 4
36, 40, 50, 52, 55
11, 13, 17
25, 28
Execução
10, 20, 30
3, 4
36, 40
11, 13, 17
25, 28
50
52, 55
Execução
10, 20, 30, 50
3, 4
36, 40
11, 13, 17
25, 28
52, 55
Execução
10, 20, 30, 50
3, 4
36, 40
11, 13, 17
25, 28
52, 55
33
Execução
10, 20, 30, 50
3, 4
33, 36, 40
11, 13, 17
25, 28
52, 55
Execução
10, 20, 30, 50
3, 4
33, 36, 40
11, 13, 17
25, 28
52, 55
48
Execução
10, 20, 30, 50
3, 4
33, 36, 40, 48
11, 13, 17
25, 28
52, 55
Execução
10, 20, 30, 50
3, 4
33, 36, 40, 48
11, 13, 17
25, 28
52, 55
43
Execução
10, 20, 30, 50
3, 4
33, 36, 40, 43, 48
11, 13, 17
25, 28
52, 55
Execução
10, 20, 30, 50
3, 4
33, 36
11, 13, 17
25, 28
52, 55
43, 48
40
Execução
10, 20, 30, 40, 50
3, 4
33, 36
11, 13, 17
25, 28
52, 55
43, 48
Execução
10, 20
3, 4
33, 36
11, 13, 17
25, 28
52, 55
43, 48
30
40, 50
Execução
10, 20
3, 4
33, 36
11, 13, 17
25, 28
52, 55
43, 48
40, 50
30
Execução
10, 20
3, 4
33, 36
11, 13, 17
25, 28
52, 55
43, 48
40, 50
30
PRONTO!!!