Estruturas de Dados para projeto de SGBD

Estruturas de dados analisadasEstruturas de nvel EsparsoDensoCombinadasArvore B+Tabela de hash

Tabelas de HashFuno de hashArray de depsitos

Tabelas de HashFuno de HashFuno de hashtb. chave de hashArgumento : inteiro de 0 a B -1Onde B o nmero de depsitos ( buckets)K/B Onde K o valor da chave

Tabelas de HashArray de depsitosArray indexado de 0 a B 1B o nmero de depsitos Contm cabealho de B listas encadeadas ( uma para cada depsito do array )

Tabelas HashSistemas hashVantagensAplicao da funo sempre resulta num positivoEsse nmero positivo pode ser como binrio

Uma tabela de Hash

h(a) = 1h(b) = 2h(c) = 1h(d) = 001

2

3SE registro tem a chave de pesquisa K ENTAO* guardar o registro vinculando-o lista de depsitos correspondente ao depsito de h(K)K ={ a, b, c, d }

Tabelas HashArmazenamento/ MecanismoArmazenamentoprimrio

Armazenamento secundrioPONTEIROBLOCOFoco em BD : armazenamento secundrio

Tipos de HashingHashing estticoNmero fixo de endereos Difcil expanso / reduo do arquivo dinamic.Hashing LinearSem estrutura adicional ao arquivoHashing Extensvel/ DinmicoUsar estrutura de acesso adicional ao arquivoSimilar a indexaousa valor resultante da funo hash no campo de pesquisa

Hashing extensvelUm vetor/tabela 2d Aplicar a funo hash nas chaves Obtm-se nmero

escolher qtde de bits para diferenciar entre os ndices a serem armazenados no diretrio. d a profundidade global do diretriod especifica o n de linhas da tabela (diretrio), que ser 2d.

Hashing extensvelPormNo preciso haver um bucket para cada uma das 2d localizaesIntroduz um nvel indireto (depsitos) o array de ponteiros para blocos E no para os blocos dos dadosCrescem em potncias de 2Em 1 etapa de cresc, , o nmero de depsitos duplicado

DepsitosBlocos de dados

Profundidade global e localProfundidade global ( d)Profundidade local ( d' ) indica quantos bits da sequncia da funo hash usados para determinar pertinncia dos registros.Pode ser menor ou igual a d

Uma tabela de HashINSERT:h(a) = 1h(b) = 2h(c) = 1h(d) = 001

2

3

Insero numa tabela hashInserir registro com chave de pesquisa k calcula-se o h(K)Tomar os primeiros i bits dessa sequncia Ir para a entrada do array de dpepsitos indexada por i mantido como parte da e.d.Seguir o ponteiro do array de depsitoObtem-se o bloco B em doisMAS ...

Insero numa tabela hash ( 2) Considere j como o nmero de bits pertinentes ao bloco B SE j < i : nada a fazer nos depsitosDesmembrar B em dois;Dsitribuir registros de B nos 2 blocos usando o (j+1)-simo bit Inserir j+1 em cada n de cada bloco para indicar nmero de bits usados na pertinnciaAjustar o array de depsitos para apontar os dois blocos , de acordo com o (j+1)-simoMAS ... se no resolver

Insero numa tabela hash ( 2) Todos registros retidos em um bloco B antigo, em lugar de divididos com o bloco novoSE i = j , incrementar i em 1 unidadeO comprimento do array de depsito duplicado 2i agora 2i+1 W a sequncia de i bits indexando a entrada do depsito anteriorw0, w1 apontam para mesmo bloco B J permanece o mesmoAgora i > j