Por uma questão de desempenho, e supondo que você esteja usando o InnoDB, eu provavelmente desnormalizaria os dados um pouco, assim:
CREATE TABLE CITY (
CITY_ID INT PRIMARY KEY
);
CREATE TABLE CITY_DISTANCE (
CITY1_ID INT,
CITY2_ID INT,
DISTANCE NUMERIC NOT NULL,
PRIMARY KEY (CITY1_ID, DISTANCE, CITY2_ID),
FOREIGN KEY (CITY1_ID) REFERENCES CITY (CITY_ID),
FOREIGN KEY (CITY2_ID) REFERENCES CITY (CITY_ID)
);
Cada par de cidades tem 2 linhas em CITY_DISTANCE contendo a mesma DISTANCE (uma para cada direção). Isso obviamente poderia torná-lo muito grande e poderia levar a inconsistências de dados (o banco de dados não se defenderá de valores de DISTANCE não correspondentes entre as mesmas cidades), e a DISTANCE não pertence logicamente ao PK, mas tenha paciência comigo ...
As tabelas InnoDB são agrupadas , o que significa que, ao declarar o PK dessa maneira específica, colocamos a tabela inteira em uma B-Tree que é particularmente adequada para uma consulta como esta:
SELECT CITY2_ID, DISTANCE
FROM CITY_DISTANCE
WHERE CITY1_ID = 1
ORDER BY DISTANCE
LIMIT 5
Esta consulta retorna as 5 cidades mais próximas da cidade identificada por
1 , e pode ser satisfeito por uma simples varredura de intervalo na B-Tree mencionada acima:id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE CITY_DISTANCE ref PRIMARY PRIMARY 4 const 6 "Using where; Using index"
BTW, o InnoDB criará automaticamente mais um índice (em CITY2_ID) por causa do segundo FK, que também incluirá o CITY1_ID e DISTANCE porque índices secundários em tabelas clusterizadas devem cobrir PK. Você pode explorar isso para evitar DISTANCEs duplicadas (criar explicitamente o índice em {CITY2_ID, DISTANCE, CITY1_ID} e deixar FK reutilizá-lo e CHECK (CITY1_ID
