Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Hoje Estamos falando sobre uma variação da Arvore B
- CONCEITO:
- Arvore B*, é uma variação da Arvore B.
- A diferença é que apesar de voce manter todas as caracteristicas iguais, voce só armazena chaves nas folhas.
- Então os indices que ficavam nos nós não folhas, eles são cópias das chaves que estão em uma folha filha.
- A parte confusa é que se eu remover da folha essa chave, o indice permance lá, portanto encontrar o indice não necessáriamente indica que a chave ainda está lá.
- Outro diferencial é que há um ponteiro entre cada folha apontando para a próxima folha!, isso agiliza muito o acesso sequencial! =]
- Eu cheguei atrazado portando não pude anotar as difereças no processo de inserção, remoção e etc. infelizmente.
- --------------------------------------------------------------------------------------------------------------------
- Acesso concorrente:
- Uma pagina segura é se em uma inserção ela tem menos de 2m chaves, e se em uma remoção ela tem mais de m chaves.
- Existem 2 tipos de travamento:
- Travamento de leitura, que permite leituras mas nao inserções e remoções
- E travamento exclusivo que não permite que os outros processos nem vejam a pagina.
- Para uma leitura, voce deve colocar um travamento de leitura na raiz.
- E então realize sua busca, a cada vez que voce caminha para um filho libere o travamento do pai e continue e trave o filho, até achar a chave, le-la e destrava-la.
- Para escrita trave a raiz exclusivamente, e vá caminhando pelos nós ate encontrar a folha, e trave todas pelo caminho
- Então se encontrar a chave, verifique se sua pagina é segura, se ela for, libere os travamentos das demais.
- --------------------------------------------------------------------------------------------------------------------
- Considerações praticas a respeito da arvore B:
- Estrutura de fácil manutenção eficiete e versátil, afinal ela está sempre balanceada, e é confiável.
- Decore isso:
- Formula1 <= altura_da_arvore <= formula2
- // Ps: seria mais esperto decorar isso depois de eu descorbrir as formulas xP, pq eu não copiei elas a tempo =P
- // Nota da Professora: ha uma probabilidade maior de não criar-se uma nova partição durante a inserção de um registro do que de criar-se um.
- para M maiores, a chance de nao se criar nova particção vai pra 99%.
- O uso de espaço médio na arvore é 69% do tamanho total.
- // Nota minha: essas notas da professora vao cair em prova!
- --------------------------------------------------------------------------------------------------------------------
- Pagina segura mais profunda:
- A ideia é que voce só precisa travar da pagina segura mais profunda pra baixo, quando estiver realiando uma inserçào ou remoção.
- Porem isso não ajuda muito, pois quase sempre a pagina segura mais profunda vai ser a folha mesmo, então da na mesma do algoritimo que falei antes.
- --------------------------------------------------------------------------------------------------------------------
- CONCEITO:
- Tecnica de transbordamento da arvore B
- Sabe quando voce está realizando uma inserção e voce precisa duplicar uma pagina?
- Bem a ideia do transbordamento é ao invés de duplicar ela de vez voce pega uma chave da pagina cheia e joga para a irma a direita ou a esquerda.
- Esse efeito gera 83% de aproveitamendo do espaço de uma arvore B
- // A professora falou que se isso for cair em prova vai ser na pergunta: "pense uma otimização para a operação de inserção da arvore B"
Advertisement
Add Comment
Please, Sign In to add comment
