Organização dos Dados e Índices - Aula 04/11 - Bancos de Dados 2020.2

Como os Bancos de Dados Organizam e Indexam Dados?

Introdução ao Tema

• André introduz o tema do vídeo, que é a organização e indexação de dados em bancos de dados, dando continuidade a um vídeo anterior sobre armazenamento.

• O foco principal será nos bancos de dados relacionais, que são os mais populares e eficientes para grandes volumes de dados.

Conceitos Fundamentais

• Definições importantes:

• Arquivo: referência a uma porção de dados no disco.

• Registro: segmentação dos elementos dentro do arquivo.

• A estrutura lógica do banco de dados (como tabelas) não se alinha diretamente com os arquivos físicos no disco.

Organização dos Dados em Tabelas

• A discussão se concentra em como os registros das tabelas são armazenados no disco, ignorando inicialmente a ideia de arquivo.

• Cada tupla da tabela é considerada um registro. A forma como esses registros são organizados impacta na recuperação dos dados.

Importância da Ordem na Armazenagem

• A ordem em que os registros são guardados influencia diretamente na eficiência da recuperação.

• Exemplo prático: se registros estão espalhados pelo disco, o banco precisa "andar" para recuperá-los, tornando o processo mais lento.

Exemplos Práticos de Armazenamento Sequencial

• Uma tabela exemplo mostra registros ordenados sequencialmente por ID. Essa gravação sequencial facilita a recuperação eficiente.

Estruturas de Armazenamento e Ordenação de Dados

Conceito de Arquivo Hip

• O arquivo Hip é caracterizado pela ausência de uma ordenação lógica nos registros, onde a ordem de gravação não possui relevância para o acesso ou organização dos dados.

• A definição do arquivo Hip implica que os registros são armazenados sem qualquer referência a uma sequência significativa, sendo considerados aleatórios.

Estratégias de Ordenação

• É possível ter diferentes tipos de ordenação além da sequencial; a escolha da estratégia depende do contexto e das necessidades específicas do sistema.

• A ordenação RESH permite que espaços vazios sejam mantidos no disco, utilizando uma função hash para determinar a posição dos registros.

Função Hash (RESH)

• A proposta é criar uma função hash baseada em um identificador (ID), onde se calcula a posição na qual o registro deve ser gravado.

• Um exemplo simples de função hash: somar os dígitos numéricos do ID para determinar sua posição. Por exemplo, para o ID 2223, a soma seria 7.

Colisões e Alocação

• Ao usar funções hash, podem ocorrer colisões (quando dois registros tentam ocupar a mesma posição). Isso será abordado em discussões futuras sobre RESH.

• Sistemas que utilizam RESH frequentemente pré-alocam blocos com registros vazios para facilitar o armazenamento eficiente à medida que novos dados são gravados.

Índices e Eficiência no Acesso

• Existem três possibilidades principais para gravar registros fisicamente: RIPH (sem ordenação), sequencial e RESH. Cada método tem suas vantagens em termos de eficiência no acesso aos dados.

• O índice serve como uma estrutura auxiliar que aponta onde os dados estão armazenados no disco, facilitando buscas rápidas sem necessidade de percorrer todos os registros.

Organização do Índice

• As entradas do índice podem ser organizadas por características específicas dos dados. Exemplos incluem chaves primárias ou listas encadeadas.

• Sem um índice adequado, seria necessário ler todos os registros associados até encontrar as informações desejadas, tornando o processo ineficiente.

Armazenamento e Indexação em Bancos de Dados

Estrutura de Índices

• A entrada do índice é composta por uma chave (kr) e um ponteiro que indica a posição no arquivo de dados.

• O índice pode apontar para registros em diferentes ordens, permitindo acesso eficiente aos dados. A chave primária deve ser única.

• Cada entrada no índice contém a chave, resultando em redundância na estrutura, mas possibilitando múltiplos registros associados à mesma chave.

Tipos de Índices

• Um índice pode ter uma lista de registros que correspondem a uma chave específica, como no caso de espécies animais.

• É possível ter mais de um índice para o mesmo arquivo, dependendo da ordenação desejada dos dados.

• A ordem do arquivo está relacionada ao índice; isso permite localizar rapidamente os registros desejados.

Redundância e Consistência

• A introdução da redundância através da cópia da chave para o índice impacta a consistência dos dados.

• É importante distinguir entre índices primários (de agrupamento), onde a ordem do arquivo é definida pela chave, e índices secundários.

Exemplos Práticos

• Um exemplo prático é um arquivo sequencial onde os registros estão ordenados por ID. Isso ilustra como um índice primário organiza os dados eficientemente.

• Um índice secundário não possui relação direta com a ordem dos dados no arquivo, sendo mais flexível na busca.

Tipos de Índice: Denso vs. Esparso

• O conceito de "índice denso" refere-se à presença de uma entrada para cada valor da chave; já o "índice esparso" tem entradas para múltiplos valores da mesma chave.

• Em bancos de dados relacionais, cada registro tem uma entrada correspondente no índice, facilitando consultas eficientes.

O que é um índice espaço?

Conceitos de Índice e Estruturas de Dados

• O conceito de índice espaço é introduzido, onde uma chave pode ter múltiplas entradas no índice para a mesma entrada.

• A diferença entre índices densos e esparsos é discutida; o denso possui uma entrada para cada valor possível da chave, enquanto o esparso tem entradas apenas para chaves únicas.

• É questionado sobre o número máximo de índices primários e secundários em uma relação com cinco atributos, encerrando a explicação sobre estrutura de arquivo e índices.

