Menyimpan matriks jarak dalam DB

Demi kinerja, dan dengan asumsi Anda menggunakan InnoDB, saya mungkin akan sedikit mendenormalisasi data, seperti ini:

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

Setiap pasangan kota memiliki 2 baris dalam CITY_DISTANCE yang berisi DISTANCE yang sama (satu untuk setiap arah). Ini jelas bisa membuatnya sangat besar dan dapat menyebabkan inkonsistensi data (database tidak akan mempertahankan diri dari nilai DISTANCE yang tidak cocok antara kota yang sama), dan DISTANCE secara logis bukan milik PK, tetapi bersabarlah ...

Tabel InnoDB dikelompokkan , yang berarti bahwa dengan mendeklarasikan PK dengan cara khusus ini, kami menempatkan seluruh tabel dalam B-Tree yang sangat cocok untuk kueri seperti ini:

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

Kueri ini mengembalikan 5 kota terdekat dengan kota yang diidentifikasi dengan 1 , dan dapat dipenuhi dengan pemindaian jarak sederhana pada B-Tree yang disebutkan di atas:

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 akan secara otomatis membuat satu indeks lagi (pada CITY2_ID) karena FK kedua, yang juga akan menyertakan CITY1_ID dan DISTANCE karena indeks sekunder dalam tabel berkerumun harus mencakup PK. Anda mungkin dapat memanfaatkannya untuk menghindari duplikasi DISTANCE (secara eksplisit membuat indeks pada {CITY2_ID, DISTANCE, CITY1_ID} dan membiarkan FK menggunakannya kembali, dan CHECK (CITY1_ID