Postgresql:实现层次树

Question

我一直在与1000多个标记(应该放在谷歌地图上)的标记聚类问题作斗争。我不太喜欢渲染带有所有标记的大型JSON结构，也不喜欢使用PostGIS进行一些复杂的服务器"地理"计算。

我想出的解决方案是将世界地图划分成某种层次空间树，让我们说四边形树，其中我的db中的每个点将被分配与该树中的"坐标"。这些坐标是具有on position_x index_of_tile in tier_x的字符串，例如。"031232320012"。字符串的长度取决于将为前端地图启用的缩放级别的数量。基本上，如果用户移动或缩放地图，我将使用当前缩放级别和视图端口坐标作为参数启动Ajax GET请求。然后在后台，我计划建立一个字符串，应该指向"在给定的缩放级别的视口"，例如:'02113'，我想在树坐标列中找到所有有这个前缀('02113')的点。

编辑:我还需要快速GROUP BY，例如SELECT count(*) from points GROUP BY left(coordinates, 5);

我的问题是如何尽可能快地执行这些操作?我的数据库是PostgreSQL

Answer 1

然后在后端，我计划建立一个字符串，应该指向"在给定的缩放级别的视口"，例如:'02113'，我想在树坐标列中找到所有具有这个前缀('02113')的点。

一个普通的索引应该在任何现代dbms上都表现良好，只要你在索引列中查看字符串最左边的五个(或六个或七个)字符。

SELECT ...
...
WHERE column_name LIKE '02113%';

在PostgreSQL中，你也可以在表达式上建立索引。因此，您可以在前五个字符上创建索引。

CREATE INDEX your_index_name ON your_table (left(column_name, 5));

如果有三个或四个这样的索引，我希望PostgreSQL的查询优化器能够选择正确的索引。(一个5个字符，一个6个字符等)

---

我建立了一个表，我用一百万行随机数据填充它。

在下面的查询中，PostgreSQL的查询优化器确实选择了正确的索引。

explain analyze
select s
from coords
where left(s, 5) ='12345';

返回时间0.1 ms。

我还使用GROUP BY进行了测试。再一次，PostgreSQL的查询优化器选择了正确的索引。

"GroupAggregate  (cost=0.00..62783.15 rows=899423 width=8) (actual time=91.300..3096.788 rows=90 loops=1)"
"  ->  Index Scan using coords_left_idx1 on coords  (cost=0.00..46540.36 rows=1000000 width=8) (actual time=0.051..2915.265 rows=1000000 loops=1)"
"Total runtime: 3096.914 ms"

像left(name, 2)这样的表达式在GROUP BY子句中会要求PostgreSQL访问索引中的每一行，如果不是表中的每一行。这就是为什么我的查询花费了3096毫秒;它必须触及索引中的一百万行。但是您可以从EXPLAIN计划中看到它使用了索引。

通常，我希望地理应用程序对PostGIS表使用边界框来减少您访问的行数。如果您的四叉树实现不能做得更好，我将坚持使用PostGIS足够长的时间，以成为它的专家。(除非你花了一些时间，否则你无法确定它是否能胜任这项工作。)