Árvore B

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

Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
1
 
 
Árvore B+ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 35 Maria do Carmo F 
40 Ronildo Santos M 
05 10 15 20 25 30 35 40 45 50 55 60 65 70 
15 25 45 
 
65 
 
35 55 
Nó Raiz 
Nó Intermediário Nó Folha 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
2
Estrutura de uma Árvore B+ 
 
 
� Estrutura de um nó de uma Árvore B+ 
 
 
� Nó Folha 
o Um nó de uma árvore B+ pode conter até n-1 valores de chave de busca K1, K2, ... Kn-1 e n ponteiros. 
o Um nó folha deve conter, pelo menos, (n-1)/2 ponteiros. (n-1)/2 arredondado para cima, 
o As chaves, de cada nó, são mantidas em ordem crescente. Para i<j, Ki < Kj. 
o No nó folha o ponteiro Pi aponta para o um registro do arquivo com chave Pi. O ponteiro Pn, não aponta para registros do arquivo, 
mas é usado para encadear as chaves de busca em ordem crescente. 
� Nó Não-Folha 
o Os nós não-folha não apontam para registros do arquivo. Eles apontam para outros nós da árvore. 
o Devem manter n ponteiros deste que: n/2 >= Número de ponteiros <= n. n/2 deve ser arredondado para o primeiro inteiro maior. 
P1 K1 P2 K2 P3 K3 P4 K4 Pn-1 Kn-1 
 
Pn 
 
........ 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
3
o O ponteiro Pi aponta para a sub-árvore com chaves de busca menores que Ki e maiores que Ki-1. 
� Nó Raiz 
o O Nó raiz deve conter no mínimo 2 ponteiros, exceção feita para árvore com um único nó, ou com uma única chave de busca por 
nó. O número máximo de ponteiros é n; 
 
Consultas em Árvores B+. 
� Supor que queremos encontrar a chave de busca V. 
� Examinar um nó em busca da maior chave de busca menor que V, até alcançar um nó folha. 
� Se V coincidir com a chave Ki do nó folha, então o ponteiro Pi aponta para o registro desejado, do arquivo. Se não há no nó folha 
alcançado um Ki que coincida com V, então a chave não existe no arquivo. 
� Para K valores de chave de busca o caminho percorrido para encontra uma chave é <= logn/s K com n/2 arredondado para cima e o logn/2 
também. 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
4
Algoritmo de consulta em uma Árvore B+ 
Procedure Encontrar (V) 
 Faça C = Nó raiz 
 Enquanto C não é um nó folha 
Faça 
 Ki = menor valor da chave de busca > V, se houver 
 Se não existe um valor 
 Então 
Faça 
 m = numero de ponteiros no nó 
 C = nó apontado por Pm 
 
Fim Faça 
 Senão 
 C = nó apontado por Pi 
 Fim Se 
 Fim Faça 
 Fim enquanto 
 Se existe um valor de chave Ki em C tal que Ki = V 
 Então Pi nos leva ao registro desejado 
 Senão não existe registro com o valor de chave V 
 Fim Se 
 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
5
Algoritmo de Inserção em uma Árvore B+ 
• Encontrar o nó folha no qual se deve incluir a chave de busca. 
• Se a chave couber no nó, inserir, no nó, a chave de modo que as chaves do nó se mantenham ordenadas. 
• Se a chave de busca não couber no nó, alocar outro nó e preencher os dois nós do seguinte modo: 
o O nó antigo fica com as (n/2, arredondado para cima) primeiras chaves (as n-1 chaves existentes no nó mais a nova chave, 
mantidas ordenadas); 
o O segundo nó fica com as chaves restantes, também mantidas ordenadas. 
o Colocar no nó pai, do nó antigo, a menor chave do novo nó. Se o nó pai não estiver cheio colocar a chave, no nó, de modo que 
continuem ordenadas; se o nó estiver cheio dividi-lo, tal como a divisão do nó folha. Se o nó dividido for a raiz da árvore, a 
árvore aumenta de altura. 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
6
 
