У меня есть геометрическая диаграмма, состоящая из 5000 ячеек, каждая из которых представляет собой произвольный многоугольник. Мое приложение должно будет сохранить много таких диаграмм.
Я решил, что мне нужно использовать базу данных для выполнения индексированных запросов к этой карте. Загрузка всех картографических данных слишком неэффективна для быстрых ответов на простые запросы.
Я добавил данные ячейки в базу данных. Он имеет довольно простую структуру:
CREATE TABLE map_cell (
map_id INT NOT NULL ,
cell_index INT NOT NULL ,
...
PRIMARY KEY (map_id, cell_index)
)
5000 строк на карту — это немало, но запросы должны оставаться эффективными для миллионов строк, поскольку основные индексы соединения могут быть кластеризованы. Если он становится слишком громоздким, его можно разделить по границам map_id. Несмотря на большое количество строк на карту, эта таблица вполне масштабируема.
Проблема возникает с хранением данных, описывающих, какие ячейки соседствуют друг с другом. Отношение соседней ячейки — это отношение «многие ко многим» к одной и той же таблице. Есть также очень большое количество таких отношений на карту. Нормализованная таблица, вероятно, будет выглядеть примерно так:
CREATE TABLE map_cell_neighbors (
id INT NOT NULL AUTO INCREMENT ,
map_id INT NOT NULL ,
cell_index INT NOT NULL ,
neighbor_index INT ,
...
INDEX IX_neighbors (map_id, cell_index)
)
Для этой таблицы требуется суррогатный ключ, который никогда не будет использоваться в объединении. Кроме того, эта таблица содержит повторяющиеся записи: если ячейка 0 соседствует с ячейкой 1, то ячейка 1 всегда является соседом ячейки 0. Я могу удалить эти записи за счет некоторого дополнительного места в индексе:
CREATE TABLE map_cell_neighbors (
id INT NOT NULL AUTO INCREMENT ,
map_id INT NOT NULL ,
neighbor1 INT NOT NULL ,
neighbor2 INT NOT NULL ,
...
INDEX IX_neighbor1 (map_id, neighbor1),
INDEX IX_neighbor2 (map_id, neighbor2)
)
Я не уверен, какой из них будет считаться более «нормализованным», поскольку вариант 1 включает в себя повторяющиеся записи (включая дублирование любых свойств, которые имеет отношение), а вариант 2 представляет собой довольно странный дизайн базы данных, который просто не кажется нормализованным. Ни один из вариантов не очень экономичен в пространстве. Для 10 карт вариант 1 использовал 300 000 строк, занимающих 12 МБ файлового пространства. Вариант 2: 150 000 строк занимают 8 МБ файлового пространства. В обеих таблицах индексы занимают больше места, чем данные, учитывая, что данные должны занимать около 20 байт на строку, но на самом деле они занимают 40-50 байт на диске.
Третий вариант вообще не будет нормализован, но будет невероятно эффективным с точки зрения пространства и строк. Это включает в себя размещение поля VARBINARY в map_cell и сохранение бинарного списка соседей в самой таблице ячеек. Это займет 24-36 байтов на ячейку, а не 40-50 байтов на отношение. Это также уменьшит общее количество строк, а запросы к таблице ячеек будут выполняться очень быстро из-за кластеризованного первичного ключа. Однако выполнить соединение с этими данными было бы невозможно. Любые рекурсивные запросы должны выполняться шаг за шагом. Кроме того, это просто очень уродливый дизайн базы данных.
К сожалению, мне нужно, чтобы мое приложение хорошо масштабировалось и не сталкивалось с узкими местами SQL всего с 50 картами. Если я не могу придумать что-то еще, последний вариант может быть единственным, который действительно работает. Прежде чем запрограммировать такую гнусную идею в код, я хотел убедиться, что четко просматриваю все варианты. Может быть другой шаблон проектирования, о котором я не думаю, или, может быть, проблемы, которые я предвижу, не так серьезны, как кажутся. В любом случае, я хотел получить мнение других людей, прежде чем заходить слишком далеко.
Наиболее сложными запросами к этим данным будут поиск путей и обнаружение путей. Это будут рекурсивные запросы, которые начинаются с определенной ячейки, проходят через соседей в течение нескольких итераций и собирают/сравнивают свойства этих ячеек. Я почти уверен, что не могу сделать все это на SQL, скорее всего, везде будет какой-то код приложения. Я хотел бы иметь возможность выполнять подобные запросы среднего размера и получать результаты за приемлемое время, чтобы чувствовать себя «отзывчивым» к пользователю, около секунды. Общая цель состоит в том, чтобы не допустить, чтобы большие размеры таблиц вызывали повторяющиеся запросы или рекурсивные запросы с фиксированной глубиной, занимающие несколько секунд или более.
