Memorizzazione di una matrice di distanza in DB

Per motivi di prestazioni e supponendo che tu stia utilizzando InnoDB, probabilmente denormalizzerei un po' i dati, in questo modo:

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

Ogni coppia di città ha 2 righe in CITY_DISTANCE contenenti la stessa DISTANCE (una per ogni direzione). Questo ovviamente potrebbe renderlo molto grande e potrebbe portare a incongruenze di dati (il database non si difenderà da valori di DISTANCE non corrispondenti tra le stesse città), e la DISTANCE non appartiene logicamente al PK, ma abbi pazienza...

Le tabelle InnoDB sono raggruppate , il che significa che dichiarando la PK in questo modo particolare mettiamo l'intera tabella in un B-Tree particolarmente adatto per una query come questa:

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

Questa query restituisce le 5 città più vicine alla città identificata da 1 , e può essere soddisfatto da una semplice scansione dell'intervallo sull'albero B di cui sopra:

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"

A proposito, InnoDB creerà automaticamente un altro indice (su CITY2_ID) a causa del secondo FK, che includerà anche CITY1_ID e DISTANCE perché gli indici secondari nelle tabelle raggruppate devono coprire PK. Potresti essere in grado di sfruttarlo per evitare DISTANCE duplicate (creare esplicitamente un indice su {CITY2_ID, DISTANCE, CITY1_ID} e lasciare che FK lo riutilizzi e CHECK (CITY1_ID