过去我曾经使用过许多关系数据库，但是我也了解了所有NoSQL数据库，并且键值存储看起来很有趣。

当我存储几何对象时，我主要使用五个索引列ID， MIN_X，MAX_X，MIN_Y和MAX_Y（其中X和Y在地图投影中）。我不需要其他数据的索引。

我需要X和Y值来查找指定位置（地图矩形）中的对象，并且如果要更新，则需要ID值指定的对象。

有什么办法可以使用键值存储？

#1 楼

我们使用Google AppEngine来运行空间/属性查询，并且主要的问题（从第一天开始）就是如何索引大型的任意大小的线/多边形。点数据并不太困难（请参见geohash，geomodel等），但是随机成簇的小/大多边形集总是一个问题（在某些情况下，仍然是）

我尝试了几种不同的方法GAE上的空间索引版本，但大多数只是以下两个版本的变体。没有一个像SQL数据库一样快，而且都有优点/缺点。不过，对于大多数基于Internet的地图绘制应用程序而言，这种折衷似乎是合理的。同样，下面的两个需要与内存中的几何剔除（通过JTS等）结合使用，以删除任何不适合最终搜索参数的特征。最后，它们依赖于GAE特定的功能，但我确信它可以应用于其他体系结构（或使用TyphoonAE在Linux群集，ec2等上运行）

Grids-打包所有功能将某个区域转换为已知的网格索引。在网格上放置一个小的空间索引，以便您快速浏览其包含的一组要素。对于大多数查询，您只需要快速拉出几个网格，因为您知道确切的网格命名约定及其与K / V实体的关系（获取而不是查询）

优点-速度快，易于实现，无内存占用。

缺点-需要进行预处理，用户需要确定网格大小，多个网格上共享大几何图形，群集会导致网格过载，序列化/反序列化成本可能是个问题（即使通过协议缓冲区）

QuadKeys-这是当前的实现。基本上与Grid相同，只是没有设置网格级别。添加功能时，它们会由完全包含其范围的四键网格索引（或者在某些情况下，当无法使用单个四键时，请分成两部分，请考虑日期线）。找到qk之后，将其拆分为最大数量的较小qk，以提供特征的更细粒度表示。然后，将指向该功能的指针/ bbox打包到一个轻量级的gridindex（一组功能）中，该索引可以查询（原始设计直接查询该功能，但是事实证明这太慢了/如果结果集很大，则需要占用大量CPU）

多边形四键http://www.arc2earth.com/images/help/GAE_QKS_1.png
多边形四键http://www.arc2earth.com/images/help/GAE_QKS_2.png

上面使用的四键命名约定是众所周知的，而且更重要的是，它倾向于保留局部性（在此处进行更多介绍）

上面的多边形看起来像这样：
0320101013123
03201010131212
03201010131213
0320101013132
03201010131133
03201010131302
03201010131303
032010101313002
032010101313003
032010101313012
032010101313013
/> 03201010131312
03201010131313
032010101313102
...

如果查询范围足够小，则可以直接通过qk获取。这是最佳选择，因为它仅是对GAE datatore的单个批处理rpc调用。如果边界足够大，以至于包含太多可能的qks（> 1000），则可以使用过滤器进行查询（例如：qk> = 0320101013和qk <= 0320101013 + \ ufffd）。四键命名约定以及GAE索引字符串的方式允许上面的查询仅获取低于该qk值的现有网格。

还有其他警告和性能问题，但总的来说，它具有以下功能：查询使其变得可行的四键

示例-查询美国县：geojson

优点-非常快，没有网格大小配置，没有内存占用，没有拥挤的网格

缺点-需要进行预处理，在某些情况下可能会超量提取，没有极性数据

空间填充曲线-看看今年Alfred在Google I / O上的NextGen Queries演讲。包含通用的空间/时间填充曲线以及新的MultiQuery运算符（并行运行）将允许进行一些非常酷的空间查询。它会击败传统的SQL性能吗？很难说，但它应该可以很好地扩展。而且我们正在迅速接近一个未来，各种形状/大小的始终可用的移动设备将极大地增加到您的站点/服务的访问量。在选择NoSQL而不是SQL之前，请紧紧围绕您的问题域。在我们的案例中，我真的很喜欢GAE的定价模型，因此确实没有选择，但是如果您不需要扩展，可以节省一些时间，而只使用标准的sql db

评论

您提到了GAE，但您使用的是哪个数据库？有几个：cloud.google.com/products/storage

–唐麦库迪
16年7月28日在15:58

#2 楼

我听说过GeoCouch，它是CouchDB的实现，用于基于位置的数据。而且我还认为MongoDB具有地理空间索引功能。

评论

是的，他们俩都做，SimpleGeo正在为Cassandra建立空间扩展。我在Voldemort或MemCache中什么都没听到

–TheSteve0
2010年7月23日下午4:39
哦，我喜欢SimpleGeo在做什么。我很嫉妒，很想为他们工作！

– JoshFinnie
10 Jul 23 '14：39

#3 楼

这主要是关于算法的问题。堆栈溢出也可能是个好地方。

无论如何，直接问题的答案是“是的，您可以使用kvp存储来表示空间数据。”但是，一个更好的问题可能是“应该使用kvp存储来表示空间数据吗？”

