of 51 /51
Pesquisa em Memória Secundária Última alteração: 31 de Agosto de 2010 * Transparências elaboradas por Wagner Meira Jr, Flávia Peligrinelli Ribeiro, Israel Guerra, Nívio Ziviani e Charles Ornelas Almeida

Pesquisa em Memória Secundária - dcc.ufmg.br · Pesquisa em Memória ... 6.1 Modelo de Computação para Memória Secundária 6.1.1 Memória Virtual 6.1.2 Implementação de um

  • Author
    lamtram

  • View
    216

  • Download
    0

Embed Size (px)

Text of Pesquisa em Memória Secundária - dcc.ufmg.br · Pesquisa em Memória ... 6.1 Modelo de...

  • Pesquisa em Memria Secundria

    ltima alterao: 31 de Agosto de 2010

    Transparncias elaboradas por Wagner Meira Jr, Flvia Peligrinelli Ribeiro, Israel Guerra, Nvio Ziviani e Charles OrnelasAlmeida

  • Projeto de Algoritmos Cap.1 Introduo 1

    Contedo do Captulo

    6.1 Modelo de Computao para Memria Secundria

    6.1.1 Memria Virtual

    6.1.2 Implementao de um Sistema de Paginao

    6.2 Acesso Sequencial Indexado

    6.2.1 Discos pticos de Apenas-Leitura

    6.3 rvores de Pesquisa

    6.3.1 rvores B

    6.3.2 rvores B

    6.3.3 Acesso Concorrente em rvores B

    6.3.4 Consideraes Prticas

  • Projeto de Algoritmos Cap.1 Introduo 2

    Introduo

    Pesquisa em memria secundria: arquivos contm mais registros do quea memria interna pode armazenar.

    Custo para acessar um registro algumas ordens de grandeza maior do queo custo de processamento na memria primria.

    Medida de complexidade: custo de trasferir dados entre a memria principale secundria (minimizar o nmero de transferncias).

    Memrias secundrias: apenas um registro pode ser acessado em um dadomomento (acesso seqencial).

    Memrias primrias: acesso a qualquer registro de um arquivo a um custouniforme (acesso direto).

    O aspecto sistema de computao importante.

    As caractersticas da arquitetura e do sistema operacional da mquinatornam os mtodos de pesquisa dependentes de parmetros que afetamseus desempenhos.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1 3

    Modelo de Computao para Memria Secundria -Memria Virtual

    Normalmente implementado como uma funo do sistemaoperacional.

    Modelo de armazenamento em dois nveis, devido necessidade degrandes quantidades de memria e o alto custo da memria principal.

    Uso de uma pequena quantidade de memria principal e uma grandequantidade de memria secundria.

    Programador pode enderear grandes quantidades de dados,deixando para o sistema a responsabilidade de trasferir o dado damemria secundria para a principal.

    Boa estratgia para algoritmos com pequena localidade de referncia.

    Organizao do fluxo entre a memria principal e secundria extremamente importante.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 4

    Memria Virtual

    Organizao de fluxo transformar o endereo usado peloprogramador na localizao fsica de memria correspondente.

    Espao de Endereamento endereos usados pelo programador.

    Espao de Memria localizaes de memria no computador.

    O espao de endereamento N e o espao de memria M podem servistos como um mapeamento de endereos do tipo: f : N M .

    O mapeamento permite ao programador usar um espao deendereamento que pode ser maior que o espao de memriaprimria disponvel.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 5

    Memria Virtual: Sistema de Paginao

    O espao de endereamento dividido em pginas de tamanho igual,em geral, mltiplos de 512 Kbytes.

    A memria principal dividida em molduras de pginas de tamanhoigual.

    As molduras de pginas contm algumas pginas ativas enquanto orestante das pginas esto residentes em memria secundria(pginas inativas).

    O mecanismo possui duas funes:

    1. Mapeamento de endereos determinar qual pgina umprograma est endereando, encontrar a moldura, se existir, quecontenha a pgina.

    2. Transferncia de pginas transferir pginas da memriasecundria para a memria primria e transfer-las de volta para amemria secundria quando no esto mais sendo utilizadas.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 6

    Memria Virtual: Sistema de Paginao

    Endereamento da pgina uma parte dos bits interpretada comoum nmero de pgina e a outra parte como o nmero do byte dentroda pgina (offset).

    Mapeamento de endereos realizado atravs de uma Tabela dePginas.

    a p-sima entrada contm a localizao p da Moldura de Pginacontendo a pgina nmero p desde que esteja na memriaprincipal.

    O mapeamento de endereos : f(e) = f(p, b) = p + b, onde e oendereo do programa, p o nmero da pgina e b o nmero do byte.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 7

    Memria Virtual: Mapeamento de Endereos

    p p+ b

    Tabela_de_Pginas Pgina p

    N dapgina

    N dobyte

    Endereode

    programap b

    p = nil pgina nopresente namemria

    ?

    --

    ?

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 8

    Memria Virtual: Reposio de Pginas

    Se no houver uma moldura de pgina vazia uma pgina deverser removida da memria principal.

    Ideal remover a pgina que no ser referenciada pelo perodo detempo mais longo no futuro.

    tentamos inferir o futuro a partir do comportamento passado.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 9

    Memria Virtual: Polticas de Reposio de Pginas

    Menos Recentemente Utilizada (LRU):

    um dos algoritmos mais utilizados,

    remove a pgina menos recentemente utilizada,

    parte do princpio que o comportamento futuro deve seguir opassado recente.

    Menos Freqentemente Utilizada (LFU):

    remove a pgina menos feqentemente utilizada,

    inconveniente: uma pgina recentemente trazida da memriasecundria tem um baixo nmero de acessos e pode ser removida.

    Ordem de Chegada (FIFO):

    remove a pgina que est residente h mais tempo,

    algoritmo mais simples e barato de manter,

    desvantagem: ignora o fato de que a pgina mais antiga pode ser amais referenciada.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 10

    Memria Virtual: Poltica LRU

    Fim -

    Incio

    Pgina p

    ?

    6

    ?6

    .

    .

    .

    .

    Toda vez que uma p-gina utilizada ela removida para o fim dafila.

    A pgina que est noincio da fila a pginaLRU.

    Quando uma nova p-gina trazida da me-mria secundria eladeve ser colocada namoldura que contm apgina LRU.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.2 11

    Memria Virtual: Estrutura de Dados

    const TAMANHODAPAGINA = 512;

    ITENSPORPAGINA = 64; { TamanhodaPagina/TamanhodoItem }

    type Registro = record

    Chave: TipoChave;

    { outros componentes }

    end;

    TipoEndereco = record

    p: integer ;

    b: 1 . . ITENSPORPAGINA;

    end;

    TipoItem = record

    Reg: TipoRegistro ;

    Esq, Dir : TipoEndereco;

    end;

    TipoPagina = array [ 1 . . ITENSPORPAGINA ] of TipoItem;

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.2 12

    Memria Virtual

    Em casos em que precisamos manipular mais de um arquivo aomesmo tempo:

    A tabela de pginas para cada arquivo pode ser declaradaseparadamente.

    A fila de molduras nica cada moldura deve ter indicado oarquivo a que se refere aquela pgina.

    type TipoPagina = record

    case byte of

    0 : (Pa : TipoPaginaA) ;

    1 : (Pb : TipoPaginaB) ;

    2 : (Pc : TipoPaginaC) ;

    end;

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.2 13

    Memria Virtual

    Procedimentos para comunicao com o sistema de paginao:

    ObtemRegistro torna disponvel um registro.

    EscreveRegistro permite criar ou alterar o contedo de umregistro.

    DescarregaPaginas varre a fila de molduras para atualizar namemria secundria todas as pginas que tenham sidomodificadas.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.2 14

    Memria Virtual - Transformao do Endereo Virtual paraReal

    P2Determinaendereo

    real

    P4Recupera pgina

    da memriasecundria

    A1Tabela

    depginas

    A3Memria

    secundria

    ProgramaUsurio

    A2Filade

    molduras

    P5Grava pginana memriasecundria

    P1Consultatabela depginas

    P3Determinamoldura

    para pgina

    ?

    6

    6?

    6

    6

    --

    ?

    -

    p

    p

    pp

    p Pgina

    p

    p

    p

    Pgina

    pp

    p

    pp

    Pgina

    p

    Quadrados resulta-dos de processos ou ar-quivos.

    Retngulos proces-sos transformadores deinformao.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.2 15

    Acesso Seqencial Indexado

    Utiliza o princpio da pesquisa seqencial cada registro lidoseqencialmente at encontrar uma chave maior ou igual a chave depesquisa.

    Providncias necessrias para aumentar a eficincia:

    o arquivo deve ser mantido ordenado pelo campo chave do registro,

    um arquivo de ndices contendo pares de valores < x, p > deve sercriado, onde x representa uma chave e p representa o endereo dapgina na qual o primeiro registro contm a chave x.

    Estrutura de um arquivo seqencial indexado para um conjunto de15 registros:

    3 14 25 411 2 3 4

    3 5 7 111 14 17 20 212 25 29 32 363 41 44 484

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.2 16

    Acesso Seqencial Indexado: Disco Magntico

    Dividido em crculos concntricos (trilhas).

    Cilindro todas as trilhas verticalmente alinhadas e que possuem omesmo dimetro.

    Latncia rotacional tempo necessrio para que o incio do blococontendo o registro a ser lido passe pela cabea de leitura/gravao.

    Tempo de busca (seek time) tempo necessrio para que omecanismo de acesso desloque de uma trilha para outra (maior partedo custo para acessar dados).

    Acesso seqencial indexado = acesso indexado + organizaoseqencial,

    Aproveitando caractersticas do disco magntico e procurandominimizar o nmero de deslocamentos do mecanismo de acesso esquema de ndices de cilindros e de pginas.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.2 17

    Acesso Seqencial Indexado: Discos ticos deApenas-Leitura (CD-ROM)

    Grande capacidade de armazenamento (600 MB) e baixo custo.

    Informao armazenada esttica.

    A eficincia na recuperao dos dados afetada pela localizao dos dadosno disco e pela seqncia com que so acessados.

    Velocidade linear constante trilhas possuem capacidade varivel e tempode latncia rotacional varia de trilha para trilha.

    A trilha tem forma de uma espiral contnua.

    Tempo de busca: acesso a trilhas mais distantes demanda mais tempo queno disco magntico. H necessidade de deslocamento do mecanismo deacesso e mudanas na rotao do disco.

    Varredura esttica: acessa conjunto de trilhas vizinhas sem deslocarmecanismo de leitura.

    Estrutura seqencial implementada mantendo-se um ndice de cilindros namemria principal.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 18

    rvores B

    rvores n-rias: mais de um registro por nodo.

    Em uma rvore B de ordem m:

    pgina raiz: 1 e 2m registros.

    demais pginas: no mnimo m registros e m+ 1 descendentes e nomximo 2m registros e 2m+ 1 descendentes.

    pginas folhas: aparecem todas no mesmo nvel.

    Registros em ordem crescente da esquerda para a direita.

    Extenso natural da rvore binria de pesquisa.

    rvore B de ordem m = 2 com trs nveis:

    hhhhhh

    30

    10 20

    ````

    40 50 ````

    3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 19

    rvores B - TAD Dicionrio

    Estrutura de Dados:

    type TipoRegistro = record

    Chave: TipoChave;

    {outros componentes}

    end;

    TipoApontador = ^TipoPagina;

    TipoPagina = record

    n: 0 . .mm;

    r : array [ 1 . .mm ] of TipoRegistro ;

    p: array [ 0 . .mm ] of TipoApontador

    end;

    TipoDicionario = TipoApontador;

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 20

    rvores B - TAD Dicionrio

    Operaes:

    Inicializa

    procedure In ic ial iza (var Dicionario : TipoDicionario ) ;

    begin

    Dicionario := n i l ;

    end; { Inic ial iza }

    Pesquisa

    Insere

    Remove

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 21

    rvores B - Pesquisa

    procedure Pesquisa (var x : TipoRegistro ; Ap: TipoApontador) ;

    var i : Integer ;

    begin

    i f Ap = ni l

    then writeln ( Registro nao esta presente na arvore )

    else with Ap^ do

    begin

    i := 1;

    while ( i < n) and (x.Chave > r [ i ] .Chave) do i := i + 1;

    i f x.Chave = r [ i ] .Chave

    then x := r [ i ]

    else i f x.Chave < r [ i ] .Chave

    then Pesquisa (x , p[ i1])

    else Pesquisa (x , p[ i ] )

    end;

    end; { Pesquisa }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 22

    rvores B - Insero

    1. Localizar a pgina apropriada aonde o regisro deve ser inserido.

    2. Se o registro a ser inserido encontra uma pgina com menos de 2mregistros, o processo de insero fica limitado pgina.

    3. Se o registro a ser inserido encontra uma pgina cheia, criada umanova pgina, no caso da pgina pai estar cheia o processo de divisose propaga.

    Exemplo: Inserindo o registro com chave 14.

    1 10

    `````

    2 33 4 8 9 16 20 25 29 (a)

    1 10 20

    `````

    2 3 43 4 8 9 14 16 25 29 (b)

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 23

    rvores B - Insero

    Exemplo de insero das chaves: 20, 10, 40, 50, 30, 55, 3, 11, 4, 28, 36,33, 52, 17, 25, 13, 45, 9, 43, 8 e 48

    (a) 20

    (b) 30

    PPP

    10 20 40 50

    (c) 10 20 30 40

    ((((((( PPP

    hhhhhhh

    3 4 11 13 17 25 28 33 36 50 52 55

    hhhhhh

    (d) 30

    10 20

    ````

    40 50 ````

    3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 24

    rvores B - Primeiro refinamento do algoritmo Insere

    procedure Insere (Reg: Registro ; var Ap: Apontador) ;

    procedure Ins (Reg: Registro ; Ap: Apontador ; var Cresceu: Boolean;var RegRetorno: Registro ; var ApRetorno: Apontador) ;

    var i : integer ;begin

    i f Ap = ni lthen begin

    Cresceu := true ;Atribui Reg a RegRetorno;Atribui n i l a ApRetorno;end

    else with Ap^ dobegini := 1;while ( i < n) and (x.Chave > r [ i ] .Chave) do i := i + 1;i f x.Chave = r [ i ] .Chavethen writeln ( Erro : Registro ja esta presente na arvore )else i f x.Chave < r [ i ] .Chave

    then Ins (x , p[ i 1], Cresceu, RegRetorno, ApRetorno)else Ins (x , p[ i ] , Cresceu, RegRetorno, ApRetorno) ;

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 25

    rvores B - Primeiro refinamento do algoritmo Insere

    i f Cresceu then i f (Numero de registros em Ap) < mmthen Insere na pagina Ap e Cresceu := falseelse begin { Overflow : pagina tem que ser dividida }

    Cria nova pagina ApTemp;Transfere metade dos registros de Ap para ApTemp;Atribui registro do meio a RegRetorno;Atribui ApTemp a ApRetorno;end;

    end;end;

    begin { Insere}Ins (Reg, Ap, Cresceu, RegRetorno, ApRetorno) ;i f Cresceu then Cria nova pagina raiz para RegRetorno e ApRetorno;end;

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 26

    rvores B - Procedimento InsereNaPgina

    procedure InsereNaPagina (Ap: TipoApontador ; Reg: TipoRegistro ; ApDir : TipoApontador) ;var NaoAchouPosicao: Boolean;

    k : Integer ;beginwith Ap^ do

    begink := n;NaoAchouPosicao := k > 0;while NaoAchouPosicao do

    i f Reg.Chave < r [k ] .Chavethen begin

    r [k+1] := r [k ] ; p[k+1] := p[k ] ;k := k 1;i f k < 1 then NaoAchouPosicao := false ;end

    else NaoAchouPosicao := false ;r [k+1] := Reg; p[k+1] := ApDir;n := n + 1;end;

    end; { InsereNaPagina }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 27

    rvores B - Refinamento final do algoritmo Insereprocedure Insere (Reg: TipoRegistro ; var Ap: TipoApontador) ;var Cresceu: Boolean; RegRetorno: TipoRegistro ;

    ApRetorno, ApTemp: TipoApontador;

    procedure Ins(Reg:TipoRegistro ; Ap: TipoApontador ; var Cresceu:Boolean;var RegRetorno:TipoRegistro ; var ApRetorno:TipoApontador) ;

    var i , j : Integer ; ApTemp: TipoApontador;begin

    i f Ap = ni lthen begin Cresceu := true ; RegRetorno := Reg; ApRetorno := n i l ; endelse with Ap^ do

    begini := 1;while ( i < n) and (Reg.Chave > r [ i ] .Chave) do i := i + 1;i f Reg.Chave = r [ i ] .Chavethen begin writeln ( Erro : Registro ja esta presente ) ; Cresceu:=false ; endelse begin i f Reg.Chave < r [ i ] .Chave then i := i 1;

    Ins (Reg, p[ i ] , Cresceu, RegRetorno, ApRetorno) ;i f Cresceuthen i f n < mm

    then begin { Pagina tem espaco }InsereNaPagina (Ap, RegRetorno, ApRetorno) ; Cresceu := false ;end

    { Continua na prxima transparncia }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 28

    rvores B - Refinamento final do algoritmo Insereelse begin { Overflow : Pagina tem que ser dividida }

    new (ApTemp) ;ApTemp^.n := 0; ApTemp^.p[0 ] := n i l ;i f i < M + 1then begin InsereNaPagina (ApTemp, r [mm] , p[mm ] ) ; n := n 1;

    InsereNaPagina (Ap, RegRetorno, ApRetorno)end

    else InsereNaPagina (ApTemp, RegRetorno, ApRetorno) ;for j := M + 2 to mm do

    InsereNaPagina (ApTemp, r [ j ] , p[ j ] ) ;n := M; ApTemp^.p[0 ] := p[M+1];RegRetorno := r [M+1]; ApRetorno := ApTemp;end;

    end;end;

    end; { Ins }begin Ins (Reg, Ap, Cresceu, RegRetorno, ApRetorno) ;

    i f Cresceu then begin { Arvore cresce na altura pela raiz }new (ApTemp) ; ApTemp^.n := 1;ApTemp^. r [1 ] := RegRetorno;ApTemp^.p[1 ] := ApRetorno;ApTemp^.p[0 ] := Ap; Ap := ApTempend

    end; { Insere }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 29

    rvores B - Remoo

    Pgina com o registro a ser retirado folha:

    1. retira-se o registro,

    2. se a pgina no possui pelo menos de m registros, a propriedadeda rvore B violada. Pega-se um registro emprestado da pginavizinha. Se no existir registros suficientes na pgina vizinha, asduas pginas devem ser fundidas em uma s.

    Pagina com o registro no folha:

    1. o registro a ser retirado deve ser primeiramente substitudo por umregistro contendo uma chave adjacente.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 30

    rvores B - Remoo

    Exemplo: Retirando a chave 3.

    j4

    6 8

    HHH

    j2

    j1 [email protected]@ j5

    j7 j9TT

    1 2

    j* ,,

    j5

    j4

    j7

    6 8

    ll

    j9TT

    1 2

    j4,,

    j5AA

    j6

    j7

    j8ll

    j9AA

    (a) Pgina vizinha possui mais do que m registros

    j1

    j2,,

    j3AA

    j4

    j5

    j6ll

    j7AA

    1 2

    j* ,,

    j4

    j5

    j6ll

    j7AA

    j

    4 6

    1 2

    j5 j7TT

    (b) Pgina vizinha possui exatamente m registros

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 31

    rvores B - Remoo

    Remoo das chaves 45 30 28; 50 8 10 4 20 40 55 17 33 11 36; 3 9 52.

    (d) 13 25 43 48

    (c) 13

    PPP

    3 9 25 43 48 52

    (b) 10 25 40 50

    ((((((( PPP

    hhhhhhh

    3 4 8 9 11 13 17 20 33 36 43 48 52 55

    hhhhhh

    (a) 30

    10 20

    ````

    40 50 ````

    3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 32

    rvores B - Procedimento Retiraprocedure Ret(Ch:TipoChave;var Ap:TipoApontador;var Diminuiu:Boolean) ;

    var Ind , j : Integer ;

    procedure Reconstitui (ApPag: TipoApontador ; ApPai : TipoApontador;PosPai : Integer ; var Diminuiu : Boolean) ;

    var Aux: TipoApontador ; DispAux, j : Integer ;begin

    i f PosPai < ApPai^.nthen begin { Aux = Pagina a direita de ApPag }

    Aux := ApPai^.p[PosPai+1];DispAux := (Aux^.n M + 1) div 2;ApPag^. r [ApPag^.n+1] := ApPai^. r [PosPai+1];ApPag^.p[ApPag^.n+1] := Aux^.p[0 ] ;ApPag^.n := ApPag^.n + 1;i f DispAux > 0then begin { Existe folga : transfere de Aux para ApPag }

    for j := 1 to DispAux 1 doInsereNaPagina (ApPag, Aux^. r [ j ] , Aux^.p[ j ] ) ;ApPai^. r [PosPai+1] := Aux^. r [DispAux] ;Aux^.n := Aux^.n DispAux;for j := 1 to Aux^.n do Aux^. r [ j ]:=Aux^. r [ j+DispAux] ;for j := 0 to Aux^.n do Aux^.p[ j ]:=Aux^.p[ j+DispAux] ;Diminuiu := falseend

    { Continua na prxima transparncia }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 33

    rvores B - Procedimento Retiraelse begin { Fusao: intercala Aux em ApPag e libera Aux }

    for j := 1 to M doInsereNaPagina (ApPag, Aux^. r [ j ] , Aux^.p[ j ] ) ;

    dispose (Aux) ;for j := PosPai + 1 to ApPai^.n 1 do with ApPai^ do

    beginr [ j ] := r [ j +1]; p[ j ] := p[ j +1]end;

    ApPai^.n := ApPai^.n 1;i f ApPai^.n >= Mthen Diminuiu := false ;end

    endelse begin { Aux = Pagina a esquerda de ApPag }

    Aux := ApPai^.p[PosPai1];DispAux := (Aux^.n M + 1) div 2;for j := ApPag^.n downto 1 do

    ApPag^. r [ j +1] := ApPag^. r [ j ] ;ApPag^. r [1 ] := ApPai^. r [PosPai ] ;for j := ApPag^.n downto 0 do

    ApPag^.p[ j +1] := ApPag^.p[ j ] ;ApPag^.n := ApPag^.n + 1;

    { Continua na prxima transparncia }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 34

    rvores B - Procedimento Retira

    i f DispAux > 0then begin { Existe folga : transfere de Aux para ApPag }

    for j := 1 to DispAux 1 do with Aux^ doInsereNaPagina (ApPag, r [Aux^.n+1j ] , p[n+1j ] ) ;

    ApPag^.p[0 ] := Aux^.p[Aux^.n+1DispAux] ;ApPai^. r [PosPai] := Aux^. r [Aux^.n+1DispAux] ;Aux^.n := Aux^.n DispAux;Diminuiu := falseend

    else begin { Fusao: intercala ApPag em Aux e libera ApPag }for j := 1 to M do

    InsereNaPagina (Aux, ApPag^. r [ j ] , ApPag^.p[ j ] ) ;dispose (ApPag) ;ApPai^.n := ApPai^.n 1;i f ApPai^.n >= M then Diminuiu := false ;end;

    end;end;

    end; { Reconstitui }{ Continua na prxima transparncia }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 35

    rvores B - Procedimento Retira

    procedure Antecessor (Ap: TipoApontador ; Ind : Integer ;ApPai : TipoApontador;var Diminuiu : Boolean) ;

    beginwith ApPai^ do

    begini f p[n] n i lthen begin

    Antecessor (Ap, Ind , p[n] , Diminuiu ) ;i f Diminuiu then Reconstitui (p[n] , ApPai, n, Diminuiu ) ;end

    else beginAp^. r [ Ind ] := r [n ] ; n := n 1;Diminuiu := n < M;end;

    endend; { Antecessor }

    { Continua na prxima transparncia }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 36

    rvores B - Procedimento Retirabegin { Ret }

    i f Ap = ni lthen begin writeln ( Erro : registro nao esta na arvore ) ; Diminuiu := false ; endelse with Ap^ do

    beginInd := 1;while ( Ind < n) and (Ch > r [ Ind ] .Chave) do Ind := Ind + 1;i f Ch = r [ Ind ] .Chavethen i f p[ Ind1] = n i l

    then begin { Pagina folha }n := n 1; Diminuiu := n < M;for j := Ind to n do

    beginr [ j ] := r [ j +1];p[ j ] := p[ j +1];end;

    endelse begin { Pagina nao e folha : trocar com antecessor }

    Antecessor (Ap, Ind , p[ Ind1], Diminuiu ) ;i f Diminuiu then Reconstitui (p[ Ind1], Ap, Ind1, Diminuiu ) ;end

    { Continua na prxima transparncia }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.1 37

    rvores B - Procedimento Retira

    else begini f Ch > r [ Ind ] .Chave then Ind := Ind + 1;Ret (Ch, p[ Ind1], Diminuiu ) ;i f Diminuiuthen Reconstitui (p[ Ind1], Ap, Ind1, Diminuiu ) ;end

    endend; { Ret }

    begin { Retira }Ret (Ch, Ap, Diminuiu ) ;i f Diminuiu and (Ap^.n = 0)then begin { Arvore diminui na altura }

    Aux := Ap; Ap := Aux^.p[0 ] ;dispose (Aux) ;end

    end; { Retira }

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.2 38

    rvores B* - TAD Dicionrio

    Estrutura de Dados:

    typeTipoRegistro = record

    Chave: TipoChave;{ outros componentes }

    end;TipoApontador = ^TipoPagina;TipoIntExt = ( Interna , Externa) ;TipoPagina = record

    case Pt : TipoIntExt ofInterna : ( ni : 0 . .mm;

    r i : array [ 1 . .mm ] of TipoChave;pi : array [ 0 . .mm ] of TipoApontador) ;

    Externa : (ne: 0 . .mm2;re : array [ 1 . .mm2 ] of TipoRegistro ) ;

    end;TipoDicionario = TipoApontador;

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.2 39

    rvores B* - Pesquisa

    Semelhante pesquisa em rvore B,

    A pesquisa sempre leva a uma pgina folha,

    A pesquisa no pra se a chave procurada for encontrada em umapgina ndice. O apontador da direita seguido at que se encontreuma pgina folha.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.2 40

    rvores B* - Procedimento para pesquisar na rvore B

    procedure Pesquisa (var x : TipoRegistro ; var Ap: TipoApontador) ;var i : integer ;begin

    i f Ap^.Pt = Internathen with Ap^ do

    begini := 1;while ( i < ni ) and (x.Chave > r i [ i ] ) do i := i + 1;i f x.Chave < r i [ i ]then Pesquisa(x , pi [ i1])else Pesquisa(x , pi [ i ] )end

    else with Ap^ dobegini := 1;while ( i < ne) and (x.Chave > re [ i ] .Chave) do i := i + 1;i f x.Chave = re [ i ] .Chavethen x := re [ i ]else writeln ( Registro nao esta presente na arvore ) ;

    end;end;

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.2 41

    rvores B* - Insero e Remoo

    Insero na rvore B*

    Semelhante insero na rvore B,

    Diferena: quando uma folha dividida em duas, o algoritmopromove uma cpia da chave que pertence ao registro do meiopara a pgina pai no nvel anterior, retendo o registro do meio napgina folha da direita.

    Remoo na rvore B*

    Relativamente mais simples que em uma rvore B,

    Todos os registros so folhas,

    Desde que a folha fique com pelo menos metade dos registros, aspginas dos ndices no precisam ser modificadas, mesmo se umacpia da chave que pertence ao registro a ser retirado esteja nondice.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.3 42

    Acesso Concorrente em rvore B*

    Acesso simultneo a banco de dados por mais de um usurio.

    Concorrncia aumenta a utilizao e melhora o tempo de resposta dosistema.

    O uso de rvores B* nesses sistemas deve permitir o processamentosimultneo de vrias solicitaes diferentes.

    Necessidade de criar mecanismos chamados protocolos para garantira integridade tanto dos dados quanto da estrutura.

    Pgina segura: no h possibilidade de modificaes na estrutura darvore como conseqncia de insero ou remoo.

    insero pgina segura se o nmero de chaves igual a 2m,

    remoo pgina segura se o nmero de chaves maior que m.

    Os algoritmos para acesso concorrente fazem uso dessa propriedadepara aumentar o nvel de concorrncia.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.3 43

    Acesso Concorrente em rvore B* - Protocolos deTravamentos

    Quando uma pgina lida, a operao de recuperao a trava, assim,outros processos, no podem interferir com a pgina.

    A pesquisa continua em direo ao nvel seguinte e a trava liberadapara que outros processos possam ler a pgina .

    Processo leitor executa uma operao de recuperao

    Processo modificador executa uma operao de insero ouretirada.

    Dois tipos de travamento:

    Travamento para leitura permite um ou mais leitores acessaremos dados, mas no permite insero ou retirada.

    Travamento exclusivo nenhum outro processo pode operar napgina e permite qualquer tipo de operao na pgina.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.4 44

    rvore B - Consideraes Prticas

    Simples, fcil manuteno, eficiente e verstil.

    Permite acesso seqencial eficiente.

    Custo para recuperar, inserir e retirar registros do arquivo logaritmico.

    Espao utilizado , no mnimo 50% do espao reservado para oarquivo,

    Emprego onde o acesso concorrente ao banco de dados necessrio, vivel e relativamente simples de ser implementado.

    Insero e retirada de registros sempre deixam a rvore balanceada.

    Uma rvore B de ordem m com N registros contm no mximo cercade logm+1N pginas.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.4 45

    rvore B - Consideraes Prticas

    Limites para a altura mxima e mnima de uma rvore B de ordem mcom N registros: log2m+1(N + 1) altura 1 + logm+1

    (

    N+12

    )

    Custo para processar uma operao de recuperao de um registrocresce com o logaritmo base m do tamanho do arquivo.

    Altura esperada: no conhecida analiticamente.

    H uma conjectura proposta a partir do clculo analtico do nmeroesperado de pginas para os quatro primeiros nveis (das folha emdireo raiz) de uma rvore 2-3 (rvore B de ordem m = 1).

    Conjetura: a altura esperada de uma rvore 2-3 randmica com Nchaves h(N) log7/3(N + 1).

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.4 46

    rvores B Randmicas - Medidas de Complexidade

    A utilizao de memria cerca de ln 2.

    Pginas ocupam 69% da rea reservada aps N inseresrandmicas em uma rvore B inicialmente vazia.

    No momento da insero, a operao mais cara a partio da pginaquando ela passa a ter mais do que 2m chaves. Envolve:

    Criao de nova pgina, rearranjo das chaves e insero da chavedo meio na pgina pai localizada no nvel acima.

    Pr{j parties}: probabilidade de que j parties ocorram durantea N -sima insero randmica.

    rvore 2-3: Pr{0 parties} = 47, Pr{1 ou mais parties} = 3

    7

    rvore B de ordem m: Pr{0 parties} = 1 1(2 ln 2)m

    +O(m2),

    Pr{1 ou + parties} = 1(2 ln 2)m

    +O(m2).

    rvore B de ordem m = 70: 99% das vezes nada acontece emtermos de parties durante uma insero.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.4 47

    rvores B Randmicas - Acesso Concorrente

    Foi proposta uma tcnica de aplicar um travamento na pgina seguramais profunda (Psmp) no caminho de insero.

    Uma pgina segura se ela contm menos do que 2m chaves.

    Uma pgina segura a mais profunda se no existir outra pginasegura abaixo dela.

    J que o travamento da pgina impede o acesso de outros processos, interessante saber qual a probabilidade de que a pgina seguramais profunda esteja no primeiro nvel.

    rvore 2-3: Pr{Psmp esteja no 1 nvel} = 47,

    Pr{Psmp esteja acima do 1 nvel} = 37

    rvore B de ordem m:Pr{Psmp esteja no 1 nvel} = 1 1

    (2 ln 2)m+O(m2),

    Pr{Psmp esteja acima do 1 nvel} = 37= 1

    (2 ln 2)m+O(m2).

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.4 48

    rvores B Randmicas - Acesso Concorrente

    Novamente, em rvores B de ordem m = 70: 99% das vezes a Psmpest em uma folha. (Permite alto grau de concorrncia para processosmodificadores.)

    Solues muito complicadas para permitir concorrncia de operaesem rvores B no trazem grandes benefcios.

    Na maioria das vezes, o travamento ocorrer em pginas folha.(Permite alto grau de concorrncia mesmo para os protocolos maissimples.)

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.4 49

    rvore B - Tcnica de Transbordamento (ou Overflow)

    Assuma que um registro tenha de ser inserido em uma pgina cheia,com 2m registros.

    Em vez de particion-la, olhamos primeiro para a pgina irm direita.

    Se a pgina irm possui menos do que 2m registros, um simplesrearranjo de chaves torna a partio desnecessria.

    Se a pgina direita tambm estiver cheia ou no existir, olhamospara a pgina irm esquerda.

    Se ambas estiverem cheias, ento a partio ter de ser realizada.

    Efeito da modificao: produzir uma rvore com melhor utilizao dememria e uma altura esperada menor.

    Produz uma utilizao de memria de cerca de 83% para uma rvoreB randmica.

  • Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.3.4 50

    rvore B - Influncia do Sistema de Paginao

    O nmero de nveis de uma rvore B muito pequeno (trs ou quatro)se comparado com o nmero de molduras de pginas.

    Assim, o sistema de paginao garante que a pgina raiz estejasempre na memria principal (se for adotada a poltica LRU).

    O esquema LRU faz com que as pginas a serem particionadas emuma insero estejam disponveis na memria principal.

    A escolha do tamanho adequado da ordem m da rvore B geralmente feita levando em conta as caractersticas de cadacomputador.

    O tamanho ideal da pgina da rvore corresponde ao tamanho dapgina do sistema, e a transferncia de dados entre as memriassecundria e principal realizada pelo sistema operacional.

    Estes tamanhos variam entre 512 bytes e 4.096 bytes, em mltiplos de512 bytes.