Document

Antes de estudarmos como os índices são construídos, vamos entender como um computador localiza um registro em um índice.

Os dados armazenados em um sistema de arquivos podem estar registrados de forma aleatória ou de forma organizada.

Quando estão dispersos (de forma aleatória), para encontrar todas as informações de um conjunto de dados é necessário testar um a um para saber se é um resultado válido.

Exemplo: suponha que você tem um saco cheio de bolinhas numeradas de 1 a 100. Para encontrar a bolinha de número 33, você precisa tirar uma a uma e verificar se aquela selecionada é a de número 33, se não for, tem que procurar outra até encontrar a desejada. Você pode encontrar a de número 33 na primeira bolinha que você tirar do saco, mas também pode ser na última bolinha. Dessa forma, estatisticamente falando, o número médio de operações de consulta que você precisa fazer para encontrar determinada bolinha é de 50% do tamanho do seu conjunto, nesse caso, 50 operações.

Se você possui um conjunto ordenado de valores ou se você possui um índice ordenado que aponta para seu conjunto de dados disperso, há várias técnicas que farão o número de operações de consulta diminuir em muito.

Uma dessas técnicas (sem dúvida a mais usada em índices de banco de dados) é a técnica de B-Tree, que será apresentada a seguir.