06 - Arvores B V-0'733

Prévia do material em texto

BANCO DE DADOS II 
Árvores B 
 
Versão dos Slides: 0.733 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação 
 Árvores B: Introdução e Propriedades Básicas 
 Operações em Árvores B 
 Variantes de Árvores B 
 Árvores B+ 
2 
3 
armazenamento externo 
serviços de arquivos 
controle de propagação 
estruturas de 
armazenamento 
caminhos de 
acessos lógicos 
estruturas de 
dados lógicas C5 
C4 
C3 
C2 
C1 
Camada 3: 
Estruturas de Armazenamento 
4 
armazenamento externo 
serviços de arquivos 
controle de propagação 
estruturas de 
armazenamento 
caminhos de 
acessos lógicos 
estruturas de 
dados lógicas 
interface de registros internos 
armazenamento de registros (na B*-tree) 
unidades de endereçamento: 
registros intern., B*-trees, tabelas hash 
estruturas auxiliares: 
índices de páginas, tabelas de endereços 
unidades de endereçamento: 
páginas, segmentos 
C5 
C4 
C3 
C2 
C1 
Camada 3: 
Estruturas de Armazenamento 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores Binárias 
5 
 Todo nó contém no máximo dois filhos 
 Todo nó x armazena uma chave e ponteiros 
para o nó pai, o filho à esquerda e o filho à 
direita 
• Notação: chave[x], p[x], esq[x], e dir[x] 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores Binárias 
 Requisito básico: deve ser possível estabelecer 
um ordem total sobre as chaves 
 Propriedade básica: 
• Se y é um nó na subárvore à esquerda do nó x, 
então chave[y] ≤ chave[x] 
• Se y é um nó na subárvore à direita do nó x, então 
chave[x] < chave[y] 
 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplos 
7 
3 
2 5 8 
7 
5 
7 
3 
2 
8 5 
5 
Árvore 1 Árvore 2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Custo de Operações 
 Implementa as operações de Busca, Mínimo, 
Máximo, Predecessor, Sucessor, Inserção, e 
Deleção em O(a) onde a é a altura da árvore 
 Entretanto, se a ≈ n, onde n é número de nós 
na árvore, a performance não é melhor que 
uma simples lista ligada 
 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvore Balanceada 
 Uma árvore binária é dita balanceada se para 
cada nó, a altura de suas subárvores difere de no 
máximo 1 (Árvore AVL - Adelson-Velskii e Landis, 
1962) 
9 
3 
2 5 8 
7 
5 
8 
7 
6 
9 
5 
Árvore Balanceada Árvore Desbalanceada 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação 
 Árvores B: Introdução e Propriedades Básicas 
 Operações em Árvores B 
 Variantes de Árvores B 
 Árvores B+ 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B 
 Generalização do conceito de árvore binária 
de busca 
• Mais de uma chave e mais de duas ramificações 
podem existir em um nó 
 Estrutura de dados criada por Bayer e 
McCreight em 1972 
• Chamada de ubíqua 7 anos mais tarde: Comer, D.: 
The Ubiquitous B-Tree. ACM Computing Surveys, 
11(2) pp. 121-137 (1979) 
• Por que o nome Árvore B? 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B e Banco de Dados 
 “B-trees are by far the most important access 
path structure in database and file systems“ – J. 
Gray and A. Reuter 
 Estrutura de dados usando meio de 
armazenamento externo 
• Necessário quando o conjunto de chaves é muito 
grande para ser mantido na memória principal 
 Modelo de custos baseado na quantidade de 
acessos ao armazenamento externo: modelo I/O 
de computação 
12 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B e Banco de Dados 
 Árvores B são índices otimizados para ambientes que usam 
paginação, isto é, quando o sistema de armazenamento não 
suporta o acesso a nível de bytes 
• O nó de uma árvore B ocupa uma página ou um conjunto de 
páginas 
• Acesso a chaves individuais requer um buffer em 
armazenamento endereçável como memória RAM 
 Suportam consultas pontuais, mutipontuais, baseadas em 
