6

Eu percebi que posso criar dois tipo de índices para um determinando campo no HeidiSQL, que usam o algoritmo HASH ou BTREE, veja abaixo:

tipo de index

Veja o código CREATE de uma tabela de exemplo para a ilustração:

CREATE TABLE `pessoa` (
    `nome` VARCHAR(50) NOT NULL,
    `email` VARCHAR(50) NOT NULL,
    INDEX `index_nome` (`nome`) USING BTREE,
    INDEX `index_email` (`email`) USING HASH
)

Sendo assim, eu fiquei com algumas dúvidas a respeito desses dois tipos de algoritmos que podem ser usados.

Dúvidas

  1. O que é o algoritmo HASH?
  2. O que e o algoritmo BTREE?
  3. Quais as diferenças entre HASH e BTREE?
5
  • HASH é a tabela de espalhamento; dado um conjunto de dados, eles geram um número X qualquer, então só consultar na tabela se existe algum elemento com esse número X. BTREE por sua vez só se aplica a elementos passíveis de ordenação absoluta; no lugar de consultar uma tabela, se consulta uma árvore B. Commented 25/11/2017 às 20:06
  • 1
    Ah, não confunda "árvore B" com "árvore binária"... Commented 25/11/2017 às 20:08
  • Neste caso o BTREE esta relacionado a árvore binária?
    – gato
    Commented 25/11/2017 às 20:09
  • Relacionado: pt.stackoverflow.com/q/220409/64969 Commented 25/11/2017 às 20:10
  • o relacionamento entre árvores B e árvores binárias é o mesmo relacionamento entre tamareiras e pinheiros: ambas são árvores. A ideia da árvore B envolve páginas de tamanho arbitrário e balanceamento dos nós, de tal modo que qualquer folha não raiz tenha pelo menos metade da página preenchida. Mais detalhes na pergunta (e nas suas respostas) que eu linkei Commented 25/11/2017 às 20:12

1 Resposta 1

5

respondi no contexto do PostgreSQL.

dei detalhes sobre Btree (ok, ainda preciso completar).

falei sobre o código de hash.

foi respondido sobre as tabelas hash.

A documentação mostra a diferença. Na forma escrita parece que não querem que use o hash. Só mostram desvantagens. O que é algo bem realista.

É muito raro ele ser útil, ainda mais em disco onde costuma forçar muito mais leitura. A tradução literal de hash table é tabela de espalhamento, e qualquer coisa que fique espalhada é ruim para acessar em certas mídias, ou prejudica o cache resultando mais thrashing.

A principal desvantagem é só poder comparar a igualdade, o que traz outras implicações como não poder manter a ordem, que vai trazendo uma cascata de implicações.

Mas se for na memória e só precisa testar a igualdade e o acesso a cada elemento costuma ser individual mesmo e há poucas colisões de chave, seja porque o dado original não se repete ou o resultado da função hash não repete muito, aí ele consegue ser mais rápido que qualquer árvore binária ou árvore B. Se tiver muita escrita quase certamente haverá ganhos nessa operação (não nos raros piores casos).

Uma árvore B pode ter muita manutenção interna em tabelas com muita escrita, mas a leitura é sempre muito otimizada.

O índice hash só é útil se a pessoa entende bem todas implicações e fez testes que demonstram ganho claro. Por isso fica quase escondido e limitado a certos engines do MySQL.

Existe um índice hash interno que o banco de dados usa quando ele entende que é melhor para organizar resultados de consultas, mas é um detalhe que não interessa para quem usa o MySQL.

Coloquei no GitHub para referência futura.

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .