Baixe o app para aproveitar ainda mais
Prévia do material em texto
Ramon Gomes Costa, Prof. D.Sc. Aula Expositiva Estruturas de Indexação para ArquivosEstruturas de Indexação para Arquivos Banco de Dados II 2 Plano de Curso Estruturas de indexação para arquivos Introdução Índices ordenados de único nível Índices primários Índices de agrupamento Índices secundários Exercícios. Banco de Dados II 3 Introdução Índices: estruturas de acesso auxiliares, utilizadas para agilizar a recuperação de registros sobre certas condições de pesquisa. são arquivos adicionais que oferecem formas alternativas de acessar os registros (caminhos de acesso secundário) sem afetar a organização física dos dados. permitem acesso eficiente com base nos campos de indexação (usado para construir o índice). índice arquivo de dados: distribuído entre blocos ponteiro para bloco Banco de Dados II 4 Introdução Busca: um índice é pesquisado e um ponteiro define o endereço para o bloco de disco onde o registro está localizado. Um índice pode ser classificado pela sua estrutura de acesso: único nível (ponteiros para blocos ou Registros); ou índices multiníveis (contém ponteiros para outros índices). Tipos de índices ordenados de único nível: Índices primários Índices de agrupamento Índices secundários Tipos de índices ordenados multiníveis: Árvores B+ Índice de único nível Índices multiníveis Banco de Dados II 5 Introdução Ideia semelhante à de um índice remissivo em um livro. Uma estrutura de acesso a índice pode ser definida sobre um campo de um registro de arquivo, chamando-o campo de índice (ou atributo de indexação). Ex.: CPF do funcionário Chassi de um carro Banco de Dados II 6 Introdução Criando tabelas em SQL (sintaxe básica - MySQL): CREATE TABLE nome_tabela ( Coluna tipo <opcionais>, … <chaves> ) ENGINE = <storageengine>; Em <chaves>, podemos especificar os seguintes tipos de chave: KEY (Índice secundário) – um índice secundário sem uma restrição de chave. [Sinônimo: INDEX] UNIQUE KEY (Chave secundária) – um índice secundário com uma restrição de chave (valores distintos para cada registro). [Sinônimo: UNIQUE] PRIMARY KEY (Chave primária) – um índice primário (utiliza os valores do campo de ordenação física do arquivo de registros). FOREIGN KEY (Chave estrangeira) – uma restrição de integridade imposta entre um índice secundário e um índice primário. Indica que os valores de campo fazem referência aos usados para formar a chave primária. Banco de Dados II 7 Introdução Criando tabelas em SQL (sintaxe básica): CREATE TABLE FUNCIONARIO ( Pnome varchar(20) NOT NULL, Minicial char(1) DEFAULT NULL, Unome varchar(20) NOT NULL, Cpf bigint(11) unsigned zerofill NOT NULL, Datanasc date DEFAULT NULL, Endereco varchar(50) DEFAULT NULL, Sexo enum('m','f') DEFAULT NULL, Salario float(7,2) DEFAULT NULL, Cpf_supervisor bigint(11) unsigned zerofill DEFAULT NULL, Dnr int unsigned NOT NULL, KEY (Unome), UNIQUE KEY (Pnome, Minicial, Unome), PRIMARY KEY (Cpf), FOREIGN KEY (Dnr) REFERENCES DEPARTAMENTO(Dnumero) ON DELETE SET DEFAULT ON UPDATE CASCADE ) ENGINE=InnoDB; Banco de Dados II 8 Introdução Identificadores de índices: O identificador da chave primária sempre será PRIMARY KEY. PRIMARY KEY (atributo_pk) índices secundários seguem o seguinte formato: KEY identificador (atributo_chave) UNIQUE KEY identificador (atributo_unique_key) utilizamos a palavra-chave CONSTRAINT para definir um identificador sobre a restrição de integridade referencial imposta em um índice chave estrangeira: CONSTRAINT identificador FOREIGN KEY (atr_fk) REFERENCES tab_pk(atr_pk) ON DELETE acao_delete ON UPDATE acao_update Banco de Dados II 9 Introdução Identificadores de índices: CREATE TABLE FUNCIONARIO ( Pnome varchar(20) NOT NULL, Minicial char(1) DEFAULT NULL, Unome varchar(20) NOT NULL, Cpf bigint(11) unsigned zerofill NOT NULL, Datanasc date DEFAULT NULL, Endereco varchar(50) DEFAULT NULL, Sexo enum('m','f') DEFAULT NULL, Salario float(7,2) DEFAULT NULL, Cpf_supervisor bigint(11) unsigned zerofill DEFAULT NULL, Dnr int unsigned NOT NULL, KEY unome (Unome), UNIQUE KEY nome (Pnome, Minicial, Unome), PRIMARY KEY (Cpf), CONSTRAINT Dnr FOREIGN KEY (Dnr) REFERENCES DEPARTAMENTO(Dnumero) ON DELETE SET DEFAULT ON UPDATE CASCADE ) ENGINE=InnoDB; Banco de Dados II 10 Índice Primário Um índice primário é um arquivo com registros formados pelo campo chave de ordenação usado para organizar um arquivo ordenado. No arquivo de índice, cada registro tem um valor único para este campo. O índice é um arquivo ordenado. &(bloco1) &(bloco2) &(bloco3) &(bloco4) &(bloco5) &(bloco6) índice Banco de Dados II 11 Índice Primário Atua como uma estrutura de acesso para procurar e acessar de modo eficiente os registros em arquivos de dados. Formato de um Registro em um arquivo de índice primário: <K(i), P(i)>, onde: Chave primária - K(i): um campo de mesmo tipo de dado do campo chave de ordenação do arquivo de dados. Ponteiro para bloco – P(i): ponteiro para um bloco de disco (endereço de bloco). <”Aaron, Eduardo ”, &(bloco1)> <”Adams, João ”, &(bloco2)> <”Alexandre, Eduardo”, &(bloco3)> Tamanho fixo Banco de Dados II 12 Índice Primário Existe um Registro de índice (entrada de índice) para cada bloco. Cada entrada de índice tem: o valor do campo chave primária para o primeiro registro em cada bloco; e um ponteiro para este bloco. Banco de Dados II 13 Índice Primário Obs.: O número total de entradas no índice (ri) é igual ao número de blocos no disco: ri = B O primeiro registro de cada bloco serve de âncora (chamado âncora de bloco ou registro de âncora) ri=4 B=4 Banco de Dados II 14 (Índices) Índices podem ser caracterizados como: Densos: uma entrada de índice para cada Registro Esparsos: menos entrada que o número de Registros Obs.: o índice primário é um índice esparso: Vár ios reg istr os não são ind exa dos Banco de Dados II 15 Índice Primário Obs.: um arquivo de índice para um índice primário ocupa um espaço muito menor do que seu arquivo de dados associado: Existem menos entradas de índice do que registros de dados Cada entrada de índice é menor em tamanho, pois tem apenas dois campos Em um bloco, cabem mais Registros de índice (Ri) que registros de dados (R) Uma pesquisa binária sobre um índice requer menos acessos de bloco Arquivo de dados: log2b Arquivo de índice: log2bi + 1, onde bi é a quantidade de blocos necessários para armazenar um índice. Banco de Dados II 16 Índice de agrupamento Um índice de agrupamento (clustered) é um arquivo com registros formados por um campo não utilizado como chave de ordenação, mas utilizado para organizar um arquivo (campo de agrupamento). Neste caso, o arquivo é chamado arquivo agrupado. No arquivo agrupado, registros podem conter valores iguais para vários campos. Obs.: na teoria, um mesmo índice não pode ser primário e clustered. Banco de Dados II 17 Índice de agrupamento Um índice clustered é um arquivo ordenado com dois campos: <K(i), P(i)> Há uma entrada no índice de agrupamento para cada valor distinto Um índice clustered é um índice esparso O ponteiro é um endereço para o primeiro bloco que contém um registro com o valor indexado. não-chave Banco de Dados II 18 Índice de agrupamento Como o arquivo de dados é um arquivo ordenado, têm-se os problemas já citados para inserção e remoção para estetipo de organização de arquivos. Resolução: manter registros com valores de campo de ordenação distintos em blocos separados. Banco de Dados II 19 (índices) Diferença principal entre tabelas hash e índices: Estrutura do arquivo: Tabelas hash: <P(i)> Índices: <K(i), P(i)> Banco de Dados II 20 Índices Secundários Um Índice secundário é um arquivo com registros formados por um campo não ordenado de um arquivo de dados. Um mesmo arquivo de dados pode ter vários índices secundários associados. CREATE TABLE FUNCIONARIO ( Pnome varchar(20) NOT NULL, Minicial char(1) DEFAULT NULL, Unome varchar(20) NOT NULL, ... Cpf bigint(11) unsigned zerofill NOT NULL PRIMARY KEY, ... Dnr int unsigned NOT NULL, INDEX dnr_index (Dnr), UNIQUE KEY nome_key (Pnome, Minicial, Unome), CONSTRAINT Dnr_ibfk FOREIGN KEY (Dnr) REFERENCES DEPARTAMENTO(Dnumero) ON DELETE SET DEFAULT ON UPDATE CASCADE ) ENGINE=InnoDB; Banco de Dados II 21 Índices Secundários Índice secundário sobre um campo chave: É, normalmente, associado à um atributo de chave UNIQUE. é um arquivo ordenado com dois campos: <K(i), P(i)> existe uma entrada para cada registro no arquivo de dados é um índice denso ... ... Banco de Dados II 22 Índices Secundários único Arquivo ordenado Banco de Dados II 23 Índices Secundários Índice secundário sobre um campo não-chave: é, normalmente, associado à um atributo de chave INDEX (ou KEY). pode ser um índice denso ou esparso. Opção de implementação: um arquivo ordenado com dois campos: <K(i), P(i)>, onde P(i) é um ponteiro para uma lista de ponteiros. ponteiros para cada registro no arquivo de dados, acessados por uma lista de ponteiros. Banco de Dados II 24 Índices Secundários Índice esparso Banco de Dados II 25 Índices Tipos de índices: baseados nas propriedades do campo de índice. Banco de Dados II 26 Índices Propriedades dos tipos de índice Exemplo do slide Banco de Dados II 27 Ramon Gomes Costa, Prof. D.Sc. ramongomescosta@gmail.com Estruturas de Indexação para ArquivosEstruturas de Indexação para Arquivos Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27
Compartilhar