Olá Bruno!

Na verdade essa é uma ótima pergunta!

Tive que fazer uma bela pesquisa para conseguir encontrar uma resposta, porém ela é mais complexa que eu esperava.

O MySQL (e outros DBs) usa o InnoDB como mecanismo de armazenamento. E a maneira de armazenar dados é com estruturas de árvores binárias, mas para entender a parte da busca, veremos como funciona a árvore binária de busca.

Ou seja, toda a tabela começa com uma raiz (root), que normalmente será um índice intermediário e essa raiz aponta para duas ramificações (knots ou nós de nó), uma em cada direção, uma anterior e uma posterior. Cada nó aponta para mais dois, um anterior e outro posterior até encontrar o valor desejado.

Digamos que para esta pequena lista, a raiz poderia ser Maçã, com isso, o primeiro índice apontaria para Laranja como um nó menor e para Uva como um nó maior, mas não percorreria todos os elementos da tabela.

Bom, basicamente é este o funcionamento. Para mais detalhes deste assunto, tem alguns links:

Documentação do MySQL, mais precisamente estrutura do InnoDB (em inglês)

Página da Wikipedia sobre Árvores binárias de busca (em português)

Página da Wikipedia sobre Árvores binárias (em português)

Espero ter ajudado! Bons estudos!