Dicionários: B-Trees

1. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-11
B-TreesB-Trees
Dicionários: B-TreesDicionários: B-Trees
Estruturas de Dados
2003/04
Aula teórica de 2003.11.12 (T9)
©2003 Salvador Abreu

2. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-22
B-TreesB-Trees
MotivaçãoMotivação
●
Grandes quantidades de informaçãoGrandes quantidades de informação
–Requer armazenamento externo (disco)Requer armazenamento externo (disco)
–Acesso a disco lento (várias ordens de Acesso a disco lento (várias ordens de
grandeza pior que memória)grandeza pior que memória)
–Procurar organização que minimize acessos Procurar organização que minimize acessos
a disco talvez desprezando quantidade de a disco talvez desprezando quantidade de
processamento?processamento?
●
Organização em árvoreOrganização em árvore
–Árvore de grau KÁrvore de grau K
–N elementos: acessos = O(logN elementos: acessos = O(log
KK N) N)

3. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-33
B-TreesB-Trees
ExemploExemplo
●
Registo CivilRegisto Civil
–Bilhetes de IdentidadeBilhetes de Identidade
–Cerca de 10.000.000 registos diferentesCerca de 10.000.000 registos diferentes
–Cada registo:Cada registo:
●
Nomes (próprio, pai, mãe): 128 bytes cadaNomes (próprio, pai, mãe): 128 bytes cada
●
Datas, locais, etc.: 128 bytesDatas, locais, etc.: 128 bytes
●
=> Total => Total 1K byte por registo1K byte por registo
●
ServidorServidor
–1 IPC @ 2GHz, 1000 APS1 IPC @ 2GHz, 1000 APS
–100 utilizadores simultâneos100 utilizadores simultâneos
●
~ 1IPC @ 20MHz, 10APS~ 1IPC @ 20MHz, 10APS

4. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-44
B-TreesB-Trees
Exemplo: árvore bináriaExemplo: árvore binária
●
Supondo AVL (ou outra binária Supondo AVL (ou outra binária
equilibrada)equilibrada)
–Profundidade: logProfundidade: log
22
(10(10
77
) ~ ) ~ 2727
–Pesquisa feita em média em 27 acesso, a 10 Pesquisa feita em média em 27 acesso, a 10
APS = 2.7sAPS = 2.7s
●
Se variarmos o grau (N) da árvoreSe variarmos o grau (N) da árvore
–N=5N=5: P=log: P=log
55
(10(10
77
) ~ ) ~ 1111; GD = ; GD = 60%60%
–N=10N=10: P=log: P=log
1010
(10(10
77
) ~ ) ~ 77; GD = ; GD = 75%75%
–N=128N=128: P=log: P=log
128128
(10(10
77
) ~ ) ~ 44; GD = ; GD = 85%85%

5. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-55
B-TreesB-Trees
ExemploExemplo
●
Grau suficientemente alto:Grau suficientemente alto:
–Limite superior sobre o número de acessos a disco: Limite superior sobre o número de acessos a disco:
objectivo valor pequeno (3-5 acessos.)objectivo valor pequeno (3-5 acessos.)
●
Resta saber como fazer...Resta saber como fazer...
–Ideia geral: árvore N-ária.Ideia geral: árvore N-ária.
–Cada nó contém K=O(N) chaves.Cada nó contém K=O(N) chaves.
–Busca envolve fazer uma pesquisa (p/ex binária) Busca envolve fazer uma pesquisa (p/ex binária)
sobre cada nó.sobre cada nó.
–Caso não esteja, desce-se para um filho particular.Caso não esteja, desce-se para um filho particular.

6. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-66
B-TreesB-Trees
B-Tree: EsquemaB-Tree: Esquema
k
1
k
2
k
3
k
i
<k
1
k
1
<k<k
2
k>k
i

7. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-77
B-TreesB-Trees
O que são: B-TreesO que são: B-Trees
●
Definição (“Propriedade BT”):Definição (“Propriedade BT”):
–B-Tree de ordem MB-Tree de ordem M
●
Nós interiores:Nós interiores:
–Entre ceil(M/2) e M filhosEntre ceil(M/2) e M filhos
–Se tiver N<=M filhos, terá exactamente N-1 chavesSe tiver N<=M filhos, terá exactamente N-1 chaves
●
Folhas: todas à mesma profundidadeFolhas: todas à mesma profundidade
–Por construçãoPor construção
–Têm entre 1 e M-1 chavesTêm entre 1 e M-1 chaves
●
Raíz: folha ou tem no máximo M filhosRaíz: folha ou tem no máximo M filhos
–Nós interiores:Nós interiores:
●
Referências aos filhos (F[i], i=1..M)Referências aos filhos (F[i], i=1..M)
●
Chaves contidas (K[i], i=1..M-1)Chaves contidas (K[i], i=1..M-1)
–FolhasFolhas
●
Chaves contidas (K[i], i=1..M-1)Chaves contidas (K[i], i=1..M-1)

8. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-88
B-TreesB-Trees
Exemplos simplesExemplos simples
●
Ex: B-tree de ordem 3, tb designada por árvore Ex: B-tree de ordem 3, tb designada por árvore
2-32-3
–3: grau máximo dos nós3: grau máximo dos nós
–2: número máximo de chaves nos nós2: número máximo de chaves nos nós
●
B-Tree de ordem 3 (i.e. árvore 2-3)B-Tree de ordem 3 (i.e. árvore 2-3)

9. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-99
B-TreesB-Trees
B-Tree: ExemploB-Tree: Exemplo
15
0 7, 8 12, 13 17, 18
2, 5
10
3

10. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1010
B-TreesB-Trees
B-Tree: PesquisaB-Tree: Pesquisa
●
Simples, semelhante a pesquisa bináriaSimples, semelhante a pesquisa binária
–em cada nó interiorem cada nó interior
●
Se X=K[i], encontramosSe X=K[i], encontramos
●
Se K[i-1]<X<K[i], procurar no filho F[i]Se K[i-1]<X<K[i], procurar no filho F[i]
–nas folhasnas folhas
●
Só resulta se encontrarmosSó resulta se encontrarmos

11. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1111
B-TreesB-Trees
B-Tree: InserçãoB-Tree: Inserção
●
Inicialmente igual à pesquisa, obtemos a Inicialmente igual à pesquisa, obtemos a
folha onde seria para inserirfolha onde seria para inserir
–Forçosamente numa folhaForçosamente numa folha
●
Caso não haja violação da propriedade Caso não haja violação da propriedade
BT (i.e. há menos que M valores na BT (i.e. há menos que M valores na
folha):folha):
–Inserimos e pronto.Inserimos e pronto.
–Possivelmente há que ajustar os valores de Possivelmente há que ajustar os valores de
mj nos no caminho até à folhamj nos no caminho até à folha
●
Caso não caiba: temos de repor a Caso não caiba: temos de repor a
"legalidade"..."legalidade"...

12. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1212
B-TreesB-Trees
B-Tree: Re-equilibrar (insersão)B-Tree: Re-equilibrar (insersão)
●
Dá-se mais um irmão à folha onde se iria Dá-se mais um irmão à folha onde se iria
inserir:inserir:
●
Transita-se uma chave Km (mediana) da antiga folha Transita-se uma chave Km (mediana) da antiga folha
(aumentada com a chave a inserir) para o pai(aumentada com a chave a inserir) para o pai
●
Divide-se os valores (<Km, >Km) entre as novas folhasDivide-se os valores (<Km, >Km) entre as novas folhas
●
Caso não seja possível (pai já tem M filhos)Caso não seja possível (pai já tem M filhos)
–Dividir o pai em dois:Dividir o pai em dois:
●
cada um com a metade dos filhos (que ficam na mesma)cada um com a metade dos filhos (que ficam na mesma)
●
Transitando uma chave (mediana) do antigo pai para o Transitando uma chave (mediana) do antigo pai para o
avôavô
●
Caso não seja possível, repetir operação ao Caso não seja possível, repetir operação ao
nível do avô, etc... até à raíznível do avô, etc... até à raíz

13. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1313
B-TreesB-Trees
B-Tree: Re-equilibrar (insersão)B-Tree: Re-equilibrar (insersão)
●
Chegando à raíz, e esta estando cheia…Chegando à raíz, e esta estando cheia…
–Cria-se uma Cria-se uma nova raíznova raíz..
●
Com a mediana (Km) da antigaCom a mediana (Km) da antiga
–Parte-se a antiga raíz em doisParte-se a antiga raíz em dois
●
Dividindo os valores da raíz anterior (<Km, >Km)Dividindo os valores da raíz anterior (<Km, >Km)
●
Mantém-se os filhos e fica-se com uma árvore Mantém-se os filhos e fica-se com uma árvore
mais profundamais profunda

14. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1414
B-TreesB-Trees
B-Tree: Exemplo (1)B-Tree: Exemplo (1)
●
Inserção dos inteirosInserção dos inteiros
0, 5, 10, 15, 2, 7, 12, 17, 3, 8, 13, 180, 5, 10, 15, 2, 7, 12, 17, 3, 8, 13, 18
0 0,5 0,5,10 5
0 10
5
0 10, 15
5
0, 2 10, 15
5
0, 2 7, 10, 15
5, 10
0, 2 7 15

15. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1515
B-TreesB-Trees
B-Tree: Exemplo (2)B-Tree: Exemplo (2)
5, 10
0, 2 7 12, 15
5, 10
0, 2 7 12, 15, 17
5, 10, 15
0, 2 7 12 17
15
0, 2 7 12 17
5
10

16. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1616
B-TreesB-Trees
B-Tree: Exemplo (3)B-Tree: Exemplo (3)
15
0 7, 8 12, 13 17, 18
2, 5
10
3

17. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1717
B-TreesB-Trees
B-Tree: remoçãoB-Tree: remoção
•Semelhante à inserçãoSemelhante à inserção
•Se número de elementos da folha resultante Se número de elementos da folha resultante
>1, não precisa fazer mais nada.>1, não precisa fazer mais nada.
•Se número de elementos da folha = 1Se número de elementos da folha = 1
–Combinar elemento restante com um irmãoCombinar elemento restante com um irmão
–Se passou a ser filho único, repetir operação ao Se passou a ser filho único, repetir operação ao
nível superiornível superior
–Se se chegar à raíz, toma-se como nova raíz o seu Se se chegar à raíz, toma-se como nova raíz o seu
filho únicofilho único

18. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1818
B-TreesB-Trees
B-Tree: análiseB-Tree: análise
•Profundidade máx. duma B-Tree de ordem MProfundidade máx. duma B-Tree de ordem M
–ceil(logceil(log
floor(M/2)floor(M/2)
N) N)
•PesquisaPesquisa
–Em cada nó, fazemos O(log M) trabalho para Em cada nó, fazemos O(log M) trabalho para
determinar por onde vamos (c/ pesquisa binária)determinar por onde vamos (c/ pesquisa binária)
–pior caso: O(log N)pior caso: O(log N)
•Inserção e remoçãoInserção e remoção
–Como pesquisa, mas podemos ter de fazer O(M) Como pesquisa, mas podemos ter de fazer O(M)
para repor as condiçõespara repor as condições
– pior caso: O(M logpior caso: O(M log
MM
N) = O((M/log M) log N) N) = O((M/log M) log N)

19. EE
ss
ttrruuttuurraass

dd
e
e


DD
aa
dd
oo
ss
2003/04 9-2003/04 9-1919
B-TreesB-Trees
B-Tree: usosB-Tree: usos
•Uso principal: Bases de dadosUso principal: Bases de dados
–Árvore mantida em disco, não em memóriaÁrvore mantida em disco, não em memória
–Número de acessos a nós = número de acessos a Número de acessos a nós = número de acessos a
discodisco
•Operação sempre muito lentaOperação sempre muito lenta
•Convem que sejam poucos (e grandes)Convem que sejam poucos (e grandes)
•O(logO(log
MM
N) N)
–Na prática, usam-se valores de M que:Na prática, usam-se valores de M que:
•sejam “grandes”sejam “grandes”
•permitam que um nó inteiro caiba num permitam que um nó inteiro caiba num blocobloco de disco de disco
(p/ex uma página de VM, tipicamente 8K)(p/ex uma página de VM, tipicamente 8K)
•em geral serão valores entre 32 e 256em geral serão valores entre 32 e 256