O banco de dados armazena o valor indexado como uma B-Tree chave e o ponteiro de registro como uma B-Tree valor.

Sempre que você pesquisa um registro que contém um determinado valor de uma coluna indexada, o mecanismo localiza a chave que contém esse valor na B-Tree , recupera o ponteiro para o registro e busca o registro.

O que exatamente é um "ponteiro de registro" depende do mecanismo de armazenamento.

• 
  Em MyISAM , o ponteiro de registro é um deslocamento para o registro no MYI Arquivo.
  
• 
  Em InnoDB , o ponteiro de registro é o valor da PRIMARY KEY .
  

Em InnoDB , a própria tabela é uma B-Tree com uma PRIMARY KEY como uma B-Tree chave. Isso é o que chamamos de "índice clusterizado" ou "tabela organizada por índice". Neste caso, todos os outros campos são armazenados como uma B-Tree valor.

Em MyISAM , os registros são armazenados sem nenhuma ordem especial. Isso é chamado de "armazenamento heap".