intervalos e scans 
• Registros são “entregues” ordenados para o invocador da 
operação de scan 
• Árvores B mantém a ordenação de dados realizada durante sua 
criação após inserções e deleções dos dados 
• Mecanismo para manutenção de arquivos sequenciais 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação 
 Árvores B: Introdução e Propriedades Básicas 
 Operações em Árvores B 
 Variantes de Árvores B 
 Árvores B+ 
14 
Busca em Árvores 
15 
42 
7 81 
15 chave de busca 
42 81 
7 24 50 61 95 107 
15 chave de busca Árvore de busca com duas e 
três ramificações por nó 
Árvore binária 
42 
chave 
ponteiro 
Árvores B: Propriedades Básicas 
16 
 O nó raiz contém pelo menos uma chave e dois 
ponteiros* 
 Os demais nós de uma árvore B de grau mínimo d 
contém entre [d, 2d] chaves e [d + 1, 2d +1] ponteiros 
 Desta maneira, o nó de uma Árvore B está sempre pelo 
menos ½ cheio 
 Tamanho do nó de uma árvore B = tamanho de página 
Chave 1 Chave 2 .... Chave 2d 
* No caso específico onde um árvore B é usada para indexar apenas um registro temos que a árvore 
toda será formada por um único nó que é a mesmo tempo raiz e folha; neste caso, este nó terá 
apenas uma chave e um único ponteiro. Vamos ignora este caso trivial no restante da discussão. 
2d + 1 ponteiros 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Balanceamento 
 Uma árvore B possui todos os nós folhas em 
uma mesma profundidade sendo, portanto, 
perfeitamente balanceada 
 Operações de inserção e deleçao sempre 
deixam a árvore balanceada 
• Modificações para re-balanceamento restritas a 
um único caminho raiz-folha 
17 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Formato de uma Árvore B 
18 
Altura 𝑂(log𝑑 𝑛) →Busca em 𝑂(log𝑑 𝑛) 
Todas folhas 
neste nível 
grau mínimo 𝑑, 
𝑛 registros indexados 
 Uma operação de busca nunca visita mais que 
𝑙𝑜𝑔𝑑𝑛 + 1 nós 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Inserção 
19 
2 7 
11 
12 15 22 35 41 53 54 63 68 69 71 76 
79 84 93 
30 66 78 
51 
53 54 63 
57 
Inserção 
Caso mais simples: 
O nó que será atualizado pode acomodar uma nova chave 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Inserção 
20 
2 7 
11 
12 15 22 35 41 53 54 63 68 69 71 76 
79 84 93 
30 66 78 
51 
53 54 57 63 
57 
Inserção 
Caso mais simples: 
O nó que será atualizado pode acomodar uma nova chave 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Inserção 
21 
2 7 
11 
12 15 22 35 41 53 54 63 68 69 71 76 
79 84 93 
30 66 78 
51 
53 54 57 63 
72 
Inserção 
Segundo Caso: 
O nó que será atualizado não pode acomodar uma nova chave 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Inserção: Divisão 
22 
66 78 
68 69 71 76 
66 71 78 
68 69 72 76 
 Se após inserção tivermos 2d + 1 chaves (situação de 
overflow), as d chaves com menor valor são 
armazenadas em um nó, as d chaves com maior valor 
são armazenadas em outro e, finalmente, a chave com 
valor mediano é promovida para o nó pai e passa a 
representar o separador para os nós recém-dividos 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
E se o Nó Pai Também 
Estiver Cheio? 
 O mesmo processo de divisão também é aplicado ao 
nó pai 
 Este processo é realizado sucessivamente até que 1) 
um ancestral seja encontrado com espaço para 
acomodar uma nova chave ou 2) o nó raiz seja testado 
(e não contenha espaço) 
 No caso de 2), a árvore B é aumentada em um nível; 
este é o único caso em que a altura de uma árvore B 
aumenta 
 Note que todas as modificaçõespara rebalanceamento 
afetam no máximo um caminho raiz-folha da árvore 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operação de Deleção 
 Deleção em árvores B requer uma operação 
de busca para encontrar o nó que contém a 
chave que será deletada 
 Caso o nó seja folha, a chave pode ser 
deletada diretamente 
 Caso contrário, a chave sucessora da chave 
