Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 ACH2024 Aulas 17 e 18 Árvores B Profa. Ariane Machado Lima 2 Nas aulas passadas... 3 https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/9_VirtualMemory.html Memória virtual 4 O você acha que o computador deve fazer para ler algum dado do HD? 1) Identifica em que setor/trilha/superfície está a informação 2) Movimenta o braço de leitura para o cilindro correto (para poder acessa a trilha correta) 3) Rotaciona o prato para posicionar a cabeça de leitura sobre o setor correto 4) Faz a leitura de um certo nr de bytes Passos 2 e 3 (chamados SEEK) são mecânicos! Por isso demora tanto! 5 Arquivos de dados Bloco: unidade de transferência de dados entre memória principal e a memória secundária (~ tamanho de uma página) É comum considerar que em cada bloco pode haver vários registros Se R (tamanho fixo do registro) e B (tamanho do bloco) e R ≤ B: fator de blocagem fb = floor(B/R) 6 Organização de arquivos (como os registros são armazenados nos blocos) Tipos vistos na aula passada: – Não ordenada (heap files) – Ordenada (sorted files) – Indexada Organização tem impacto nas operações de inserção, deleção, modificação, busca, etc. 7 Organização não ordenada O arquivo, de r registros espalhados em b blocos, não está ordenado Inserção eficiente: O(1) Busca: O(b) Remoção: Precisa achar onde está o registro – O(b) Modificação de registro de tamanho variável: Pode exigir a remoção de outros registros a serem inseridos em outros blocos Leitura ordenada: MUITO INEFICIENTE Exige uma ordenação primeiro! (ordenação externa) 8 Organização ordenada Os r registros estão ordenados pela chave Leitura ordenada eficiente (sequencial) – O(b) O próximo registro pode estar no mesmo bloco Mínimo / Máximo estão no cabeçalho do arquivo – O(1) Busca: dá para usar busca binária (baseada nos blocos!) - O(lg b) Inserção/remoção: cara! - O(b) - tem que reorganizar os registros na ordem Modificação: cara! - O(b) – principalmente se for na chave 9 Organização indexada Blocos de dados: em cada bloco os registros são ordenados pela chave Índice primário: blocos de índices ORDENADOS (pelo campo k) contendo registros de tamanho fixo com os campos <k,b>, sendo k a chave (primária) do primeiro registro (âncora) do bloco apontado por b O índice é ordenado pelo campo k Qual a vantagem? Índice tem bi blocos, sendo bi << b (cada entrada é menor que um registro, e há só uma entrada por bloco) → busca binária no índice é muito mais rápida!!! O(lg bi) Blocos de dados Blocos do índice k b 10 11 Organização indexada Problema: inserção / remoção Altera a posição em disco de vários registros → altera âncora de vários blocos → altera várias entradas do índice primário Formas de contornar o problema: Remoção por bits de validade Usar um arquivo desordenado de overflow (para as inserções, se necessário) Ou uma lista ligada de overflow (os registros do bloco e da lista podem ser ordenados para melhorar a busca) 12 Aula de hoje Dá para melhorar? O que dá para fazer se o arquivo é muito grande e o próprio índice ficou grande (com muitos blocos)? 13 Aula de hoje Dá para melhorar? O que dá para fazer se o arquivo é muito grande e o próprio índice ficou grande (com muitos blocos)? – ÍNDICE DO ÍNDICE!!! 14 Organização indexada multiníveis Nível 1: arquivo de índices para os dados Nível 2: arquivo de índices para o arquivo de índices nível 1 Se no nível 2 precisar de mais de um bloco, criar nível 3! …. 15 16 Organização indexada multiníveis Nível 1: arquivo de índices para os dados Nível 2: arquivo de índices para o arquivo de índices nível 1 Se no nível 2 precisar de mais de um bloco, criar nível 3! …. Busca: binária em cada nível (rápida!) - O(t) - precisa acessar t blocos, sendo t o número de níveis t = ceil(logfbi r1), fbi = nr de registros que cabem em um bloco de índice (fator de blocagem) r1 = nr total de registros de índice no nível 1 17 Organização indexada multiníveis Nível 1: arquivo de índices para os dados Nível 2: arquivo de índices para o arquivo de índices nível 1 Se no nível 2 precisar de mais de um bloco, criar nível 3! …. Busca: binária em cada nível (rápida!) - O(t) - precisa acessar t blocos, sendo t o número de níveis t = ceil(logfbi r1), fbi = nr de registros que cabem em um bloco de índice (fator de blocagem) r1 = nr total de registros de índice no nível 1 18 Organização indexada multiníveis Nível 1: arquivo de índices para os dados Nível 2: arquivo de índices para o arquivo de índices nível 1 Se no nível 2 precisar de mais de um bloco, criar nível 3! …. Busca: binária em cada nível (rápida!) - O(t) - precisa acessar t blocos, sendo t o número de níveis t = ceil(logfbi r1), fbi = nr de registros que cabem em um bloco de índice (fator de blocagem) r1 = nr total de registros de índice no nível 1 19 Organização indexada multiníveis Inserção / remoção: ? 20 Organização indexada multiníveis Inserção / remoção: cada vez mais complicado!!! Posso ter que alterar tudo! 21 Organização indexada multiníveis Inserção / remoção: cada vez mais complicado!!! Posso ter que alterar tudo! O que fazer??? Como ter uma busca eficiente mas permitir uma inserção e remoção razoável? 22 Lembrando de AED 1... Busca eficiente sem gastar memória: 23 Lembrando de AED 1... Busca eficiente sem gastar memória: Busca binária (em um vetor) Mas o problema era justamente inserção / deleção Qual era a alternativa de continuar fazendo busca binária mas permitir dinamismo de inserção / remoção? 24 Lembrando de AED 1... Busca eficiente sem gastar memória: Busca binária (em um vetor) Mas o problema era justamente inserção / deleção Qual era a alternativa de continuar fazendo busca binária mas permitir dinamismo de inserção / remoção? Árvores Binárias de Busca!!!! 25 Lembrando de AED 1... Busca binária (em um vetor): -4, 2, 3, 5, 19, 21, 25 Árvores Binárias de Busca: IMPLEMENTAÇÃO ? 26 Lembrando de AED 1... Busca binária (em um vetor): -4, 2, 3, 5, 19, 21, 25 Árvores Binárias de Busca: 27 Podemos pensar em algo semelhante para melhorar o dinamismo dos índices múltiníveis? 28 Podemos pensar em algo semelhante para melhorar o dinamismo dos índices múltiníveis? Árvores de busca n+1-árias! N = quantos registros são representados em um nó (bloco) da árvore, cada registro com uma chave ki N+1 ponteiros para nós filhos contendo registros com chaves em cada intervalo O segredo será mantê-las balanceadas! 29 ÁRVORES B !!! Registros organizados pela árvore, assim como na árvore binária de busca Logo, se a chave é única, não há repetição de valores Abaixo é representada só a chave para simplificar a figura, mas na verdade deve conter, para cada chave ki, o resto do registro (demais dados daquele item) ou um ponteiro pi para o registro (ki, pi) 30 ÁRVORES B+ Nós internos (de índices) Nós folhas (de dados) Variação da árvore B, na qual: os nós internos armazenam apenas os índices (ponteiros de filhos e chaves) as folhas armazenam os registros de dados (conectadas da esquerda para a direita, permitindo acesso sequencial ordenado mais eficiente) Blocagem menor (cabem mais registros nos nós internos → altura menor) 31 Árvore B Clássica Vamos começar estudando a árvore B clássica, depois fica fácil adaptar para a árvoreB+ 32 Árvore B - Definição 33 Árvore B - Definição 34 Árvore B - Definição chaves 35 Árvore B - Observação 36 Árvore B – altura máxima 37 Operações Básicas em Árvores B 38 39 o nó x raiz 40 Inserção em árvore B Ex: Como inserir o nó “O” nesta árvore (t = 4)? As inserções ocorrem sempre nas folhas 41 Inserção em árvore B Ex: Como inserir o nó “O” nesta árvore (t = 4)? Antes, precisa resolver o problema do nó cheio... As inserções ocorrem sempre nas folhas 42 Inserção em árvore B Ex: Como inserir o nó “O” nesta árvore (t = 4)? Antes, precisa resolver o problema do nó cheio... As inserções ocorrem sempre nas folhas 43 Inserção em árvore B O que aconteceria se o nó pai também estiver cheio? Teria que dividir também o pai, o que poderia causar subdivisões em cascata Todo nó teria que guardar ponteiros para o nó pai Aumentar o conteúdo de um nó → diminui o fator de blocagem → diminui o fator de ramificação → aumenta a altura da árvore Além disso (e principalmente), as subdivisões podem alterar em qual nó o registro deve ser armazenado (teria que buscar novamente o local da inserção) Então uma solução é, durante a busca da localização de inserção do nó, no caminho da raiz até uma folha, se achar um nó filho (a ser seguido) cheio, já o subdivide Vamos assumir que o nó atual (pai do nó cheio) não é cheio, a menos da raiz que deve ser tratada separadamente 0 2 4 6 8 10 20 12 14 Ex: inserção do “5” 44 Inserção em árvore B O que aconteceria se o nó pai também estiver cheio? Teria que dividir também o pai, o que poderia causar subdivisões em cascata Todo nó teria que guardar ponteiros para o nó pai Aumentar o conteúdo de um nó → diminui o fator de blocagem → diminui o fator de ramificação → aumenta a altura da árvore Além disso (e principalmente), as subdivisões podem alterar em qual nó o registro deve ser armazenado (teria que buscar novamente o local da inserção) Então uma solução é, durante a busca da localização de inserção do nó, no caminho da raiz até uma folha, se achar um nó filho (a ser seguido) cheio, já o subdivide Vamos assumir que o nó atual (pai do nó cheio) não é cheio, a menos da raiz que deve ser tratada separadamente 45 Exemplo Inserção t = 3 46 Exemplo Inserção t = 3 47 Exemplo Inserção t = 3 48 Exemplo Inserção t = 3 49 Exemplo Inserção t = 3 50 Exemplo Inserção t = 3 51 Exemplo Inserção t = 3 52 Exemplo Inserção t = 3 53 54 O que precisa fazer? 55 O que precisa fazer? Aloca e inicializa z Ajusta y Ajusta x 56 Aloca e inicializa z 57 Aloca e inicializa z 58 Aloca e inicializa z Ajusta y 59 Aloca e inicializa z Ajusta y 60 Aloca e inicializa z Ajusta y Ajusta x 61 Aloca e inicializa z Ajusta y Ajusta x 62 Aloca e inicializa z Ajusta y Ajusta x Note que assume-se que as chaves e filhos começam na posição 1 !!! 63 COMPLEXIDADE: 64 COMPLEXIDADE: Acessos ao disco: O(1) CPU: O(t) 65 66 Não preciso escrever s no disco pois isso já será feito no B-Tree-Split-Child 67 68 COMPLEXIDADE: Acessos ao disco: O(h) = O(lgt b) CPU: O(t*h) = O(t lgt b) 69 Não preciso escrever s no disco pois isso já será feito no B-Tree-Split-Child COMPLEXIDADE: Acessos ao disco: O(h) = O(lgt b) CPU: O(t*h) = O(t lgt b) 70 Remoção em árvores B x 71 Remoção em árvores B x y 72 Remoção em árvores B x x y y 73 Remoção em árvores B 74 Remoção em árvores B x y z 75 Remoção em árvores B x x y y z 76 Remoção em árvores B x ci[x] Deletar B: 77 Remoção em árvores B Algum problema? x ci[x] Deletar B: 78 Remoção em árvores B Algum problema? Se ci[x] tem o nr mínimo de chaves, se tiver que deletar desse nó vai dar problema... x ci[x] Deletar B: 79 Remoção em árvores B x ci[x] Deletar B: 80 Remoção em árvores B x ci[x] Deletar B: 81 x ci[x] 82 x ci[x] 83 Remoção em árvores B x 84 Remoção em árvores B x x (pelos procedimentos anteriores, já sei que o nó x tem pelo menos t chaves) 85 Remoção em árvores B Atenção quando um dos nós for a raiz: Ela pode ter menos do que t-1 chaves Se ficar com zero chaves precisa desalocar o bloco e atualizar quem é a nova raiz. Precisa de uma camada extra sobre a chamada da deleção: 86 Remoção em árvores B B-Tree-Delete-From-Root(T, k){ r ← raiz[T]; se (n[r] = 0) retorna; senão B-Tree-Delete(r,k); se (n[r] = 0 E (! leave[r]){ raiz[T] ← c1[r]; desaloca(r); } } 87 Remoção em árvores B Exercício: IMPLEMENTEM EM CASA!!!! Pode cair na prova P3…. 88 Comentários sobre árvores B+ 89 ÁRVORES B+ Nós internos (de índices) Nós folhas (de dados) Variação da árvore B, na qual: os nós internos armazenam apenas os índices (ponteiros de filhos e chaves) as folhas armazenam os registros de dados (conectadas da esquerda para a direita, permitindo acesso sequencial ordenado mais eficiente) Blocagem menor (cabem mais registros nos nós internos → altura menor) 90 Comentários sobre árvores B+ Adaptações dos algoritmos: Busca: tem sempre que descer às folhas Inserção: Split : mediana de uma folha é COPIADA para o pai Mediada de um nó interno é MOVIDO para o pai Remoção: nas folhas Se k (chave a ser removida) ocorrer em um nó interno, o valor deve ser substituído pelo valor predecessor nas folhas 91 Referências Livro do Cormen: cap 18 (3a ed.) Sobre árvores B+: SILBERSCHATZ A. et al. Database System Concepts. 6th ed. Ed. McGrawHill. Seção 11.3 Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44 Slide 45 Slide 46 Slide 47 Slide 48 Slide 49 Slide 50 Slide 51 Slide 52 Slide 53 Slide 54 Slide 55 Slide 56 Slide 57 Slide 58 Slide 59 Slide 60 Slide 61 Slide 62 Slide 63 Slide 64 Slide 65 Slide 66 Slide 67 Slide 68 Slide 69 Slide 70 Slide 71 Slide 72 Slide 73 Slide 74 Slide 75 Slide 76 Slide 77 Slide 78 Slide 79 Slide 80 Slide 81 Slide 82 Slide 83 Slide 84 Slide 85 Slide 86 Slide 87 Slide 88 Slide 89 Slide 90 Slide 91
Compartilhar