Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Algoritmos B-Tree e B+Tree

Apresentação do tema Algoritmos de bancos de dados B-Tree e B+Tree no PostgreSQL para qualificação do trabalho de conclusão de curso em Análise e Desenvolvimento de Sistemas na Fatec Ourinhos.
by

Lucas Costa

on 28 May 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmos B-Tree e B+Tree

Introdução
Problema
: Quão eficientes são as estruturas de indexação B-Tree e B+-Tree utilizadas pelos SGBDs?


Objetivo
: Implementar o algoritmo B+-Tree no processo de consultas do PostgreSQL


Justificativa
: Promover a recuperação dos dados no menor tempo possível


B-Tree
Uma árvore de pesquisa, quando possui mais de um registro por nó ela deixa de ser binaria e passa a ser uma B-Tree.

Principal característica

Mecanismos:
Algoritmo de busca
Algoritmo de inserção
Algoritmo de exclusão
Algoritmo de busca da B-Tree
1)Uma tabela com 10.000 linhas, procura-se a linha com elemento de número 51

2)A tabela contém 10.000 linhas e será submetido a uma pesquisa em B-Tree

3)10.000 linhas é muita coisa para pesquisar, então dividimos em 8 nós

Algoritmo de busca da B+-Tree
CENTRO PAULA SOUZA
FATEC OURINHOS
CURSO DE ANÁLISE E DESENVOLVIMENTO DE SISTEMAS

Lucas Bueno da Costa


Reduz número de blocos acessados

O algoritmo percorre a árvore com base no valor de entrada

Cada nó interno de uma B+-Tree possui um ponteiro para o próximo nó, com a finalidade de orientar a pesquisa




Algoritmo de inserção da B+-Tree
É inserido recursivamente a entrada chamando o algoritmo de inserção no nó filho apropriado

Se o nó está cheio e deve ser dividido, então é criado um ponteiro no nó pai indicando o nó filha criado

A árvore em média se mantém com 69% cheia

Árvore balanceada B+-Tree
Implementado quando se trata de um índice multinível dinâmico, e é derivada da B-Tree.

Característica principal
Diferença entre B-Tree e B+-Tree
Valores repetidos
Todos os nós folha estão no mesmo nível
ALGORITMOS DE INDEXAÇÃO DE BANCO DE DADOS
B-TREE E B+-TREE NO POSTGRESQL

Será considerado nessa apresentação:
Introdução (Problema,objetivo e justificativa)
Introdução ao SGBD PostgreSQL
Estrutura do algoritmo B-Tree
Estrutura do algoritmo B+-Tree
Conclusão
Referências
Definição de termos
Raiz
Nodos descendentes
Subárvore
Grau de árvore
Folha ou terminal
Árvore balanceada

Processamento de consultas no PostgreSQL
Referências
DROZDEK, A. Estrutura de dados e algoritmos em C++. São Paulo: Cengage Learning, 2010.

EDELWEISS, N. GALANTE, R. Estrutura de dados. Porto Alegre: Bookman, 2009.

ELMASRI, R; NAVATHE, S. B. Sistemas de Banco de Dados. 6 ed. São Paulo: Pearson Addison Wesley, 2011.

GUTTOSKI, P. B; Otimização de Consultas no Postgresql Utilizando o Algoritmo de Kruskal. 2006. 105f. Dissertação (Mestrado no Programa de Pós-Graduação em Informática) – Universidade Federal do Paraná, Curitiba.

RAMAKRISHNAN, R.; GEHRKE, J. Sistemas de Gerenciamento de Banco de Dados. 3 ed. São Paulo: McGraw-Hill, 2008.

STONEBRAKER, M; HANSON, E; HONG, C. H. The design of the postgres rules system. Proc. IEEE Conference on Data Engineering, 1987.

STONEBRAKER, M; HEARST, M; POTAMIANOS, S. A commentary on the postgres rules system. SIGMOD Record, 1989.

ZIVIANI, N. Projeto de algoritmos: com implementações em Pascal e C. 3 ed. São Paulo: Cengage Learning, 2011.

Algoritmo de exclusão da B+-Tree
O algoritmo recebe uma entrada, encontra o nó folha onde ela está e a exclui

Se o nó estiver com ocupação mínima, deverá haver redistribuição com um irmão adjacente

A exclusão é simplesmente a remoção da chave no nó folha, porém pode haver redistribuição e atualização do valor do nó pai
Metodologia
Ambiente

Participantes

Materiais e instrumentos
Dev-C++
PostregreSQL - v. 9.3
Windows 7 e Linux
Dúvidas?
Full transcript