（与其他许多问题一样）该问题的答案是“取决于”。这取决于您的规模，（事务性的）工作负载，数据的性质以及您可以使用的计算基础结构。

kvp存储将具有较低的开销，这可以帮助提高吞吐量用于大量的插入和更新并行处理。但是，执行空间搜索（找到矩形内的所有对象）并不是很快。为此，您需要一个空间索引，例如R-Tree。

但是，如果您的数据量非常大，并且计算机集群很大，那么使用kvp索引可以提供一定的性能。好处。真正确定的唯一方法是使用您希望遇到的实际数据和访问模式进行性能测量。

更新：

这里有更多信息。您可以使用KVP存储进行空间查找。问题是它很慢。要了解原因，请考虑以下内容：

  ***********
  ***********
  ***********
  ***********
  ****###****
  ****###****
  ****###****
  ***********
  ***********
  ***********
  ***********


其中*和＃代表对象，以11x11网格布局，原点位于左上角。想象一下在矩形（4,4）-（7,7）中搜索对象。那应该找到所有的“＃”。假设您使用b +树表示KVP存储中的索引，则可以使用“ X”索引或“ Y”索引查找结果。在这种情况下，哪一个都没有关系。为了便于讨论，我将使用x索引。您将在X索引中执行log（n）查找，以找到X值为“ 4”的第一个节点，然后迭代b + -tree叶子节点，直到找到一个值大于7的节点。遍历x索引，然后您将拒绝任何超出所需y范围的东西。

这很慢。想象一下，在一个具有相同密度（例如100 K * 100 K）的大网格上。您最终将不得不扫描“ 300，000”索引条目以仅找到9条记录。但是，如果使用适当平衡的R-Tree，则索引查找可能仅需要扫描大约90条记录。这是巨大的差异。

但是，问题是保持R-Tree平衡很昂贵。这就是为什么答案是“取决于”以及为什么问题“我应该这样做”比“我应该如何做”更为重要的原因。
如果您多次插入和删除记录，并且通常执行“对象ID”查找，并且不经常执行“空间”查找，因此使用KVP索引可以为您实际希望使用系统的性能提供更好的性能。但是，如果您不经常插入或删除，但是经常进行空间查找，那么您想使用R-Tree。

评论

我不会接受“是的，您可以的”这样的答案。因为我想知道如何。而且“ SHOULD I ..”不是一个更好的问题，因为正如您所说的“这取决于”。

–乔纳斯（Jonas）
2010年7月24日在16:57
我不同意你的看法。如果您想构建一个有用的系统，或者在互联网上为其他构建类似系统的人留下有用的参考，那么“我应该”比“如何”更为重要。为了有帮助，但是我确实为您编辑了答案，以提供有关操作方法的信息。

–斯科特·维斯涅夫斯基
10年7月24日在21:29


@Jonas我相信您获得“建议”答案的原因是您询问问题的方式：“但是我也阅读了所有NoSQL数据库，并且键值存储看起来很有趣。”这具有寻找问题的解决方案的所有特征。

–JasonBirch
2010年7月25日在18:55
NoSQL确实解决了一个问题，但是实际上这是一个没人解决的问题，因为它们没有足够大规模地工作。不幸的是，总是觉得我们自己的系统在总体方案中比实际的系统更大。 :)

–詹姆斯·瑞安（JamesRyan）
2010年8月9日，9：18

#4 楼

如果您使用的是经/纬度值，则可以将geohashes用作商店的价值部分。 dr5regy6rc6ye

使用geohash，您可以开始在geohash的末尾剔除字符以获得不同精度的网格： js实施示例：http：//github.com/davetroy/geohash-js

#5 楼

在大多数情况下，与从键/值或键/值/类型存储相比，从关系数据存储中获得的实用性更高。有效地查询和报告这种数据方案存在相当大的复杂性。

我的建议是在考虑如何使用NoSQL之前，仔细评估您的规模是否真正需要NoSQL。

评论

如果需要计算某个点在几何图形的内部还是外部，这是您可能遇到的问题的一个示例（以及解决方案）。 code.google.com/p/giscloud/wiki/SerializedSpatialIndexes

–乔恩·布林赫斯特（Jon Bringhurst）
10年7月22日在20:20


嘿@Jon，最好将它添加为答案。这样，它就可以独立存在，并且如果人们认为它有优点，您将为它赢得赞誉！

–JasonBirch
2010年7月22日在20:21

#6 楼

看一下这个GAE应用程序，它将JTS几何序列化为BigTable。您也许可以将其用于其他NoSQL存储引擎。

#7 楼

MongoDB具有基于Documents的严格2d [x，y]元组属性创建和使用地理空间索引的功能，并且允许“近”和“边界”类型查询。但是，它不处理任何投影校正，并使用理想的平坦地球模型

#8 楼

我只会将键/值存储区用作缓存层，请参见http://www.membase.org/或http://wiki.basho.com/display/RIAK/How+Things+Work（riak_kv_cache_backend）

取决于您的应用程序需求，您可能仍希望对数据进行SQL访问。

#9 楼

FOSS4G会议即将进行的一些演讲肯定是一个新兴的兴趣领域：



GeoCouch：CouchDB的空间索引
MongoDB的地理空间索引
超越PostGIS
云中的分布式空间索引