Хранение дистанционной матрицы в БД

Question

Мне нужно отобразить матрицу расстояний на моей веб-странице для всех близлежащих мест города.

Я хотел бы получить все эти данные из веб-сервиса и заранее сохранить в моей БД. Я пытаюсь выяснить лучший дизайн реляционной БД для сохранения таких данных.

Я хочу избежать избыточных данных, а также дизайна, который дает оптимальную производительность.

Я знаю, что DB отношения не лучший вариант для этого, но это то, что я не могу помочь в этой точке.

Вопрос: Итак, каков наилучший дизайн схемы БД для хранения такой информации. Мне нужно будет запросить базу данных, указав только один город, и мне нужно будет отобразить матрицу из 5 или 10 ближайших городов.

Время в пути не так важно, меня беспокоит расстояние в основном.

Answer 1

Ради производительности и при условии, что вы используете InnoDB, я бы, вероятно, немного денормировал данные, например так:

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

Каждая пара городов имеет 2 строки в CITY_DISTANCE, содержащих одинаковую DISTANCE (по одной для каждого направления). Очевидно, это может сделать его очень большим и привести к несоответствиям данных (база данных не будет защищаться от несоответствующих значений DISTANCE между одними и теми же городами), и DISTANCE логически не принадлежит PK, но потерпите меня...

Таблицы InnoDB кластеризованы, что означает, что, объявляя PK таким конкретным способом, мы помещаем всю таблицу в B-Tree, которая особенно подходит для такого запроса:

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

Этот запрос возвращает 5 ближайших городов к городу, указанному 1и может быть удовлетворен простым сканированием диапазона на B-дереве, упомянутом выше:

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"

Кстати, InnoDB автоматически создаст еще один индекс (для CITY2_ID) из-за второго FK, который также будет включать CITY1_ID и DISTANCE, потому что вторичные индексы в кластеризованных таблицах должны покрывать PK. Возможно, вы сможете использовать это, чтобы избежать дублирования DISTANCE (явно создайте индекс для {CITY2_ID, DISTANCE, CITY1_ID} и позвольте FK использовать его повторно, а также CHECK (CITY1_ID

Answer 2

Самый простой способ - сохранить пару городов, а также расстояние и любые другие данные, которые вы хотите отобразить. Я бы хранил сами города в отдельной таблице и сохранял только два ключа и информацию о расстоянии в таблице расстояний.

Я уверен, что вы хотите отобразить только 5 или 10 ближайших, вы можете начать только с добавления этих записей. Это означает, что для N городов вы получите только N*10 записей в базе данных, которые должны быть достаточно масштабируемыми.

Даже при большем количестве записей производительность должна быть хорошей, если вы добавите правильные индексы.