wiki

Discussão:BDA - Aula 19 - 2014/2

Questões


1. Qual a diferença entre índices Binary Tree e índices comuns?

  • Uma diferença é que com índices comuns sempre há uma pesquisa sequencial dentro de um arquivo de índice até encontrar o chave procurada. Devido a esse procedimento quanto mais para o final do índice a chave procurada estiver, maior será o tempo de localização. Por isso, os programadores criam dois índices "ascendente" e "descendente" para facilitar pesquisas com campos do tipo data, para realizar buscas nos dois sentidos. Apesar da idéia ser boa, sempre requer criação de índices extras.
  • Já em bases com índices BTree, as informações são dispostas de forma diferente, cada tipo de informação é pesquisa aprofundando-se nos "nós" (Depth nodes) que possuem alguma semelhanca (seletividade) com o item a ser pesquisado. De fato, pode-se aprofundar em "nós" até um ponto máximo e será nesse ponto máximo que estará os limites onde efetuar-se-à pesquisa. Não há necessidade de varrer um índice inteiro, apenas uma parte do índice.
  • A vantagem do BTree está apenas sobre enormes bases de dados, pois uma base de dados pequena usando índice BTree possui quantidade de acessos físicos bem superior a índices comuns.

fonte: [1]

2. O que é balanceamento de índices?

  • O balanceamento de índices é avaliar o custo-benefício de cada índice, evitando que sejam criados aqueles que não serão usados, ou que sejam duplicados, com alto custo de manutenção ou mesmo mal formulados. Além disso, o balanceamento de índices se trata do processo de manutenção destes índices, isto é, como eles estão, geralmente, estruturados em árvores balanceadas, devido às inúmeras operações de inserção, atualização e deleções, com o tempo os índices se tornam "desbalanceados", necessitando de desfragmentação, reindexação, realinhamento.


3. O que é e como funciona um IAM (Index allocation map)?

  • Uma página IAM (Index Allocation Map) mapeia as extensões em uma parte de 4 gigabytes (GB) de um arquivo de banco de dados usada por uma unidade de alocação.
  • Uma unidade de alocação deve ser de um dos três tipos:
    • IN_ROW_DATA : ** Partição de um heap ou indice
    • LOB_DATA: ** Tipos de dados xml, varchar (objetos grandes)
    • ROW_OVERFLOW_DATA : ** Comprimento variavel e grande
  • Se a unidade de alocação contiver extensões de mais de um arquivo, ou mais de um intervalo de 4 GB de um arquivo, haverá várias páginas IAM vinculadas com uma cadeia de IAM
  • Portanto, cada unidade de alocação tem pelo menos uma página IAM para cada arquivo no qual tem extensões. Também poderá haver mais de uma página IAM em um arquivo, se o intervalo das extensões no arquivo alocado à unidade de alocação exceder o intervalo que uma única página IAM pode registrar.
  • Ref: [ref]


4. Como funciona a questão índices de hash (hash indexes)?

  • A tabela hash é uma estrutura de dados especial, que associa chaves de pesquisa a valores através de uma função. Essa função é chamada de função de espalhamento ou função de dispersão. O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. A função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes. Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o que chamamos de colisão. Por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.
  • Um exemplo de função de dispersão é o: Método da divisão (método da congruência linear)
 h(k) = k * mod(m)
  • Onde:
  • Potências de dois devem ser evitadas para valores de m.
  • m deve ser um numero primo distante de pequenas potencias de dois.

Exemplo: k = 10028; m = 5013; h(10028) = 10028 * mod(5013) -> h(10028) = 2.

5. Como os índices sáo alocados nas tabelas?

Os índices podem ser alocados nas tabelas nas seguintes situações: 

 - Um arquivo separado por objeto do banco de dados (como no Postgre);
 - Todos os objetos de um mesmo "database" num único arquivo sem workspaces internamente (como no Firebird) ;
 - Todos os "databases" dentro de um único arquivo (que passa a chamar-se "device") e cada database com seus próprios objetos (como no SQLServer).


6. Quais técnicas devemos considerar para Indexação?

  • Tempo de Acesso: O tempo para encontrar um item de dados particular.


  • Tempo de Inserção: O tempo para inserir um novo item de dado. Isto inclui o tempo para encontrar o lugar correto para inserir o novo item de dado assim como o tempo para atualizar a estrutura do índice.


  • Tempo de Remoção: O tempo para remover um item de dado. Isto inclui o tempo para encontrar o item a ser removido assim como para atualizar a estrutura do índice.


  • Espaço Extra: O espaço adicional ocupado por uma estrutura de índice. Se o espaço adicional é pequeno, normalmente é vantajoso sacrificar esse espaço em benefício de um melhor desempenho.


Disponível em “http://3.143.69.156/wiki/index.php?title=Discussão:BDA_-_Aula_19_-_2014/2&oldid=33818”