主页 / dba / 问题 / 19640
Accepted
user4951
Asked: 2012-06-22 02:44:14 +0800 CST

R-Tree 如何胜过 B-Tree 来简单检查一个点是否在矩形内

  • 772

对于查找最近的邻居之类的事情，我可以理解 R=Tree 可以胜过 B-Tree。R-Tree可以踢出更明显的假点。

然而，对于矩形中的一个点的简单检查，它是有效的

分钟

如果 x 和 y 被 b 树索引，它们也可以踢出很多假点。

所以我用空间索引做了一个实验

SELECT DISTINCT
  TB.ID,
  TB.Latitude,
  TB.Longitude,
  111151.29341326*SQRT(pow(-6.185-TB.Latitude,2)+pow(106.773-TB.Longitude,2)*0.98839228980165) AS Distance
FROM
  `tablebusiness` AS TB
   join tableauxiliary as TA on TA.BusinessID=TB.ID
WHERE
MBRContains(
   GeomFromText ('MULTIPOINT(-6.2317830813328 106.72621691867,-6.1382169186672  106.81978308133)'),
   TA.Latlong
   )
   AND 
MATCH (FullTextSearch) AGAINST ('kucing*' IN BOOLEAN MODE)
ORDER BY
  Distance
LIMIT
  0, 20

这非常快。.24 秒

然后我做

SELECT DISTINCT
  TB.ID,
  TB.Latitude,
  TB.Longitude,
  111151.29341326*SQRT(pow(-6.185-TB.Latitude,2)+pow(106.773-TB.Longitude,2)*0.98839228980165) AS Distance
FROM
  `tablebusiness` AS TB
   join tableauxiliary as TA
WHERE
  -6.2317830813328 < TB.Latitude
AND
  TB.Latitude < -6.1382169186672
AND
  106.72621691867 < TB.Longitude
AND
  TB.Longitude <106.81978308133
AND 
   MATCH (TA.FullTextSearch) AGAINST ('kucing*' IN BOOLEAN MODE)
ORDER BY
  Distance
LIMIT
  0, 20

这很慢。

我想知道为什么。这没有意义。

mysql spatial

1 个回答

  1. Best Answer

    R-tree 结构的工作方式是两个附近的点在 R-tree 索引中“更近”——因为两个坐标和具有相同权重的两个点都用于决定（在索引中）放置新点的位置。

    因此，很容易识别“靠近”固定点的点 - 即两个坐标都接近固定点坐标的点。

    另一方面，B 树索引的工作方式不同。即使你有一个复合索引，比如(Latitude, Longitude)，其中两个坐标都包含在索引中，它们的权重也不相同。换句话说，不同Latitude和相同的两个点将Longitude相距很远（在索引结构中）。Latitude比具有相同和不同的两点相距更多Longitude。

    因此，搜索附近点（具有上述(Lat, Long)索引）可能会找到具有完全相同的快速附近点Latitude。但是对于所有其他点，它不会非常有效。

    例如，假设您正在寻找非洲村庄附近的地方 - 一个Latitude与伦敦相同的村庄。您的查询将花费大量时间来计算您的村庄与英国具有相同（或几乎相同）纬度的所有（数百万）个点之间的距离。然后拒绝这些点，因为它们相距太远。

    您可能会认为两个 B 树索引，一个 on(Latitude)和一个 on(Longitude)就可以满足此类查询。毕竟，为什么不应该在具有以下内容的查询中同时使用这两个索引：

    WHERE Latitude  BETWEEN @LatStart  AND @LatEnd 
  AND Longitude BETWEEN @LongStart AND @LongEnd

    我认为 DBMS 不能像在查询中那样使用两个（B 树）索引（MySQL 不能 AFAIK）。即使可以，从性能方面来看也不是很好，因为这两种情况都不会缩小搜索范围。因此，在这两个索引扫描之后，发现匹配一个条件的一百万行必须与另一个条件的一百万行合并。而且这种合并可能还需要排序——如果子结果很大，这会降低性能。

    通常，任何在同一张表上具有多个范围条件的查询都很难通过 B 树索引进行优化。（对于具有其他类型索引的其他 DBMS，如 Hash 或 Bitmap，我不能谈论）。

    这就是为什么 R 树和其他在空间搜索中表现良好的索引首先被发明的原因。它们在索引结构中有点“交错”两个坐标（或更高维度索引中的所有 3 或 4），并且没有坐标比其他坐标具有更高的权重。

    • 9

相关问题