Lagring av en avståndsmatris i DB

För prestandas skull, och förutsatt att du använder InnoDB, skulle jag förmodligen avnormalisera data lite, så här:

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

Varje par av städer har 2 rader i CITY_DISTANCE som innehåller samma DISTANCE (en för varje riktning). Detta kan uppenbarligen göra det mycket stort och kan leda till datainkonsekvenser (databasen kommer inte att försvara sig från icke-matchande DISTANCE-värden mellan samma städer), och DISTANCE tillhör logiskt sett inte till PK, men håll ut med mig...

InnoDB-tabeller är klustrade , vilket innebär att genom att deklarera PK på detta sätt lägger vi hela tabellen i ett B-träd som är särskilt lämpat för en fråga som denna:

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

Den här frågan returnerar de 5 städerna närmast staden som identifieras av 1 , och kan tillfredsställas med en enkel räckviddsskanning på B-trädet som nämns ovan:

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 kommer automatiskt att skapa ytterligare ett index (på CITY2_ID) på grund av den andra FK, som också kommer att inkludera CITY1_ID och DISTANCE eftersom sekundära index i klustrade tabeller måste täcka PK. Du kanske kan utnyttja det för att undvika duplicerade DISTANCES (skapa uttryckligen index på {CITY2_ID, DISTANCE, CITY1_ID} och låt FK återanvända det och KONTROLLERA (CITY1_ID