Exercício 1 
Apresentar a estrutura da árvore B+ após a inclusão das seguintes chaves: 75,05,10,70,15,20, 65, 80,74,68,95,100 
. Mostrar a estrutura da árvore com duas chaves por nó e três ponteiros. 
 
Para efeito de clareza da estrutura da árvore vamos omitir os ponteiros para os arquivos e os ponteiros nulos. 
Os nós escurecidos significam que foram afetados pela inclusão da nova chave. Ou foram criados, ou alterados. 
 
 Passo 1: Inclusão da chave 75 
 
 
Passo 2: Inclusão da chave 05 
 Como o nó 1 não está cheio incluímos nele a nova chave, de modo a garantir a ordem das chaves 
75 
Nó 1 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
7
 
 
 Repare que as chaves devem ser mantidas ordenadas 
 
Passo 3: Inclusão da chave 10 
Agora precisamos dividir o nó. 
Então, alocamos um novo nó. Deixamos, no nó antigo, as n/2 (arredondado para cima) primeiras chaves (05, 10, 75), no nosso 
caso as chaves 05 e 10; no novo nó as chaves restantes, ou seja 75. 
 
 
 
Nó 1 
05 75 
05 10 75 
Nó 1 
Nó 2 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
8
 
Precisamos agora incluir a menor chave do novo nó (75) no pai do nó antigo; no nosso caso o nó das chaves 05 e 10. Como o nó não tem 
pai devemos criar um novo nó para acomodar a chave. 
 
 
 
 
05 10 75 
75 
Nó 1 
Nó 2 
Nó 3 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
9
Passo 4: Inclusão da chave 70 
A chave 70 deve ser incluída na sub-árvore _a esquerda do nó 3; ou seja no nó 1. 
Como o nó 1 está cheio devemos alocar outro nó e colocar a primeira metade (arredondado para cima) das chaves do nó 1 e as 
restantes no novo nó (nó 4); além de incluir a menor chave do novo nó (nó 4) no pai do nó 1, que é o nó 3, assim: 
 
 
 
 
Passo 5: Inclusão da chave 15 
05 10 75 
70 75 
Nó 1 
Nó 2 
Nó 3 
70 
Nó 4 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
10
 
A chave 15 deve ser incluída nó 1; 
Como o nó 1 está cheio devemos alocar outro nó e colocar a primeira metade (arredondado para cima) das chaves do nó 1 e as 
restantes no novo nó (nó 5); além de incluir a menor chave do novo nó (nó 5) no pai do nó 1, que é o nó 3. Como o nó 3 está 
cheio precisamos alocar um novo nó (nó 6) para acomodar a nova chave (15); como o nó 3 não tem ancestral precisamos alocar 
outro nó para acomodar a nova raiz da árvore; e a nossa árvore fica assim: 
 
 
 
 
 
 
 
 
05 10 75 
75 
Nó 1 
Nó 2 
Nó 3 
70 
Nó 4 
15 
Nó 5 
70 
Nó 7 
15 
Nó 6 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
11
Passo 6: Inclusão da chave 20 
A chave 20 deve ser incluída nó 5; 
Como o nó 5 não está cheio colocamos a chave no nó 5 de modo a garantir a ordem das chaves no nó. A nossa árvore fica assim: 
 
 
 
 
 
 
 
 
 
05 10 75 
75 
Nó 1 
Nó 2 
Nó 3 
70 
Nó 4 
15 20 
Nó 5 
70 
Nó 7 
15 
Nó 6 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
12
Passo 7: Inclusão da chave 65 
A chave 65 deve ser incluída nó 5; 
Como o nó 5 está cheio devemos alocar outro nó (nó 8). Deixamos, então, a primeira metade das chaves no nó 5 e colocamos as 
restantes no novo nó (nó 8). Em seguida devemos incluir a menor chave do novo nó (nó 8) no nó pai do nó 5. Como o nó 6 não 
está cheio incluímos nele a chave (no nosso caso a 65) 
 
 
 
 
 
 
 
 
 
