Almacenar una matriz de distancia en DB

Por el bien del rendimiento, y suponiendo que esté usando InnoDB, probablemente desnormalizaría un poco los datos, así:

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 ciudades tiene 2 filas en CITY_DISTANCE que contienen la misma DISTANCIA (una para cada dirección). Obviamente, esto podría hacerlo muy grande y podría generar inconsistencias en los datos (la base de datos no se defenderá de los valores de DISTANCIA que no coinciden entre las mismas ciudades), y la DISTANCIA no pertenece lógicamente al PK, pero tengan paciencia conmigo...

Las tablas InnoDB están agrupadas , lo que significa que al declarar el PK de esta manera particular, colocamos toda la tabla en un B-Tree que es particularmente adecuado para una consulta como esta:

SELECT CITY2_ID, DISTANCE
FROM CITY_DISTANCE
WHERE CITY1_ID = 1
ORDER BY DISTANCE
LIMIT 5

Esta consulta devuelve las 5 ciudades más cercanas a la ciudad identificada por 1 , y se puede satisfacer con un simple escaneo de rango en el B-Tree mencionado anteriormente:

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"

Por cierto, InnoDB creará automáticamente un índice más (en CITY2_ID) debido al segundo FK, que también incluirá CITY1_ID y DISTANCE porque los índices secundarios en tablas agrupadas deben cubrir PK. Es posible que pueda explotar eso para evitar DISTANCIAS duplicadas (cree explícitamente un índice en {CITY2_ID, DISTANCE, CITY1_ID} y deje que FK lo reutilice, y CHECK (CITY1_ID