问题标签 [spatial-index]

我目前有一个站点，其中包含一个包含 Lat/Long 浮点列的表，以及这 2 列以及我需要检索的另一列的索引。

我一直在查询这个表以获取从某个点开始落在一个半径内的行（我实际上是为了速度而得到一个正方形），但我只需要已经索引的字段，所以这个索引实际上是覆盖，而执行计划只有两个步骤：

现在，我正在尝试利用 SQL 2008 的空间特性。我已经创建了 Geography 列，填充了它，创建了空间索引，工作正常。

一切正常，除了执行计划有一百万个步骤，74% 的时间花在聚集索引搜索上，它将在空间索引中找到的行连接到实际表中，以获取其余的数据...
（空间索引搜索占执行计划成本的 1%）

因此，显然，它正在适当地使用空间索引，并且通过 Lat/Long 上的“常规”索引比以前更快地找到我需要的记录，但是加入主表是在杀死我，空间查询需要 7 倍只要是我的旧的。

有没有办法向空间索引添加更多列，以便它可以覆盖并且可以一步完成，就像以前一样？
我还能做些什么来改善这种情况吗？

更新：我发现“常规”索引可以使用 INCLUDE 关键字“包含”其他列（我不知道，我曾经只是将列包含在索引本身中）
根据此处的文档，该子句不是空间索引的一个选项......有什么想法吗？

谢谢！
丹尼尔

我们有一个 x,y 对的列表。每对代表二维空间上的一个点。我想从这个列表中找到离特定点 xq,yq 最近的点。这个问题的最佳性能关键算法是什么？Lisp of points 不会改变；这意味着我不需要执行插入和删除。我只想找到这个集合中目标 xq,yq 点的最近邻居。

编辑1：谢谢大家！正如 Stephan202 猜对的那样，我想反复这样做；像一个函数。列表不一定是排序的（实际上我不明白它是如何排序的？就像一个具有 2 列 a 和 y 的主键的表？如果这有帮助，那么我会对其进行排序）。

我会根据列表构造一次数据结构，然后我会在函数中使用这个生成的数据结构（如果这个过程本身是相关的）。

谢谢雅各布；KD-Tree 数据结构似乎是一个很好的答案候选者（我觉得确实如此。当我得到一些相关结果时，我会更新）。

编辑2：我发现，这个问题被命名为“最近的邻居”！

编辑 3：第一个标题是“In Search of an Algorithm (for Spatial-Querying and Spatial-Indexing) (Nearest Neighbor)”；我选择了一个新标题：“解决最近邻的最佳性能关键算法”。由于我不想对我的初始数据执行插入和删除操作，而我只想要离它们最近的一个到一个新点（不会被插入），我选择（当前）在 KD-Trees 上工作。谢谢大家！

我在 C# 中找到了一些开源 R-Tree 实现，但没有文档，也没有被开发人员以外的其他人使用的迹象。

我正在考虑在不使用 SQL2008 的情况下在 .NET 中实现空间查询。第一个要求是能够创建（BTree 风格的）空间索引并能够查询它。

尽管 SQL 2008 附带了用于这些类型的 .NET 库，但您需要将 SQL 用于空间索引。

有没有人使用任何 .NET 库来存储空间数据（操作系统或商业）？我正在查看 NetTopologySuite，但它看起来很安静，我不想要一个死库。

有人有使用 lucene 的空间搜索组件（lucene 3.0）的经验吗？

我尝试了一个非常简单的示例，但无法让搜索返回任何内容，请参阅下面的所有代码

任何帮助/意见将不胜感激。

二维空间索引问题：

您将什么称为本质上是无限*四叉树的数据结构，其节点既不包含绝对坐标也不包含绝对比例——其中每个节点的坐标系已归一化为单位平方 (0,0)-(1,1 ), 哪个顶级节点不是绝对固定的？

当然，它是一个四叉树——但它是什么类型的四叉树？（有一个通用名称吗？我在文献中看到了几十种命名和定义的四叉树，但不是这个特定的。）

为了渲染一个场景，你会得到一些起始节点（不一定是根节点）、它的像素大小以及它在屏幕上的位置。然后，您通过使用当前变换矩阵缩放其坐标来绘制节点内的所有对象，您将其压入堆栈并在沿着树向下时减半。因此，节点的绝对坐标仅在渲染期间通过临时工作变量可用，并且不包含在数据结构本身中。

如果一个节点内的对象移动到节点之外（例如，在单位正方形之外），您将它传递给父节点以重新分配给另一个节点。如果一个物体变得碎片化（例如，一颗被子弹击中的小行星），较小的部分将传递给子节点，子节点必须适当地缩放坐标以保持每个节点内的单位平方归一化。

