O MySQL não "reconstrói" o índice em cada inserção.

O tamanho de página padrão do MySQL é 16K. Ele aloca essas páginas em incrementos de 1 MB (chamados de extensões).

Quando uma tabela é criada pela primeira vez (os índices são reconstruídos), as páginas são preenchidas 15/16, deixando espaço para algumas inserções aleatórias (1k de espaço). Se suas entradas de índice tiverem 500 bytes cada (tamanho da chave primária + dados de linha para um índice clusterizado), isso deixará espaço para que 2 novas linhas sejam inseridas antes de dividir a página.

O MySQL mantém o valor do registro mais alto e mais baixo no cabeçalho da página, de modo que os registros dentro de um determinado intervalo vão para a mesma página.

Quando o MySQL precisa inserir uma linha em uma página inteira, a página deve ser dividida. O MySQL adicionará uma nova página e moverá metade dos dados da página para a nova página.

Dentro de uma página, os registros podem não estar em ordem física. Eles estarão na ordem em que foram inseridos. Eles são vinculados em ordem por meio de uma forma de lista vinculada. Assim, mesmo uma inserção aleatória, fora da necessidade de dividir a página, não faz com que os dados sejam movidos fisicamente.

Depois de muitas inserções aleatórias, suas páginas estarão de 1/2 cheias a cheias. Um índice com muitas páginas meio cheias afetará negativamente o desempenho de leitura (você precisa ler duas páginas meio cheias para ler o mesmo número de registros que uma página inteira 15/16).

Agora, se você estiver inserindo linhas em ordem de índice, o MySQL simplesmente continua adicionando ao final das páginas, preenchendo-as 15/16 e adicionando uma extensão de cada vez nas páginas. Muito menos perda de desempenho, pois não há divisão de páginas, portanto, nenhuma movimentação de dados está envolvida, sem mencionar o benefício de desempenho de leitura de páginas quase inteiras.

Inserções aleatórias também aumentam a fragmentação das páginas, o que pode afetar o desempenho de leitura se você costuma ler um grande número de registros sequenciais (raro).

Além disso, alterar buffer pode afetá-lo.