Stocker une matrice de distance dans DB

Pour des raisons de performances, et en supposant que vous utilisez InnoDB, je dénormaliserais probablement un peu les données, comme ceci :

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)
);

Chaque paire de villes a 2 lignes dans CITY_DISTANCE contenant la même DISTANCE (une pour chaque direction). Cela pourrait évidemment le rendre très grand et pourrait conduire à des incohérences de données (la base de données ne se défendra pas des valeurs de DISTANCE non concordantes entre les mêmes villes), et la DISTANCE n'appartient logiquement pas au PK, mais soyez patient...

Les tables InnoDB sont regroupées , ce qui signifie qu'en déclarant le PK de cette manière particulière, nous plaçons toute la table dans un B-Tree particulièrement adapté à une requête comme celle-ci :

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

Cette requête renvoie les 5 villes les plus proches de la ville identifiée par 1 , et peut être satisfait par un simple scan de plage sur le B-Tree mentionné ci-dessus :

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, InnoDB créera automatiquement un index supplémentaire (sur CITY2_ID) à cause du deuxième FK, qui inclura également CITY1_ID et DISTANCE car les index secondaires dans les tables en cluster doivent couvrir PK. Vous pourrez peut-être exploiter cela pour éviter les DISTANCEs en double (créez explicitement un index sur {CITY2_ID, DISTANCE, CITY1_ID} et laissez FK le réutiliser, et CHECK (CITY1_ID