Índices, tabelas hash e árvores b

Centro Universitário de Anápolis – UniEVANGÉLICA
Bacharelado em Sistemas de Informação
4º Período
Disciplina: Estrutura de Dados II
Professora: Noeli Pimentel
Acadêmica: Iara Maia Silva

Índices, Tabelas Hash e Árvores B

Um índice corresponde a um identificador, utilizado para agilizar o processo de busca de informações, reduzindo o custo de acesso a uma informação qualquer. A característica essencial de um índice é seu caráter único, que diz que sua escolha deve corresponder a uma informação única, dentro do conjunto de dados armazenados, que possa servir como referência a esse conjunto. Um exemplo muito comum, quando se trata da ilustração de índices é o CPF, que se trata um número com 11 dígitos, capaz de identificar pessoas físicas maiores de 16 anos.
“A ideia central do hash é utilizar uma função aplicada sobre a parte da informação (chave), para retornar o índice onde a informação deve ou deveria estar armazenada” (SILVA, S/D, pág.9). Sendo assim, uma tabela hash armazena informações, associando a estas uma chave de pesquisa, podendo ser representada, por exemplo, por vetores e/ou vetores+listas encadeadas.
Uma função hash se encarrega por gerar índices e tratar possíveis colisões (endereços de pesquisa iguais, ou já ocupados), distribuindo as informações ao longo da tabela. Colisões não são admitidas em sistemas de criptografias, a solução para estas se dá por meio da utilização de funções hash em conjunto com outras estruturas de dados, como as árvores e as listas.
Uma função hash pode ser definida por: h(x) = x mod M, onde h corresponde ao índice que a informação x irá ocupar, é obtido pelo resto da divisão de x por M, que corresponde a quantidade de posições para armazenamento na tabela.

Figura 1: Exemplo Tabela Hash A primeira característica tratada quando se discute uma Árvore B é a quantidade de registros por nó. Diferente da Árvore Binária, que contém apenas um registro por nó, e dois nós filhos para cada raiz, as árvores B são capazes de