Gravação Sequencial e Organização dos Dados

Estrutura da Tabela Exemplo

• Uma tabela exemplo com registros de animais pré-históricos é apresentada, destacando que o número do catálogo é único, enquanto a espécie não é.

• A gravação sequencial dos dados no disco é explicada; os registros são armazenados em ordem crescente pelo ID.

• A importância da manutenção da ordem na gravação dos arquivos é discutida, mencionando as dificuldades ao inserir novos registros.

Tipos de Ordenação: Hip e RESH

Conceito de Arquivo Hip

• O termo "Hip" refere-se à falta de ordenação significativa nos registros gravados; a ordem não está relacionada a nenhuma chave relevante.

• A ideia do arquivo Hip implica que mesmo que os registros sejam gravados em sequência, isso não significa que tenham uma organização lógica ou útil.

Estratégia de Ordenação RESH

• Introduz-se o conceito de ordenação RESH, permitindo espaços vazios nos discos. Essa técnica utiliza funções hash para determinar onde gravar os registros.

Introdução ao RESH e Estruturas de Índice

O que é o RESH?

• O RESH (Registro Estruturado Hash) é uma política para ordenar dados em arquivos, onde posições podem estar vazias inicialmente.

• Sistemas RESH pré-alocam blocos com registros vazios e gravam nas posições conforme os cálculos são realizados.

• Questões como colisão serão abordadas posteriormente, mas a ideia principal é entender que o RESH é uma das opções para organização de dados.

Métodos de Gravação de Registros

• Existem três métodos principais para gravar registros fisicamente no disco: RIPH (sem ordenação), sequencial e RESH.

• É importante ter estratégias auxiliares para melhorar o acesso aos dados, especialmente quando não estão ordenados.

• A eficiência do acesso aos registros não ordenados é um desafio que pode ser superado com técnicas adequadas.

Conceito de Índice

• Um índice é uma estrutura separada que melhora a eficiência do acesso aos dados armazenados no disco.

• Cada entrada do índice contém uma chave e um ponteiro que indica onde está o registro correspondente no disco.

• O índice funciona como um índice de livro, permitindo localizar rapidamente informações sem ler todos os registros.

Organização do Índice

Tipos de Estruturas de Índice

• As entradas do índice podem ser organizadas de diferentes maneiras, conforme classificado por Christmadeu em três tipos: casterístico, krd e krd list.

1. Casterístico

• No caso casterístico, o arquivo está organizado pela chave, sem necessidade de uma estrutura separada para o índice; cada registro inteiro da tabela serve como entrada.

2. Estrutura Separada

• Quando há uma estrutura separada, cada entrada do índice consiste em uma chave e um ponteiro indicando a posição do registro correspondente no arquivo.

3. Chaves Não Únicas

Estruturas de Índice em Banco de Dados

Chaves e Estruturas de Índice

• A chave é única em algumas estruturas, enquanto em outras pode haver múltiplas entradas para uma mesma chave. A redundância da chave no índice é um ponto importante a ser discutido.

• Em casos onde há repetições, como espécies de animais, o índice deve apontar para várias entradas correspondentes à mesma chave, permitindo a busca eficiente por registros duplicados.

Tipos de Índices

• Existem três formas principais de estruturação:

• Característica (registro original com chave e dados).

• KRD (um ponto para um registro).

• KRD (uma chave apontando para vários registros).

• As alternativas 2 e 3 permitem múltiplos índices para o mesmo arquivo, possibilitando diferentes ordenações dos dados. No entanto, não incluem todos os dados do registro, apenas chaves e ponteiros.

Eficiência dos Índices

• O uso eficiente da memória é possível ao carregar um índice inteiro na RAM antes de acessar os registros no disco. Isso melhora a velocidade de leitura.

• É viável criar estruturas mais complexas além das listas ordenadas simples mencionadas anteriormente.

Redundância e Consistência dos Dados

• A introdução da redundância através dos índices pode impactar a consistência dos dados e as velocidades de leitura e gravação. É essencial analisar esses efeitos nos exercícios propostos.

Nomenclatura dos Índices

• Introduz-se uma nomenclatura que distingue entre índices primários (ou agrupamento) e secundários. O índice primário requer que o arquivo esteja ordenado sequencialmente pela chave.

• Um exemplo prático é quando os registros estão organizados por ID; isso caracteriza um índice primário devido à relação direta entre ordem do arquivo e chave.

Exemplos Práticos

• Mesmo com índices separados, se o arquivo estiver ordenado sequencialmente pela espécie, ainda pode ser considerado um índice primário.

Estruturas de Índices em Banco de Dados

Tipos de Índices

• O índice secundário é mencionado como uma estrutura onde os dados não têm ordem associada ao índice, resultando em ponteiros cruzados.

• O índice denso é definido como tendo uma entrada para cada valor da chave, enquanto o índice espaço possui entradas para mais de um valor da chave.

• A confusão entre as definições de índices denso e espaço é abordada, destacando que um índice denso tem uma entrada para cada valor da chave, mesmo que haja múltiplos registros associados.

Exemplos Práticos

• Um exemplo prático ilustra que um índice denso pode ter várias entradas para a mesma chave, mas ainda assim mantém a relação 1:1 com os valores das chaves.

• No caso do índice espaço, há múltiplas chaves associadas à mesma entrada no índice. Isso demonstra a flexibilidade dos índices em lidar com dados duplicados.

Resumo e Conclusão

• A distinção entre índices densos e espaços é reiterada: o primeiro tem uma entrada por cada possível valor de chave; o segundo permite múltiplas chaves por entrada no índice.