75 
75 
05 10 
Nó 1 
Nó 2 
Nó 3 
70 
Nó 4 
15 
Nó 5 
70 
Nó 7 
15 65 
Nó 6 
20 65 
Nó 8 
 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues
Canêdo 
13
Passo 8: Inclusão da chave 80 
A chave deve ser incluída na sub-árvore à direita da raiz; ou seja no nó 2. 
Como o nó 2 não está cheio incluímos a chave no nó. A árvore fica assim: 
 
 
 
 
 
 
 
 
 
 
75 80 
75 
05 10 
Nó 1 
Nó 2 
Nó 3 
70 
Nó 4 
15 
Nó 5 
70 
Nó 7 
15 65 
Nó 6 
20 65 
Nó 8 
 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
14
Passo 9: Inclusão da chave 74 
A chave 74 deve ser incluída no nó 4. 
Como o nó 4 não está cheio incluímos a chave no nó de modo a garantir a ordem das chaves. A árvore fica assim: 
 
 
 
 
 
 
 
 
 
75 
75 
05 10 
Nó 1 
Nó 2 
Nó 3 
70 74 
Nó 4 
15 
Nó 5 
70 
Nó 7 
15 65 
Nó 6 
20 65 
Nó 8 
 
80 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
15
Passo 10: Inclusão da chave 68 
A chave 68 deve ser incluída no nó 8. 
Como o nó 8 não está cheio incluímos a chave no nó de modo a garantir a ordem das chaves. A árvore fica assim: 
 
 
 
 
 
 
 
 
 
75 
75 
05 10 
Nó 1 
Nó 2 
Nó 3 
70 74 
Nó 4 
15 
Nó 5 
70 
Nó 7 
15 65 
Nó 6 
20 65 
Nó 8 
68 80 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
16
Passo 11: Inclusão da chave 95 
A chave 95 deve ser incluída no nó 2. 
Como o nó 2 está cheio devemos alocar outro bloco para acomodar a chave. Deixamos a primeira metade das chaves no nó 2 e a 
outra metade no novo nó (nó 9); devemos garantir a ordem das chaves nos dois nós. Em seguida devemos incluir a menor chave 
do novo nó (nó 9) no pai do nó 2. A árvore fica assim: 
 
 
 
 
 
 
 
 
 
75 
75 95 
05 10 
Nó 1 Nó 2 
Nó 3 
70 74 
Nó 4 
15 
Nó 5 
70 
Nó 7 
15 65 
Nó 6 
20 65 
Nó 8 
68 80 95 
Nó 9 
 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
17
Passo 12: Inclusão da chave 100 
A chave 100 deve ser incluída no nó 9. 
Como o nó 2 não está cheio, apenas, incluímos a chave no nó. A árvore fica assim: 
 
 
 
 
 
 
 
 
 
 
75 
75 
05 10 
Nó 1 Nó 2 
Nó 3 
70 74 
Nó 4 
15 
Nó 5 
70 
Nó 7 
15 65 
Nó 6 
20 65 
Nó 8 
68 80 95 
Nó 9 
100 
95 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
18
 
Exercício 2 
Apresentar a estrutura da árvore B+ após a inclusão das seguintes chaves: 75,05,10,70,15,20, 80,74,68,95,100 
. Mostrar a estrutura da árvore com três chaves por nó e quatro ponteiros. 
 Passo 1: Inclusão da chave 75 
 
 
 
Passo 2: Inclusão da chave 05 
 Como o nó 1 não está cheio incluímos nele a nova chave, de modo a garantir a ordem das chaves 
 
 
 
75 
Nó 1 
 
Nó 1 
05 75 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
19
 
Passo 3: Inclusão da chave 10 
 Como o nó 1 não está cheio incluímos nele a nova chave, de modo a garantir a ordem das chaves 
 
 
 
Nó 1 
05 10 75 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
20
 
Passo 4: Inclusão da chave 70 
Como o nó 1 está cheio devemos alocar um novo nó para acomodar as chaves. A primeira metade das chaves do nó fica no nó 
antigo e as a outra metade, incluindo a chave que se quer incluir fica no novo nó (nó 2). Nos dois nós as chaves devem ser 
mantidas ordenadas. Assim: 
 
 
 