deletada tem que ser encontrada e movida 
para o mesmo local que a chave deletada 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Busca pela Chave Sucessora 
25 
17 ... ... 
... 
... 
... 
23 ... 21 
 Localização da chave 
sucessora de uma 
chave deletada em um 
nó não-folha: nó folha 
mais à esquerda da 
subárvore à direita da 
chave deletada 
chave deletada: 17 
chave sucessora: 21 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processo de Deleção 
 Após uma chave ter sido movida ou deletada de 
um nó folha é necessário checar se ainda restam 
pelo menos d chaves no nó 
 Caso o nó folha contenha d-1 chaves (situação de 
underflow), é necessário restaurar a propriedade 
de Árvores B de que todo nó possui pelo menos d 
chaves 
 Duas alternativas: 
• Redistribuição 
• Concatenação 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Redistribuição 
 Realiza a restribuição das chaves com um nó 
folha adjacente (o total de chaves entre os dois 
nós deve ser >= 2d) 
 Observe o nova chave separadora no nó pai 
 Pode evitar a necessidade múltiplas situações de 
underflow após deleções sucessivas 
27 
50 
30 41 47 49 60 
... ... 49 
30 41 47 50 60 
... ... 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Concatenação 
 Processo inverso ao de divisão 
• Necessário quando existem menos que 2𝑑 chaves 
para distribuição 
 Note que a chave separando os dois nós no pai 
(chave 15) não é mais necessária 
• Ela é removida do pai e armazenada no nó 
concatenado 
28 
10 15 27 
12 14 20 
10 27 
12 14 15 20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
E se o Número de Chaves no Nó 
Pai for Menor que d? 
 O mesmo processo de contenação também é aplicado 
ao nó pai 
 Este processo é realizado sucessivamente até que 1) 
um ancestral seja encontrado com pelo menos d+ 1 
chaves ou 2) o nó raiz seja alcançado (e contenha 
apenas uma chave) 
 No caso de 2), a Árvore B é diminuída em um nível; 
este é o único caso em que a altura de uma árvore B 
diminui 
 Note que, assim como para inserção, todas as 
modificações para rebalanceamento após deleção 
afetam no máximo um caminho raiz-folha da árvore 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Custo de Operações 
 Dada que um nó de um árvore B corresponde a 
um bloco do disco, temos que, que no pior caso, 
o acesso a nó em uma árvore corresponde a uma 
operação de IO 
 Com exceção do nó raiz, que possui pelo menos 
dois descendentes, todos nós não-folhas 
possuem pelo 𝑑 descendentes em uma árvore de 
grau mínimo 𝑑 
 Portanto o número de nós nos níveis* 
0, 1, 2, … , 𝑛 é 2, 2𝑑, 2𝑑2, … , 2𝑑3 
30 
* O nó raiz está no nível 0, os filhos de um nó no nível 𝑙 − 1 estão no nível 𝑙. 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Custo de Busca 
 Como todas folhas estão no mesmo nível ℎ, temos que a 
quantidade de nós com pelo menos 𝑑 chaves é dada por: 
 𝑑𝑙 =
𝑑ℎ − 1
2𝑑 − 1
ℎ
𝑙=0
 
 Portanto, temos a seguinte restrição para a altura ℎ de uma 
árvore B com n chaves: 
ℎ = log𝑑
𝑛 + 1
2
 
 O número de nós acessados é no máximo ℎ 
 O custo de busca em temos de IO cresce logaritmicamente 
com o tamanho do arquivo 
 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Custo de Busca: Exemplo 
32 
3 4 5 6 7 
2 3 3 4 4 
2 2 3 3 4 
2 2 3 3 4 
103 104 105 106 107 
10 
50 
100 
150 
Tamanho do arquivo em número de registros 
grau da 
árvore B 
Limite superior da quantidade de IO realizada no pior caso 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B na Prática 
 Usando páginas de 4KB ou 8KB podemos ter 
de centenas a milhares de chaves por nó 
• Árvores com de 2 a 3 níveis 
• 99% dos nós são nós folha 
• Mantendo o nó raiz na memória (referência de 
localidade), operações de busca requerem 1 ou 
duas operações de IO 
 
 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Custo de Inserção e Deleção 
 Devido a operações de divisão ou 
