Buscar

05_indexacao

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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 = <storage­engine>;
 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

Outros materiais