As pessoas costumam dizer que a indexação é uma técnica para processar consultas com eficiência caso seu banco de dados seja grande o suficiente. Este post é para resumir o que é o índice do banco de dados e revisitar hash e B+Tree.
Índice é uma estrutura de dados que organiza registros para otimizar certos tipos de operações de recuperação. Podemos criar um índice em um campo da tabela e recuperar todos os registros que satisfaçam as condições de pesquisa em
search-key campo. Sem índice, nossa consulta acabaria varrendo linearmente todo o conteúdo da tabela para buscar apenas um ou alguns registros. Nesta postagem, gostaria de resumir o desempenho e os casos de uso de duas técnicas comuns de indexação:Índice de hash e B+árvore
Índice de hash
Esta técnica é amplamente usada para criar índices na memória principal porque sua recuperação rápida por natureza. Tem complexidade média de operação O(1) e complexidade de armazenamento O(n).
Em muitos livros, as pessoas usam o termo
bucket para denotar uma unidade de armazenamento que armazena um ou mais registros Há duas coisas a serem discutidas quando se trata de hash:
- Função de hash:mapeia as chaves de pesquisa (como sua entrada) para um número inteiro que representa essa chave no bucket.
- Esquema de hash:como lidar com a colisão de chaves após o hash.
Algumas pessoas perguntam:por que colisão? Uma função de hash perfeita já existe? Na verdade, digamos que suas chaves sejam um conjunto infinito, é impossível mapeá-las em um conjunto de inteiros de 32 bits sem nenhuma colisão. Deve haver um trade-off entre computação e taxa de colisão.
Existem alguns esquemas de hash que valem a pena mencionar:sondagem linear, hash encadeado e hash extensível. Os algoritmos de pesquisa/inserção/exclusão variam de acordo com o esquema de hash, por exemplo, o hash encadeado lida com colisões de chaves colocando elementos com o mesmo valor de hash no mesmo bucket.
Prós
- O índice de hash é adequado para pesquisa de igualdade ou chave primária. As consultas podem se beneficiar do índice de hash para obter o custo de pesquisa O(1) amortizado. Por exemplo:
SELECT name, id FROM student WHERE id = '1315';
Contras
A tabela de hash tem algumas limitações:
- As consultas de intervalo não são eficientes. A tabela de hash é baseada na distribuição uniforme. Em outras palavras, você não tem controle de onde uma entrada de índice será colocada.
- Baixa escalabilidade:o desempenho da operação de pesquisa pode diminuir quando há muitas colisões e é necessário redimensionar a tabela de hash e refazer as entradas de índice existentes.
B+Árvore
Esta é uma estrutura de dados de árvore auto-equilibrada que mantém os dados em ordem de classificação e permite uma pesquisa rápida em cada nó, normalmente usando pesquisa binária.
B+Tree é uma implementação de índice padrão em quase todos os sistemas de banco de dados relacionais.
B+Tree é basicamente uma árvore de busca M-way que tem a seguinte estrutura:
- equilíbrio perfeito:os nós folha sempre têm a mesma altura.
- todo nó interno, exceto a raiz, está pelo menos meio cheio (M/2 − 1 <=número de chaves <=M − 1).
- todo nó interno com k chaves tem k+1 filhos não nulos.
Cada nó da árvore tem uma matriz de pares de valores-chave classificados. O par chave-valor é construído a partir de (valor da chave de pesquisa, ponteiro) para nós raiz e internos. Os valores do nó folha podem ser 2 possibilidades:
- o registro real
- o ponteiro para o registro real
Pesquise um valor v
- Comece com o nó raiz
- Enquanto o nó não é um nó folha, nós fazemos:
- Encontre o menor Ki onde Ki>=v
- If Ki ==v:define o nó atual para o nó apontado por Pi+1
- Caso contrário, defina o nó atual para o nó apontado por Pi
Chaves duplicadas
Em geral, a chave de pesquisa pode ser duplicada, para resolver isso, a maioria das implementações de banco de dados apresenta uma chave de pesquisa composta. Por exemplo, queremos criar um índice em
student_name então nossa chave de pesquisa composta deve ser (nome_do_aluno, Ap) onde Ap é a chave primária da tabela. Prós
Existem dois recursos principais que o B+tree oferece:
- Minimizando operações de E/S
- Altura reduzida:B+Tree tem um fator de ramificação bastante grande (valor entre 50 e 2000 frequentemente usado), o que torna a árvore gorda e curta. A figura abaixo ilustra um B+Tree com altura de 2. Como podemos ver os nós estão espalhados, são necessários menos nós para atravessar até uma folha. O custo de procurar um único valor é a altura da árvore + 1 para o acesso aleatório à tabela.
- Escalabilidade:
- Você tem um desempenho previsível para todos os casos, O(log(n)) em particular. Para bancos de dados, geralmente é mais importante do que ter um desempenho melhor ou médio de caso.
- A árvore sempre permanece equilibrada por sua implementação. Um B+Tree com n chaves sempre tem uma profundidade de O(log(n)). Assim, o desempenho não diminuirá se o banco de dados crescer. Uma árvore de quatro níveis com um fator de ramificação de 500 pode armazenar até 256 TB, desde que a página tenha 4 KB.
- B+Tree é mais adequado para consultas de intervalo, por exemplo
"SELECT * FROM student WHERE age > 20 AND age < 22"
Conclusão
Embora o índice de hash tenha um desempenho melhor em termos de consultas de correspondência exata, B+Tree é sem dúvida a estrutura de índice mais usada no RDBMS, graças ao seu desempenho consistente em escalabilidade geral e alta.
| B+Árvore | Hash | |
|---|---|---|
| Tempo de pesquisa | O(log(n)) | O(log(1)) |
| Tempo de inserção | O(log(n)) | O(log(1)) |
| Hora de exclusão | O(log(n)) | O(log(1)) |
Recentemente, a árvore de mesclagem estruturada em log (LSM-tree) atraiu um interesse significativo como concorrente da árvore B+, porque sua estrutura de dados pode permitir uma melhor eficiência no uso do espaço de armazenamento. Vou pesquisar mais sobre isso e fazer um post sobre isso em breve.