concatenação, o custo das operações de 
inserção e deleção é o dobro que a operação 
de busca 
• Tempo proporcional a log𝑑 𝑛 no pior caso 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação 
 Árvores B: Introdução e Propriedades Básicas 
 Operações em Árvores B 
 Variantes de Árvores B 
 Árvores B+ 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B: Variações 
 Emprego da estratégia de redistribuição 
também na operação de inserção para evitar 
sucessivas divisões 
 Árvores B com grau mínimo variável a cada 
nível [Knuth 73] 
 Permitir que nós tenham menos que 𝑑 chaves 
• Quantidade mínima de chaves será 
eventualmente obtida após inserções futuras 
 
 36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B: Variações 
 Árvores B* [Knuth 73] 
 Define que nós contenham pelo menos 4d/3 
chaves (e não apenas d) 
• Na prática, nós encontram-se 70% cheios após uma 
sequência randômica de inserções e deleções 
 A operação de inserção emprega um esquema de 
redistribuição local que adia a divisão até o 
momento em dois nós adjacentes estejam cheios 
 Reduz a altura da árvore B -> acelera o tempo de 
busca 
 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processamento Sequencial 
 Operações discutidas até o momento se referem 
a acessos randômicos 
 Processamento sequencial: recuperação de um 
conjunto de registros em sequência determinada 
pela ordenação da chave 
 Cada localização da chave sucessora pode 
requerer o percorrimento de caminhos através 
de vários nós 
• Relembre, o sucessor em nós não folha está localizado 
na folha mais a esquerda da subárvore a direita 
38 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B: Variações 
 Árvores B+: todas as chaves são armazenadas 
nos nós folhas 
 Os valores armazenados nos nós superiores 
representam apenas um “roadmap” para 
rápida localização das chaves 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Motivação 
 Árvores B: Introdução e Propriedades Básicas 
 Operações em Árvores B 
 Variantes de Árvores B 
 Árvores B+ 
40 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B+ 
41 
Busca randômica 
Busca 
sequencial 
Índice: uma 
Árvore B 
 Nós no índice e na sequência de conjuntos 
pode ter diferentes tamanhos e formatos 
Nós-folha representados por lista duplamente encadeada 
Nós Não-Folha 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B+ 
 Manter o índice e a sequência de conjuntos de 
maneira independente traz vários benefícios 
• Operações de busca, inserção, e deleção sofrem 
apenas pequenas mudanças; custo ainda é 
O(logdn) 
• Processamento sequencial requer no máximo um 
acesso para encontrar a próxima chave 
 Arvores B+ é a variante mais usada na prática 
em SGBDs 
42 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Árvores B+: 
Layout de Entradas em Nós-Folha 
43 
Chave de Busca Layout 1: Registro 
 Arquivo sequencial 
armazenado nos nós-folha 
Chave de Busca Layout 2: RID 
 Nós-folha contém ponteiros 
(RIDs) para páginas do 
arquivo sequencial 
Chave de Busca Layout 3: Chave  Nós-folha contém chaves de 
busca de um índice primário 
 Layout 1 é normalmente empregado em índices 
primários; layout 2 e 3 em índices secundáriosProf. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Secundários: 
Layout 2 vs. Layout 3 
44 
Índice Primário Índice Secundário 
RID 
Layout 2: 
Índice Primário Índice Secundário 
Layout 3: 
chave de busca 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Índices Secundários: 
Layout 2 vs. Layout 3 
 As duas estratégias possuem vantagens e desvantagens 
 Layout 2: 
• Vantagem: permite acesso direto ao bloco desejado no 
arquivo sequencial 
• Desvantagem: Divisões ou concatenações de nós-folha no 
índice primário demandam atualizações em todos índices 
secundários 
 Layout 3: 
• Vantagem: divisões ou concatenações de nós-folha no 
índice primário não afetam índices secundários 
• Desvantagem: Requer uma busca no índice primário para 
toda busca no índice secundário 
 
45 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Referências Adicionais 
 Comer, D.: The Ubiquitous B-Tree. ACM Computing 
Surveys, 11(2) pp. 121-137 (1979) 
 Goetz Graefe: Modern B-Tree Techniques 
Foundations and Trends in Databases 3(4): 203-402 
(2011) 
46