我有一个由 5,000 个单元组成的几何图，每个单元都是一个任意多边形。我的应用程序将需要保存许多这样的图表。
我已经确定我需要使用数据库来对这张地图进行索引查询。加载所有地图数据效率太低，无法快速响应简单查询。
我已将单元格数据添加到数据库中。它有一个相当简单的结构：
CREATE TABLE map_cell (
map_id INT NOT NULL ,
cell_index INT NOT NULL ,
...
PRIMARY KEY (map_id, cell_index)
)
每个映射 5,000 行是相当多的，但查询应该保持对数百万行的高效，因为可以聚集主连接索引。如果它变得太笨重，可以在 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 行，占用了 12M 的文件空间。选项 2 是 150,000 行占用 8M 文件空间。在这两个表上，索引占用的空间比数据多，考虑到数据应该是每行大约 20 个字节，但实际上它在磁盘上占用了 40-50 个字节。
第三个选项根本不会被规范化，但会非常节省空间和行。它涉及在 map_cell 中放置一个 VARBINARY 字段，并在单元表本身中存储一个二进制打包的邻居列表。这将需要每个单元 24-36 个字节，而不是每个关系 40-50 个字节。它还会减少总行数，并且由于聚集的主键，对单元表的查询会非常快。但是，对这些数据执行连接是不可能的。任何递归查询都必须一次完成一个步骤。此外，这只是非常丑陋的数据库设计。
不幸的是，我需要我的应用程序能够很好地扩展，而不是仅使用 50 个映射就遇到 SQL 瓶颈。除非我能想到别的东西，否则后一种选择可能是唯一真正有效的选择。在我将这样一个卑鄙的想法提交给代码之前，我想确保我清楚地查看了所有选项。可能还有另一种我没有想到的设计模式，或者我预见的问题可能并不像看起来那么糟糕。无论哪种方式，我都想在过分深入之前获得其他人的意见。
针对这些数据最复杂的查询是路径查找和路径发现。这些将是从特定单元格开始的递归查询，经过多次迭代遍历邻居并收集/比较这些单元格的属性。我很确定我不能在 SQL 中完成所有这些，可能会有一些应用程序代码贯穿始终。我希望能够执行这样大小适中的查询，并在可接受的时间内获得结果，让用户感觉“响应”大约一秒钟。总体目标是防止大表大小导致重复查询或固定深度递归查询花费几秒钟或更长时间。