teste

Páginas: 5 (1204 palavras) Publicado: 10 de dezembro de 2014
Árvores B

Prof. Flávio Humberto Cabral Nunes

Conteúdo
1.
2.
3.
4.
5.
6.

Introdução
Busca
Inserção
Remoção
B*
B+
Capítulo: 8 (APOSTILA).

Introdução
Em muitas aplicações, a tabela considerada
é muito grande


As chaves não podem ser mantidas todas na
memória principal

Assim, a tabela precisa ser mantida em
memória secundária


Alto custo de acesso Introdução
Necessidade de uma estrutura que minimize
o tempo de acesso na tabela para




Buscas
Inserções
Remoções

Árvores B
As árvores B permitem manter mais de uma
chave em cada nó da estrutura
Proporciona uma organização de ponteiros
de forma que as operações são executadas
rapidamente
Sua construção assegura que todas as
folhas se encontram no mesmo nível, não
importando aordem de entrada dos dados

Árvores B
Largamente utilizadas como forma de
armazenamento em memória secundária
Diversos sistemas comerciais de banco de
dados utilizam árvores B

Definição
Todo nó x tem os seguintes campos






n[x]: número de chaves atualmente
armazenadas no nó x
N[x] chaves de modo que chave1 chave2 ...
chaven[x]
folha[x]: booleano indicando se o nó x éfolha
ou não

Definição
Cada nó interno contém n[x] + 1 ponteiros
c1[x], c2[x], ..., cn[x]+1[x] para seus filhos
Nós folhas não têm filhos


Campos ci são indefinidos

As chaves chavei[x] separam os intervalos
de chaves armazenadas em cada sub-árvore



Se ki é qualquer chave na sub-árvore
k1 chave1[x] k2 chave2[x] ... chaven[x][x]
kn[x]+1

Definição
Toda folha tem a mesmaaltura
O número de chaves em cada nó é limitado




Mínimo: m chaves
Máximo: 2m chaves
m 2, exceto para raíz onde m pode ser 1

Representação de Uma Página
Número de chaves

n p1 k1 dados r1 p2 k2 dados r2 . . . p2m k2m dados r2m p2m+1

k1 dados

k2 dados

k2m dados

Representação Simplificada

k1
p1

k2
p2

.....
p3

k2m

p2m

P2m + 1

Exemplo
22 5830 36

9 17

4 8

12 13

18

25 27

32

70

40

60 61

72

Busca
Buscar uma chave x em uma árvore B
Semelhante ao utilizado para árvore binária
de busca
O mesmo caminhamento é realizado




Acrescenta-se testes relativos às chaves
existentes de cada página
Pesquisa sequencial ou binária dentro de uma
página

Busca - Exemplo
22 58

30 36

9 17

4 812 13

18

25 27

32

70

40

60 61

72

Inserção
Adicionar uma nova chave x a uma árvore B
Primeiro é feito uma busca




Se a chave já existir, ela não pode ser incluída
novamente
Se não existir e houver espaço suficiente na
folha, basta adicioná-la garantindo que estejam
ordenadas

Inserção
Caso a chave não exista e não exista
espaço suficiente na folha

––

A folha é dividida em duas folhas
A chave do meio é promovida para a página pai
Se não houver espaço na página pai, o processo
é repetido para esse nó

Inserção – Exemplo
Árvore B de ordem 2 (m = 2)
Inserir registro 14
10

3489

16 20 25 29

Inserção – Exemplo
Árvore B de ordem 2 (m = 2)
Inserir registro 14
10

3489

Página excedeu o limite.
Limite = 2m = 4

14 1620 25 29

Inserção – Exemplo
Árvore B de ordem 2 (m = 2)
Inserir registro 14
10

3489

14 16 20 25 29

Inserção – Exemplo
Árvore B de ordem 2 (m = 2)
Inserir registro 14
10
20
3489

14 16

25 29

Inserção – Exemplo
Árvore B de ordem 2 (m = 2)
Inserir registro 14
10 20

3489

14 16

25 29

Inserção
No pior caso, o processo de divisão pode
propagar-se até araiz da árvore.
Neste caso, a árvore aumenta sua altura de
um nível
Uma árvore B somente aumenta sua altura
com a divisão da raiz

Remoção
Consiste em retirar uma chave da árvore
Quando a página que contém o registro a
ser retirado é uma página folha, a operação
é simples

Remoção
Árvore B de ordem 2 (m = 2)
Remover chave 8
10 20

3489

14 16

25 29

Remoção
Árvore B de...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Teste teste teste teste
  • teste teste teste teste
  • TESTE TESTE
  • teste de teste
  • Teste do teste
  • Teste teste
  • teste teste
  • Teste teste

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!