Lagring af en afstandsmatrix i DB

For ydeevnens skyld, og hvis du antager, at du bruger InnoDB, ville jeg nok denormalisere dataene lidt, sådan her:

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

Hvert bypar har 2 rækker i CITY_DISTANCE, der indeholder den samme DISTANCE (en for hver retning). Dette kunne tydeligvis gøre det meget stort og kan føre til datainkonsistens (databasen vil ikke forsvare sig mod ikke-matchende DISTANCE-værdier mellem samme byer), og DISTANCE hører logisk ikke til PK, men bær over med mig...

InnoDB-tabeller er grupperet , hvilket betyder, at ved at deklarere PK'en på denne særlige måde sætter vi hele tabellen i et B-Tree, der er særligt velegnet til en forespørgsel som denne:

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

Denne forespørgsel returnerer de nærmeste 5 byer til byen identificeret med 1 , og kan tilfredsstilles ved en simpel rækkeviddescanning på B-træet nævnt ovenfor:

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 vil InnoDB automatisk oprette et indeks mere (på CITY2_ID) på grund af den anden FK, som også vil inkludere CITY1_ID og DISTANCE, fordi sekundære indekser i klyngede tabeller skal dække PK. Du kan muligvis udnytte det til at undgå duplikerede DISTANCEr (opret eksplicit indeks på {CITY2_ID, DISTANCE, CITY1_ID} og lad FK genbruge det, og CHECK (CITY1_ID