Algorítmos e estrutura de
dados III
Carlos Oberdan Rolim
Ciência da Computação
Árvores 2-3
Árvores B (B-Trees)
Árvores B+
Árvores de busca com grau maior que 2
Vimos que árvores de busca quando balanceadas,
como as árvores AVL, permitem busca em tempo
logarítmico.
No caso das árvores AVL, a busca se dá em tempo
log2 (n) no pior caso.
Poderíamos tentar melhorar procurando fazer a
busca em tempo logk (n), com k > 2.
Árvores 2-3
Similar às árvores AVL, mas
- Cada nó interno tem dois ou três filhos e
- Todos os nós externos têm a mesma profundidade.
P
G
T
C
A
KM
F
H
L
R
O
Q
X
S
V
Z
Inserção em árvores 2-3
Como nas árvores AVL, a inserção se dá numa folha. Se há
espaço para acrescentar o novo elemento, ele entra aí.
Ex: Inserção do elemento G na árvore abaixo.
T
I
EG
VX
LP
U
W
Z
Inserção em árvores 2-3
Se não há espaço para acrescentar o novo elemento, gerase dois nós com os dois elementos extremos no nó, e
promove-se o elemento central, para ser incluído no nível
imediatamente superior.
T
I
EG
VX
LP
N
U
W
Z
Inserção em árvores 2-3
Ex: Inserção do elemento N na árvore abaixo.
Como um nó não pode ter três elementos, são criados dois nós
com um elemento cada, e o elemento do meio é promovido.
T
I N
EG
L
VX
P
U
W
Z
Inserção em árvores 2-3
Se não há espaço para acrescentar o nó promovido,
procede-se da mesma forma que no overflow anterior, até
eventualmente achar espaço suficiente ou chegar até a raiz.
Ex: Inserção do elemento C na árvore abaixo.
T
I N
EG
C
L
VX
P
U
W
Z
Inserção em árvores 2-3
Se não há espaço para acrescentar o nó promovido,
procede-se da mesma forma que no overflow anterior, até
eventualmente achar espaço suficiente ou chegar até a raiz.
Ex: Inserção do elemento C leva à promoção do elemento E.
I
E
C
T
N
G
L
VX
P
U
W
Z
Inserção em árvores 2-3
Ex: Inserção do elemento C leva à promoção do elemento E
que por sua vez leva à promoção do elemento I.
IT
E
C
N
G
L
VX
P
U
W
Z
Árvores B ou B-Tree
Note que a diferença crucial em termos de tempo
de acesso entre a árvores binárias e as árvores 2-3
é que agora o acesso pode ser feito em tempo
logarítmico, mas com base 3, o que é mais rápido.
Podemos pensar então numa forma de diminuir
mais ainda o tempo de acesso, aumentando o
número de elementos em cada nó.
Árvores B
Árvores B são uma extensão da noção de árvores
2-3, onde cada nó que não é a raiz pode ter entre
m e 2m chaves.
Esta estrutura normalmente é usada em memória
externa.
Deve haver um compromisso entre o maior número
de elementos por nó e a capacidade de acesso em
disco, além de uma técnica de busca dentro do nó.
Árvores B
É um tipo de árvore muito utilizada em banco de
dados e sistema de arquivos.
Para inserir ou remover variáveis de um nó, o nó não
poderá ultrapassar sua ordem e nem ser menor que
sua ordem dividida por dois.
Árvores B não precisam ser rebalanceadas como são
freqüentemente as árvores de busca binária com
Árvore AVL.
Árvores B
Árvores B têm vantagens substanciais em relação a outros
tipos de implementações quanto ao tempo de acesso e
pesquisa aos nós.
O criador das árvores B, Rudolf Bayer, não definiu
claramente de onde veio o B das árvores B.
Ao que parece, o B vem de balanceamento onde todos os
nós da árvore estão em um mesmo nível.
Também é possível que o B tenha vindo de seu
sobrenome Bayer, ou ainda do nome da empresa onde
trabalhava Boeing, no Boeing Scientific Research Labs.
Árvores B
Definições
Quando existem 2 ou mais nós, passam a ser
chamadas de n-árias
Nesses casos, os nós são mais comumente
chamados de páginas
Os registros de uma árvore B também são todos
ordenados
Árvores B
Supondo uma árvore B n-ária. Em um
árvore B de ordem m temos:
Cada página contém:
Registros: no mínimo m e no máximo 2m registros
, exceto a raiz, que pode conter entre 1 e 2m
registros;
Descendentes: no mínimo m + 1 descendentes e
no máximo
2m +1 descendentes
Todas as páginas folhas aparecem no mesmo nível
Exemplo de uma árvore B
Exemplo de uma árvore B de ordem 2 com 3 níveis
30
10 20
3489
11 13 17
Páginas
25 28
40 50
33 36
43 45 48
52 55
Árvores B
Objetivo principal
Minimizar o número de acessos ao disco para recuperar um registro
25
10
2 5 7 8
20
30
22 24
13 14 15 18
40
26 27 28
41 42 45 46
32 35 38
Declaração do TAD Árvores B
Definição da Estrutura
#define ORDEM 2
#define TAMANHO (ORDEM*2)-1
typedef struct Pagina *PonteiroPagina;
typedef struct {
int chave;
PonteiroPagina p;
} item;
typedef struct {
int m;
// numero de itens na pagina
PonteiroPagina p0;
item e[TAMANHO];
} Pagina;
Declaração do TAD Árvores B
Definição das operações. Algumas das
operações que podem ser feitas em árvores
B são:
Inicializa
Pesquisa
Insere
Retira
Pesquisa em Árvore B
Procedimento para pesquisa do número 13
30
10 20
3489
11 13 17
40 50
25 28
33 36
42 45 48
52 55
Pesquisa em Árvore B
Procedimento para pesquisa do número 55
30
10 20
3489
11 13 17
40 50
25 28
33 36
42 45 48
52 55
Inserção
Primeiro, é preciso localizar a página apropriada em que o
novo registro deve ser inserido
Duas possibilidades:
Caso 1: o registro encontra seu lugar em uma página com menos de 2m
registros. Nesse caso, o processo de inserção fica limitado àquela
página
Caso 2:O registro precisa ser inserido em uma página já cheia (com 2m
registros). Nesse caso, o processo de inserção pode levar à criação de
uma nova página.
Inserção de Registros
Caso 1: o registro encontra seu lugar em uma página com menos de 2m registros
Ordem 2
Registro 9
40
Registro 45
Registro 50
348 9
41 43 45 50
Inserção de Registros
Caso 2: O registro precisa ser inserido em uma página já cheia (com 2m registros),
e a página pai tem menos que 2m registros e 2m+1 páginas
Ordem: 2
40
Registro 20
348 9
20
40
41 43 45 50
3 4 8 9 20
41 43 45 50
8 40
40
3 4 8 9 20
41 43 45 50
34
9 20
41 43 45 50
Inserção de Registros
Caso 2: O registro precisa ser inserido em uma página já cheia (com 2m registros),
e a página pai já tem 2m registros e 2m+1 páginas
Ordem: 2
8 20 28 40
Registro 22
1347
9 13 15 18 21 23 25 26
30 33 35 37
41 43 45 50
22
8 20 28 40
1347
9 13 15 18
21 22 23 25 26
30 33 35 37
41 43 45 50
8 20 23 28 40
1347
9 13 15 18
21 22
25 26
30 33 35 37
41 43 45 50
23
28 40
8 20
1347
9 13 15 18
21 22
25 26
30 33 35 37
41 43 45 50
Remoção
Primeiro, é preciso localizar a página apropriada do registro a ser
excluído
Duas possibilidades:
Caso 1: quando o registro se encontra em uma página folha.
1.1: A folha possui mais que m registros
1.2: A folha possui apenas m registro e o irmão possui m+1 registros
1.3: A folha e seus irmãos possuem apenas m registros
Caso 2: quando o registro não se encontra em uma folha. Nesse caso, o
registro a ser retirado deve ser primeiro substituído por um outro para depois
ser excluído.
Em ambos os casos deve-se verificar se a retirada não afeta as
propriedades básicas de uma árvore B
Remoção de Registros
Caso 1.1: quando o registro se encontra em uma página folha e a folha possui
mais que m registros
Ordem 2
Registros 7, 13, 15, 33, 37, 41 e 43
23
28 40
8 20
1347
9 13 15 18
21 22
Retirada simples do elemento da folha
25 26
30 33 35 37
41 43 45 50
Remoção de Registros
Caso 1.2: quando o registro se encontra em uma página folha, a folha possui
m registros (mínimo possível) e o irmão possui m+1 registros
Ordem 2
23
Registro 9
28 40
8 20
134
9 18
21 22
25 26
30 35
45 50
23
28 40
4 20
13
8 18
21 22
25 26
30 35
45 50
A chave k do pai que separa os irmãos pode ser incluída no nó X e a última ou
primeira chave do irmão (última se o irmão for da esquerda e primeira se o
irmão for da direita) pode ser inserida no pai no lugar de k.
Remoção de Registros
Caso 1.2: quando o registro se encontra em uma página folha, a folha possui
m registro (mínimo possível) e o irmão possui m+1 registros
Ordem 2
23
Registro 18
28 40
8 19
134
9 18
20 21 22
25 26
30 35
45 50
23
28 40
8 20
134
8 19
21 22
25 26
30 35
45 50
Remoção de Registros
Caso 1.3: quando o registro se encontra em uma página folha, a folha e seus
irmãos possuem m registros (mínimo possível). Se sub-dividem em dois
casos:
• Caso 1.3.1: O pai pode emprestar registros
•Caso 1.3.2: O pai não pode emprestar registros
Remoção de Registros
Caso 1.3.1: quando o registro se encontra em uma página folha, a folha e seus
irmãos possuem m registros (mínimo possível) e o pai pode emprestar
Ordem 2
23
Registro 6
13
28 40
4 10 20
68
13 18
21 22
25 26
30 35
45 50
23
28 40
10 20
1348
13 18
21 22
25 26
30 35
45 50
Se os dois irmãos de X contiverem exatamente m registros (ocupação
mínima), nenhum registro poderá ser emprestado. Neste caso, o nó X e um de
seus irmãos (à esquerda ou direita) são concatenados em um único nó, que
também contém a chave separadora do pai.
Remoção de Registros
Caso 1.3.1: quando o registro se encontra em uma página folha, a folha e seus
irmãos possuem m registros (mínimo possível) e o pai pode emprestar
Ordem 2
23
Registro 8
13
28 40
4 10 20
68
13 18
21 22
25 26
30 35
45 50
23
28 40
4 20
13
6 10 13 18
21 22
25 26
30 35
45 50
Remoção de Registros
Caso 1.3.1: quando o registro se encontra em uma página folha, a folha e seus
irmãos possuem m registros (mínimo possível) e o pai pode emprestar
Ordem 2
23
Registro 22
13
28 40
4 10 20
68
13 18
21 22
25 26
30 35
45 50
23
28 40
4 10
13
68
13 18 20 21
25 26
30 35
45 50
Remoção de Registros
Caso 1.3.2: quando o registro se encontra em uma página folha, a folha e seus
irmãos possuem m registros (mínimo possível) e o pai não pode emprestar
Ordem 2
Registro 13
23
28 40
10 20
48
13 18
21 22
25 26
30 35
45 50
Se os dois irmãos de X e o pai contiverem exatamente m registros (ocupação
mínima), também nenhum registro poderá ser emprestado. Neste caso, o nó X
e um de seus irmãos são concatenados em um único nó que também contém
a chave separadora do pai, e o procedimento é feito recursivamente até que
as páginas contenham a quantidade mínima de registros.
Remoção de Registros
23
28 40
10 20
48
13 18
21 22
25 26
30 35
45 50
23
28 40
20
4 8 10 18
21 22
25 26
30 35
45 50
4 8 10 18
20 23 28 40
21 22
25 26
30 35
45 50
Remoção de Registros
Outro exemplo: Árvore B de ordem 1
Registro 3
10
05
20
02
01
07
03
06
15
09
13
35
16
30
40
10
05
20
07
01 02
06
15
09
13
35
16
30
40
Remoção de Registros
10
05
20
07
01 02
06
15
09
13
35
16
10
30
40
20
05 07
01 02
10 20
05 07
01 02
06
15
09
13
35
16
30
40
06
15
09
13
35
16
30
40
Remoção
Caso 2: quando o registro não se encontra em uma folha.
Mesmo procedimento de remoção em árvores binárias ou
AVL
Substituição pelo registro mais à direita da sub-árvore à esquerda;
Substituição pelo registro mais à esquerda da sub-árvore à direita;
Caso 2.1: a sub-árvore vizinha possui registros para
emprestar
Caso 2.2: a sub-árvore vizinha não possui registros para
emprestar
Remoção de Registros
Caso 2.1: a sub-árvore vizinha possui registros para emprestar
20 24 28 40
Registro 20
4 8 10 18
21 22 23
25 26
30 35
45 50
21 24 28 40
OU
18 24 28 40
4 8 10 18
4 8 10
21 22 23
25 26
30 35
45 50
22 23
25 26
30 35
45 50
Remoção de Registros
Caso 2: quando o registro não se encontra em uma folha.
Possui dois casos:
Caso 2.2.1: O irmão possui registros para emprestar
Caso 2.2.2: O irmão não possui registros para emprestar
Remoção de Registros
Caso 2.2.1: a sub-árvore vizinha NÃO possui registros para emprestar e o irmão
possui registros para emprestar
23
Registro 20
4 20
13
6 18
28 37 40
21 22
25 26
38 39
30 35
45 50
23
28 37 40
4
13
6 18 21 22
25 26
30 35
38 39
45 50
Concatena-se o filho à esquerda e à direita do registro excluído; o registro mais à esquerda
(ou mais à direita) do irmão é promovido para a raiz e o registro à esquerda (ou à direita) da
raiz é inserido na página que teve o registro excluído; o filho à esquerda (ou o filho à
direita) do registro que foi emprestado passa a ser o filho à direita (ou à esquerda) do nó
para onde ele foi deslocado;
Remoção de Registros
23
28 37 40
4
13
6 18 21 22
25 26
30 35
38 39
45 50
28
4 23
13
6 18 21 22
37 40
25 26
30 35
38 39
45 50
Remoção de Registros
Caso 2.2.1: a sub-árvore vizinha NÃO possui registros para emprestar e o irmão
possui registros para emprestar
28
Registro 40
4 20 25
13
6 18
22 23
37 40
26 27
30 32
38 39
45 50
28
4 20 25
13
6 18
22 23
37
26 27
30 32
38 39 45 50
Remoção de Registros
28
4 20 25
13
6 18
22 23
37
26 27
30 32
38 39 45 50
25
28 37
4 20
13
6 18
22 23
26 27
30 32
38 39 45 50
Remoção de Registros
Caso 2.2.2: a sub-árvore vizinha NÃO possui registros para emprestar e o irmão
também NÃO possui registros para emprestar
28
Registro 23
4 23
13
37 40
25 26
6 18
30 35
45 50
4 28 37 40
28
4
13
6 18 25 26
37 40
30 35
45 50
13
6 18 25 26
30 35
45 50
Concatena-se os registros filhos à esquerda e à direita do registro excluído; em seguida,
concatena-se os registros da página excluída, do seu irmão e do seu pai
Considerações finais
Inserção: Mais veloz se comparado à tabelas de
hash, por sua capacidade de se ajustar e balancear
a cada inserção, isto significa menores colisões, e
consequentemente menos laços para encontrar
uma posição livre.
No caso de precisar expandir, a duplicação é feita
somente na folha, e nos nós correspondentes se
necessário, o que garante menor espaço vazio
alocado e menos ocupação em disco, ao contrário
do hash que duplica a tabela por inteiro.
Considerações finais
Exclusão: No caso de uma exclusão,
Arvores B são capazes de evitar grandes
fragmentações, pois se ajustam e
balanceiam também nesse momento.
Já em tabelas de hash, quando há exclusão
de uma chave, o espaço alocado para esta
fica vazio, porém ainda alocado. Maior
fragmentação significa menor desempenho.
Considerações finais
Busca: Árvores B são tão boas e velozes quanto tabelas de
hash numa busca por igualdade, porém são muito superiores
em velocidade e desempenho em buscas do tipo range.
A superioridade da Árvore B, se baseia na chave primária,
onde a busca começa pela raiz e é direcionada aos nós e
filhos de acordo com a chave procurada, isto torna mais
objetivo e direto o resultado final. Porém, se comparado a
Árvore B+, sua performance pode cair um pouco em uma
busca linear.
Árvores B+
São árvores B que contém dados somente nos nós folhas e
existe uma ligação entre os irmãos folhas adjacentes para
facilitar a busca
Uma árvore B+ é uma variação da árvore B.
Representa a ordenação de dados de uma maneira que
permita uma inserção e remoção eficiente de elementos.
É um índice dinâmico de multi-níveis com ligações
máximas e mínimas no número de chaves em cada nodo.
Árvores B+
Os sistemas de arquivos NTFS para o Microsoft Windows, o
sistema de arquivos ReiserFS para Unix, o XFS para IRIX e
Linux, e o JFS2 para AIX, OS/2 e Linux, usam este tipo de
árvore.
Numa árvore-B+, contrastando com uma árvore-B, todos dos
dados são gravados nas folhas.
Os nodos internos contêm apenas chaves e apontadores da
árvore.
Todas as folhas estão no mesmo nível mais baixo.
Os nodos das folhas também estão ligados entre si como uma
lista para efetuar consultas facilmente.
Arvores B+
O número máximo de apontadores num registro é
chamado de ordem da árvore B+.
O número mínimo de chaves por registro é metade do
número máximo de chaves. Por exemplo:
Se a ordem de uma árvore B+ for n+1, cada nodo (exceto o da raiz)
deverá ter entre (n+1)/2 e n chaves.
Se n for um número primo, o número mínimo de chaves pode ser
(n+1)/2 ou (n-1)/2, mas terá de ser o mesmo em toda a árvore.
Árvores B+
Um exemplo simples de uma árvore B+ ligando as chaves 1-7 aos
valores de dados d1-d7.
Notar a lista ligada (em vermelho) permitindo uma atualização
ordenada rápida.