这里与空间索引中使用的传统四叉树实现的主要区别在于对象的坐标始终相对于包含它们的节点的坐标系。这种相对主义不仅适用于位置，也适用于规模。

* Infinite 缺少绝对坐标；当用于绝对定位时，即使是双精度浮点坐标也会限制位置和大小。

像大多数普通的 PHP Web 开发人员一样，我使用 MySql 作为 RDBMS。MySql（也和其他 RDBMS 一样）提供了 SPATIAL INDEX 功能，但我不太明白。我已经用谷歌搜索了它，但没有找到明确的现实世界例子来澄清我对它的坏了解。

有人可以向我解释一下什么是空间索引，我应该什么时候使用它？

我有一个大表（> 50m 行），其中包含一些带有 ID 和时间戳的数据：

...在 . 上有一个多列索引(id, timestamp)。

我需要查询表以选择时间戳在两个日期之间的具有特定 ID 的所有行，我目前正在使用：

目前，这在高端机器上需要 2 多分钟（2x 3Ghz 双核 Xeons w/HT，16GB RAM，RAID 0 中的 2x 1TB 驱动器），我真的很想加快速度。

我发现了这个建议使用空间索引的技巧，但它给出的示例是针对 IP 地址的。然而，速度提升（436s 到 3s）令人印象深刻。

如何将它与时间戳一起使用？

我正在寻找一种为矩形提供索引的数据结构。我需要插入算法尽可能快，因为矩形将在屏幕上移动（考虑用鼠标将矩形拖动到新位置）。

我研究过 R-Trees、R+Trees、kD-Trees、Quad-Trees 和 B-Trees，但据我了解，插入通常很慢。我更喜欢以亚线性时间复杂度插入，所以也许有人可以证明我对列出的任何一个数据结构都错了。

我应该能够查询数据结构，以了解哪些矩形在点（x，y）或哪些矩形与矩形相交（x，y，宽度，高度）。

编辑：我想要插入这么快的原因是因为如果你想到一个矩形在屏幕上移动，它们将不得不被删除然后重新插入。

谢谢！

我正在尝试为我正在处理的数据集选择一个体面的 SQL Server 2008 空间索引设置，这很有趣。

数据集是多边形，代表整个地球的轮廓。表中有 106,000 行，多边形存储在几何字段中。

我遇到的问题是许多多边形覆盖了地球的很大一部分。这似乎很难获得将消除主过滤器中的许多行的空间索引。例如，查看以下查询：

这是查询与表中仅两个多边形相交的区域。无论我选择哪种空间索引设置组合，Filter() 总是返回大约 60,000 行。

用 STIntersects() 替换 Filter() 当然只返回我想要的两个多边形，但当然需要更长的时间（Filter() 是 6 秒，STIntersects() 是 12 秒）。

谁能给我任何提示，说明是否存在可能改进 60,000 行的空间索引设置，或者我的数据集是否与 SQL Server 的空间索引不匹配？

更多信息：

按照建议，我在全球使用 4x4 网格将多边形拆分。我看不到使用 QGIS 的方法，所以我编写了自己的查询来做到这一点。首先我定义了 16 个边界框，第一个看起来像这样：

然后我使用每个边界框来选择和截断与该框相交的多边形：

我显然对 4x4 网格中的所有 16 个边界框都这样做了。最终结果是我有一个大约 107,000 行的新表（这证实了我实际上并没有很多巨大的多边形）。

我添加了一个空间索引，每个对象有 1024 个单元格，每个级别的单元格为低、低、低、低。

然而，非常奇怪的是，这个带有分割多边形的新表的性能仍然与旧表相同。执行上面列出的 .Filter仍会返回约 60,000 行。我真的完全不明白这一点，显然我不明白空间索引是如何工作的。

矛盾的是，虽然 .Filter() 仍然返回约 60,000 行，但它提高了性能。.Filter() 现在需要大约 2 秒而不是 6 秒，.STIntersects() 现在需要 6 秒而不是 12 秒。

此处要求是索引的 SQL 示例：

尽管请记住，我已经为每个对象的网格和单元格尝试了一系列不同的设置，每次都得到相同的结果。

以下是运行 sp_help_spatial_geometry_index 的结果，这是在我的拆分数据集上，其中没有单个多边形占据地球的 1/16 以上：