Precisamos agora incluir a menor chave do novo nó (70) no pai do nó antigo; no nosso caso o nó 1. Como o nó não tem pai 
devemos criar um novo nó para acomodar a chave. 
 
 
 
 
Nó 1 Nó 2 
05 10 70 75 
Nó 1 Nó 2 
05 10 70 75 
70 Nó 3 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
21
 
Passo 5: Inclusão da chave 15 
 A chave 15 deve ser inserida no nó 1. 
Como o nó 1 não está cheio incluímos a incluímos nele a chave. 
 
 
 
 
 
 
 
 
 
Nó 1 Nó 2 
05 10 70 75 15 
70 Nó 3 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
22
Passo 6: Inclusão da chave 20 
 A chave 20 deve ser inserida no nó 1. 
Como o nó 1 está cheio temos de alocar um bloco novo (nó 4) para acomodar as chaves. A primeira metade fica no nó 1 e a outra 
metade incluindo a chave nova fica no nó novo. Incluímos, também a menor chave do novo nó (nó 4) no nó pai do nó1. Assim: 
 
 
 
 
 
 
 
 
Nó 1 Nó 2 
05 10 70 75 
15 70 Nó 3 
Nó 4 
15 20 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
23
Passo 7: Inclusão da chave 80 
 A chave 80 deve ser inserida no nó 2. 
Como o nó 2 não está cheio, incluimos a chave nele, simplesmente. Assim: 
 
 
 
 
 
 
 
 
 
Nó 1 Nó 2 
05 10 70 75 80 
15 70 Nó 3 
Nó 4 
15 20 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
24
Passo 8: Inclusão da chave 74 
 A chave 74 deve ser inserida no nó 2. 
Como o nó 2 está cheio precisamos alocar um novo nó (nó 5) para acomodar as chaves. A primeira metade das chaves fica nó 2 e 
a segunda metade incluindo a chave nova fica no nó 5. Depois transferimos para o pai do nó 4 a menor chave do novo nó (nó5). A 
árvore fica assim: 
 
 
 
 
 
 
 
 
Nó 1 Nó 2 
05 10 70 74 
15 70 75 Nó 3 
Nó 4 
15 20 
Nó 5 
75 80 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
25
Passo 9: Inclusão da chave 68 
 A chave 68 deve ser inserida no nó 4. 
Como o nó 4 não está cheio incluímos a chave nele de modo que as chaves do nó fiquem ordenadas. 
 
 
 
 
 
 
 
 
 
Nó 1 Nó 2 
05 10 70 74 
15 70 75 Nó 3 
Nó 4 
15 20 68 
Nó 5 
75 80 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
26
Passo 10: Inclusão da chave 95 
 A chave 95 deve ser inserida no nó 5. 
Como o nó 2 não está cheio incluímos a chave nele de modo que as chaves do nó fiquem ordenadas. 
 
 
 
 
 
 
 
 
 
Nó 1 Nó 2 
05 10 70 74 
15 70 75 Nó 3 
Nó 4 
15 20 68 
Nó 5 
75 80 95 
Universidade Castólica de Goiás 
Banco de Dados 
Pro.: Ivon Rodrigues Canêdo 
27
Passo 11: Inclusão da chave 100 
 A chave 100 deve ser inserida no nó 2. 
Como o nó 2 está cheio devemos alocar um novo nó. A primeira metade das chaves do nó 2 incluindo a nova chave fica no nó 2 e 
a outra metade fica no nó 6. Em seguida incluímos a menor chave do novo nó (nó 6) no pai do nó2. Como o pai do nó 2 (nó 3) está 
cheio devemos dividi-lo, também. 
 
 
 
 
 
 
 
 
 
Nó 1 Nó 2 
05 10 70 74 
15 70 
Nó 3 
Nó 4 
15 20 68 
Nó 5 
75 80 
Nó 6 
95 100 
95 
Nó 3 
75 
Nó 7