Os índices Hashing usa a ideia central a divisão de um universo de dados a ser organizado em subconjuntos mais gerenciáveis para grandes quantidades e utiliza dois conceitos importantes
Tabela de Hashing – É estrutura que permite o acesso aos subconjuntos.
Função de Hashing – É a função que realiza um mapeamento entre valores de chaves e entradas na tabela.
A utilização é simples temos que saber quantos subconjuntos se quer e criar uma regra de cálculo que diga, dada uma chave, em qual subconjunto devo procurar pelos dados com esta chave ou colocar este dado, caso seja um novo elemento. Essa é a função Hashing, em seguida, possuir um índice que me permita encontrar o início do subconjunto certo, depois de calcular o hashing. Isso é tabela Hashing.
Os índices hashing possuem uma série de limitações em relação às árvores: não permite recuperar/imprimir todos os elementos em ordem de chave nem tampouco outras operações que exijam sequência dos dados e não permite operações do tipo recuperar o elemento com a maior ou a menor chave.
Outra forma de busca por índice seria árvore B
As árvores B são organizadas por nós, tais como os das árvores binárias de busca, mas apresentam um conjunto de chaves maior do que um e são usualmente chamados de páginas. Dentre suas propriedades ela permite a inserção, remoção e busca de chaves numa complexidade de tempo logarítmica.
Ao comparar o desempenho das duas formas de buscas por índice, para uma faixa de valores o melhor desempenho é a utilização de árvores.
Fonte: https://fabiansilva.wordpress.com/2014/09/17/prova-comentada-2014-perito-criminal-ciencia-da-computacao-fundacao-aroeira/