Com a maioria das implementações, a chave é simplesmente uma chave mais longa que inclui todos os valores de chave, com um separador. Não há mágica lá;-)
No seu exemplo, os valores-chave podem ser algo como
"123499|John Doe|Conway, NH" "32144|Bill Gates| Seattle, WA"
Uma das características desses índices com chaves compostas é que os nós intermediários da árvore podem ser usados em alguns casos para "cobrir" a consulta.
Por exemplo, se a consulta for para encontrar o Nome e a Cidade de acordo com o ID, já que o ID é o primeiro no índice, o índice pode pesquisar por isso com eficiência. Uma vez no nó intermediário, ele pode "analisar" o Nome e a Cidade, a partir da chave, e não precisa ir ao nó folha para ler o mesmo.
Se, no entanto, a consulta também quisesse exibir o número de telefone, a lógica seguiria a folha quando o registro completo fosse encontrado.