Base_Table_Rows 215138 Bounding_Box_xmin -90 Bounding_Box_ymin -180 Bounding_Box_xmax 90 Bounding_Box_ymax 180 Grid_Size_Level_1 64 Grid_Size_Level_2 64 Grid_Size_Level_3 64 Grid_Size_Level_4 64 CELLS_PER_OBJECT 16个Total_Primary_Index_Rows 378650个Total_Primary_Index_Pages 1129 Average_Number_Of_Index_Rows_Per_Base_Row 1 Total_Number_Of_ObjectCells_In_Level0_For_QuerySample 1 Total_Number_Of_ObjectCells_In_Level0_In_Index 60956 Total_Number_Of_ObjectCells_In_Level1_In_Index 361 Total_Number_Of_ObjectCells_In_Level2_In_Index 2935 Total_Number_Of_ObjectCells_In_Level3_In_Index 32420 Total_Number_Of_ObjectCells_In_Level4_In_Index 281978 Total_Number_Of_Interior_ObjectCells_In_Level2_In_Index 1 Total_Number_Of_Interior_ObjectCells_In_Level3_In_Index 49 Total_Number_Of_Interior_ObjectCells_In_Level4_In_Index4236 Total_Number_Of_Intersecting_ObjectCells_In_Level1_In_Index 29 Total_Number_Of_Intersecting_ObjectCells_In_Level2_In_Index 1294 Total_Number_Of_Intersecting_ObjectCells_In_Level3_In_Index 29680 Total_Number_Of_Intersecting_ObjectCells_In_Level4_In_Index 251517 Total_Number_Of_Border_ObjectCells_In_Level0_For_QuerySample 1 Total_Number_Of_Border_ObjectCells_In_Level0_In_Index 60956 Total_Number_Of_Border_ObjectCells_In_Level1_In_Index 332 Total_Number_Of_Border_ObjectCells_In_Level2_In_Index 1640 Total_Number_Of_Border_ObjectCells_In_Level3_In_Index 2691 Total_Number_Of_Border_ObjectCells_In_Level4_In_Index 26225 Interior_To_Total_Cells_Normalized_To_Leaf_Grid_Percentage 0.004852925 Intersecting_To_Total_Cells_Normalized_To_Leaf_Grid_Percentage 0.288147586 Border_To_Total_Cells_Normalized_To_Leaf_Grid_Percentage 99。70699949 Average_Cells_Per_Object_Normalized_To_Leaf_Grid 405.7282349 Average_Objects_PerLeaf_GridCell 0.002464704 Number_Of_SRIDs_Found 1 Width_Of_Cell_In_Level1 2.8125 Width_Of_Cell_In_Level2 0.043945313 Width_Of_Cell_In_Level3 0.000686646 Width_Of_Cell_In_Level4 1.07E-05 5.625 Height_Of_Cell_In_Level1 Height_Of_Cell_In_Level2 0.087890625 Height_Of_Cell_In_Level3 0.001373291 Height_Of_Cell_In_Level4 2.15E-05 Area_Of_Cell_In_Level1 1012.5 Area_Of_Cell_In_Level2 15.8203125 Area_Of_Cell_In_Level3 0.247192383 Area_Of_Cell_In_Level4 0.003862381 CellArea_To_BoundingBoxArea_Percentage_In_Level1 1.5625 CellArea_To_BoundingBoxArea_Percentage_In_Level2 0.024414063 CellArea_To_BoundingBoxArea_Percentage_In_Level3 0.00038147 CellArea_To_BoundingBoxArea_Percentage_In_Level4 5。96E-06 Number_Of_Rows_Selected_By_Primary_Filter 60956 Number_Of_Rows_Selected_By_Internal_Filter 0 Number_Of_Times_Secondary_Filter_Is_Called 60956 Number_Of_Rows_Output 2 Percentage_Of_Rows_NotSelected_By_Primary_Filter 71.66655821 Percentage_Of_Primary_Filter_Rows_Selected_By_Internal_Filter 0 Internal_Filter_Efficiency 0 Primary_Filter_Efficiency 0.003281055

“Base_Table_Rows 215138”对我来说没有多大意义，表中有 107,000 行，而不是 215,000

渲染后的数据集如下所示：（ _{来源：norman.cx）}

进一步的研究：

我继续对这些数据的初级过滤器性能不佳感到困惑。所以我做了一个测试，看看我的数据是如何分裂的。使用我原来的未拆分功能，我在表格中添加了一个“单元格”列。然后我运行了 16 个查询来计算该特征跨越的 4x4 网格中有多少个单元格。所以我为每个单元格运行了这样的查询：

如果我再查看表​​中的“单元格”列，我的整个数据集中只有 672 个特征与 4x4 网格中的超过 1 个单元格相交。那么，从字面上看，主过滤器如何返回 60,000 个特征来查看一个 200 英里宽的小矩形？

在这一点上，看起来我可以编写自己的索引方案，它会比 SQL Server 对这些功能的执行方式更好。