R-Tree 如何在简单检查点是否在矩形内优于 B-Tree

Question

对于查找最近邻居之类的事情，我可以理解 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

这是非常缓慢的。

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

Answer 1

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 个），并且没有坐标比其他坐标具有更高的权重。