Een afstandsmatrix opslaan in DB

Omwille van de prestaties, en ervan uitgaande dat je InnoDB gebruikt, zou ik de gegevens waarschijnlijk een beetje denormaliseren, zoals dit:

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

Elk paar steden heeft 2 rijen in CITY_DISTANCE met dezelfde DISTANCE (één voor elke richting). Dit kan het natuurlijk erg groot maken en kan leiden tot inconsistenties in de gegevens (de database zal zichzelf niet verdedigen tegen niet-overeenkomende DISTANCE-waarden tussen dezelfde steden), en de DISTANCE behoort logischerwijs niet tot de PK, maar wees geduldig...

InnoDB-tabellen zijn geclusterd , wat betekent dat we door de PK op deze specifieke manier te declareren, de hele tabel in een B-Tree plaatsen die bijzonder geschikt is voor een zoekopdracht als deze:

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

Deze zoekopdracht retourneert de 5 steden die het dichtst bij de stad liggen die wordt geïdentificeerd door 1 , en kan worden voldaan door een eenvoudige bereikscan op de hierboven genoemde B-Tree:

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"

Trouwens, de InnoDB zal automatisch nog een index maken (op CITY2_ID) vanwege de tweede FK, die ook de CITY1_ID en DISTANCE zal bevatten, omdat secundaire indexen in geclusterde tabellen PK moeten dekken. U kunt dat misschien misbruiken om dubbele DISTANCE's te vermijden (maak expliciet een index op {CITY2_ID, DISTANCE, CITY1_ID} en laat FK deze opnieuw gebruiken, en CHECK (CITY1_ID