Przechowywanie macierzy odległości w DB

Ze względu na wydajność i zakładając, że używasz InnoDB, prawdopodobnie trochę zdenormalizowałbym dane, tak jak poniżej:

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

Każda para miast ma 2 rzędy w CITY_DISTANCE zawierające tę samą DISTANCE (po jednym dla każdego kierunku). Może to oczywiście sprawić, że będzie bardzo duży i może prowadzić do niespójności danych (baza danych nie obroni się przed niezgodnymi wartościami ODLEGŁOŚCI między tymi samymi miastami), a ODLEGŁOŚĆ logicznie nie należy do PK, ale wytrzyma ze mną...

Tabele InnoDB są grupowane , co oznacza, że ​​deklarując PK w ten szczególny sposób, umieszczamy całą tabelę w B-drzewie, które jest szczególnie odpowiednie dla zapytania takiego jak to:

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

To zapytanie zwraca 5 najbliższych miast miastu oznaczonemu przez 1 , i może być spełniony przez proste skanowanie zakresu na wspomnianym powyżej 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"

BTW, InnoDB automatycznie utworzy jeszcze jeden indeks (na CITY2_ID) z powodu drugiego FK, który będzie również zawierał CITY1_ID i DISTANCE, ponieważ indeksy dodatkowe w tabelach klastrowych muszą obejmować PK. Możesz być w stanie to wykorzystać, aby uniknąć zduplikowanych DISTANCE (wyraźnie utwórz indeks dla {CITY2_ID, DISTANCE, CITY1_ID} i pozwól FK go ponownie użyć i CHECK (CITY1_ID