经开区网站建设,手机商店app下载,橘子seo,西安做网站收费价格目录
一、空间索引快速理解
#xff08;一#xff09;区域编码
#xff08;二#xff09;区域编码检索
#xff08;三#xff09;Geohash 编码
#xff08;四#xff09;RTree及其变体
二、业内方案选取
三、分布式空间索引架构
#xff08;一#xff09;PG数…目录
一、空间索引快速理解
一区域编码
二区域编码检索
三Geohash 编码
四RTree及其变体
二、业内方案选取
三、分布式空间索引架构
一PG数据变更通知服务
二空间索引管理服务
三空间索引SDK
参考文章 一、空间索引快速理解
假设用户A使用某社交应用希望查看附近的人以扩展社交圈或寻找志趣相投的人。
假设用户B使用某共享单车应用希望看到当前附近可以骑行的车以快速查找并进行骑行计划。
这两类场景都需要通过地理位置服务来实现“附近的X”功能。 可以通过限定“附近”的范围来减少检索空间。一般可以将所有的检索空间划分为多个区域并做好编号然后以区域编号为 key 做好索引。以查找附近的人为例可以先快速查询到自己所属的区域然后再将该区域中所有人的位置取出计算和每一个人的距离就可以了。
一区域编码
对于一个完整的二维空间可以通过二分的思想进行均匀划分。具体方法是在水平方向和垂直方向上分别进行二分形成四个均匀划分的子空间。对这四个子空间进行编号可以使用两个比特位。在水平方向上用 0 表示左边的区域用 1 表示右边的区域在垂直方向上用 0 表示下面的区域用 1 表示上面的区域。按照顺时针的顺序从左下角开始编号为 00、01、11 和 10。 通过这样的划分和编号方式整个二维空间就被划分为多个具有唯一标识的区域。通过继续沿用区域划分的思路可以将每个区域再分为四块形成更细致的划分。整个空间会被划分成16块区域对应的编号也会增加两位。例如编号为01的区域被划分成4小块分别为0100、0101、0110、0111。这就是区域编码的基本思路。
二区域编码检索
有了区域编码方式后查询附近的人可以利用区域编码的一维特性将二维空间的两个维度用一维编码表示。 具体的查询步骤如下
区域编码存储 将区域编码作为 key 存储在有序数组中。有序数组的排序方式按照区域编码的大小进行排列。二分查找 使用二分查找技术在有序数组中快速定位自己所属区域的编码。这种方式适用于静态的区域信息如果区域动态增加也可以考虑使用二叉检索树或跳表等数据结构进行索引。区域查询 查询到自己所属区域的编码后从索引中获取所有属于该区域的用户信息。这一步可以通过有序数组、二叉检索树、跳表等结构进行高效查询。计算距离和排序 对获取的用户信息进行距离计算计算每个用户与自己的距离。最后根据距离排序展现给用户。
但找到的“附近的人”实际上是同一区域的人并不一定是离自己最近的人。对于边缘区域的用户可能在邻接区域里因此在实际应用中需要权衡查询效率和精确度。如图中的蓝色圆点相比绿色圆点反而是更远的。
为了更精确地找到附近的人可以建立一个更大的候选集合将目标区域周围的邻接区域的用户都加入然后进行距离计算和排序。 操作步骤如下 确定查询半径 根据期望的查询半径以当前区域为中心向周围扩散。例如如果查询半径是一个区域边长的一半可以涵盖目标区域周围一圈的邻接区域。 扩展候选集 将扩展后的邻接区域中的用户都加入候选集。在示例中如果考虑目标区域周围的8个邻接区域可以确保不遗漏任何可能的附近用户。 距离计算和排序 对候选集中的用户进行距离计算计算每个用户与目标用户的距离。最后根据距离排序得到最终的查询结果。
虽然这样的操作会增加计算量但可以提供更精确的解。如果希望降低计算量可以考虑提高区域划分的粒度使得在相同查询半径下需要检索的用户数量减少。这样可以在保持查询效果的情况下降低计算复杂度。
回到区域编码方案本身要快速寻找目标区域周围的邻接区域的编码可以利用区域编码的奇偶位拆分水平编码和垂直编码。 通过对这两块编码进行操作可以得到不同方向上邻接的8个区域的编码。具体操作步骤如下 分解编码 对于一个区域编码例如0110可以分解成水平编码01和垂直编码10。 获取邻接区域编码 对于当前区域分别对水平编码和垂直编码进行加1或减1的操作得到不同方向上邻接的8个区域的编码。例如如果水平编码是01那么右边区域的水平编码就是10垂直编码相同。
通过这样的操作可以快速获取目标区域周围邻接区域的编码进而进行候选集的扩展和附近用户的查询。这种方法利用了区域编码的特性实现了高效的邻接区域查找。
三Geohash 编码 在实际工作中用户的地理位置坐标通常用经纬度表示而地球可以看作一个大的二维空间经度和纬度就是这个空间的水平和垂直切分方向。地球的纬度区间是[-90,90]经度是[-180,180]。
如果给出的用户纬度垂直方向坐标是 39.983429经度水平方向坐标是 116.490273那求这个用户所属的区域编码的过程就可以总结为 3 步
在纬度方向上第一次二分39.983429 在[0,90]之间[0,90]属于空间的上半边因此我们得到编码 1。然后在[0,90]这个空间上第二次二分39.983429 在[0,45]之间[0,45]属于区间的下半边因此得到编码 0。两次划分之后得到的编码就是 10。在经度方向上第一次二分116.490273 在[0,180]之间[0,180]属于空间的右半边因此得到编码 1。然后在[0,180]这个空间上第二次二分116.490273 在[90,180]之间[90,180]还是属于区间的右半边因此得到的编码还是 1。两次划分之后得到的编码就是 11。纬度的编码和经度的编码交叉组合起来先是经度再是纬度。这样就构成了区域编码为 1110。
实际上如果区域划分的粒度非常细就要持续、多次二分。而每多二分一次我们就需要增加一个比特位来表示编码。 如果经度和纬度各二分 15 次的话那我们就需要 30 个比特位来表示一个位置的编码。那上面例子中的编码就会是 11100 11101 00100 01111 00110 11110。
这样得到的编码会特别长为了简化编码表示可以以 5 个比特位为一个单位把长编码转为 base32 编码最终得到的就是 wx4g6y。这种将经纬度坐标转换为字符串的编码方式就叫作 Geohash 编码。大多数应用都会使用 Geohash 编码进行地理位置的表示以及在很多系统中比如Redis、MySQL 以及 Elastic Search 中也都支持 Geohash 数据的存储和查询。
四RTree及其变体
另一种空间索引方法是按照数据进行划分通常是对空间对象的外接矩形MBR进行多级划分。这种方法使用一棵多叉树来保存MBR和空间对象其中每一级作为树的一层。只有叶子节点存储实际的空间对象而非叶子节点存储更大范围的MBR。这类空间索引的典型代表是RTree及其变体。 假设我们有一个城市地图上的空间数据集其中包含了许多建筑物空间对象。希望使用RTree来组织这些建筑物的位置信息以便能够高效地进行范围查询和邻近查询。 建立RTree 开始时RTree的根节点包含整个城市的外接矩形。每个节点都有一个关联的MBR而叶子节点包含实际的建筑物信息。 插入建筑物 当新的建筑物被插入时RTree会调整相应的节点确保树的平衡。插入操作可能导致节点的分裂以容纳新的MBR。 范围查询 假设我们要查询城市中某个区域内的所有建筑物。RTree会从根节点开始逐层检查节点的MBR仅选择与查询区域相交的节点。这样就能有效剪枝减少搜索空间直到到达叶子节点。然后我们可以检查叶子节点中实际的建筑物数据找到符合查询条件的建筑物。 邻近查询 假设我们想找到某个特定建筑物附近的其他建筑物。我们首先找到包含该建筑物的叶子节点然后沿着树遍历到根节点选择可能与目标建筑物相交或接近的节点。这样我们可以有效地缩小搜索范围找到附近的建筑物。 删除建筑物 如果需要删除某个建筑物RTree会调整相关节点确保树的平衡。删除操作可能导致节点的合并或调整。
通过RTree我们能够以高效的方式组织、查询和更新城市地图上的建筑物数据提供了对多维空间数据的灵活支持。这是一个简化的案例。
二、业内方案选取
空间数据的存储和空间关系计算需要借助空间索引来实现常见的空间索引有三个方案本地内存比如基于RTree、空间数据库典型的如PostgreSQLPostGIS、分布式KV比如基于Geohash的RedisGEO。
方案特点优点缺点典型应用场景 本地内存索引 RTree 基于树状结构适用于本地内存中的数据组织和查询空间范围查询和邻近查询性能好不适用于大规模数据存储和分布式计算中小规模数据集的本地应用 空间数据库 PostgreSQLPostGIS 基于关系型数据库系统提供空间扩展PostGIS支持复杂的空间查询和分析数据持久化部署和维护相对复杂对小规模应用可能过重大规模、复杂的空间数据应用 分布式KV 基于Geohash的RedisGEO 基于键值存储系统使用Geohash编码高效的地理位置查询适用于分布式环境不适用于复杂的空间查询和分析实时位置服务分布式系统
选择合适的空间索引方案通常取决于应用的需求和规模。如果是小规模、单机的应用RTree等本地内存索引可能足够对于复杂查询和大规模数据集空间数据库是一个不错的选择而分布式KV适用于需要分布式处理和实时查询的场景。
三、分布式空间索引架构
只提供一个简单的架构思考实际中一定不能单独只用一种这样实现上很受限最好是结合着实际情况进行整合设计具体应用请根据实际内容进行设置处理。基于读写分离的CQRSCommand Query Responsibility Segregation架构其中查询端和管理端之间通过消息传输实现松耦合。 一PG数据变更通知服务
服务类型: 自研的PostgreSQL版本DTS服务。
职责: 负责订阅PG数据源的变更并进行变更通知。
功能: 提供实时的数据变更订阅功能使得其他系统能够获取PG数据库的最新状态。
二空间索引管理服务
职责: 管理空间索引包括多集群、多分片、多节点的管理。
功能:
增删集群、分片、节点。数据分发、一致性保障。处理围栏变更、主从切换、zk状态更新等操作。提供可视化管理页面和基于Prometheus的监控报警平台。
三空间索引SDK
职责: 客户端路由和空间索引节点服务发现。
功能:
利用Lettuce非阻塞响应式开源库处理客户端请求。提供空间索引节点的服务发现确保客户端能够准确路由请求。基于公司的ZK平台提供额外能力。
整体架构的特点包括CQRS的使用读写分离消息传输的松耦合以及对PG数据库和空间索引的有效管理和通知机制。这样的设计有助于系统的可维护性、伸缩性和性能优化。 参考文章
1.13 | 空间检索上如何用Geohash实现“查找附近的人”功能-极客时间
2.RTree算法及介绍_c# rtree-CSDN博客
3.开源方案距离计算问题https://github.com/tidwall/tile38/issues/222
4.RTree的距离计算算法Для просмотра статьи разгадайте капчу
