Início / dba / Perguntas / 19640
Accepted
user4951
Asked: 2012-06-22 02:44:14 +0800 CST

Como o R-Tree supera o B-Tree para verificação simples se um ponto está dentro de um retângulo

  • 772

Para coisas como encontrar vizinhos mais próximos, posso entender que R=Tree pode superar B-Tree. O R-Tree pode lançar pontos mais obviamente falsos.

No entanto, para verificação simples de um ponto em um retângulo, é efetivamente

min

Se x e y forem indexados pela árvore b, eles também podem gerar muitos pontos falsos.

Então eu fiz um experimento com índice espacial

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

Isso é muito rápido. 0,24 segundos

E então eu faço

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

Isso é muito lento.

Eu quero saber porque. Não faz sentido.

mysql spatial

1 respostas

  1. Best Answer

    A estrutura da árvore R funciona de forma que dois pontos próximos estejam "mais próximos" no índice da árvore R - porque ambas as coordenadas e ambas com o mesmo peso são usadas para decidir onde (no índice) um novo ponto deve ser colocado.

    Portanto, é fácil identificar pontos que estão "próximos" de um ponto fixo - ou seja, pontos que possuem ambas as coordenadas próximas às coordenadas do ponto fixo.

    Os índices de árvore B, por outro lado, funcionam de maneira diferente. Mesmo se você tiver um índice composto, digamos (Latitude, Longitude), onde ambas as coordenadas estão incluídas no índice, elas não têm o mesmo peso. Em outras palavras, dois pontos com valores diferentes Latitudee iguais Longitudeestarão muito distantes (na estrutura do índice). Muito mais separados do que dois pontos iguais Latitudee diferentes Longitude.

    Portanto, pesquisar pontos próximos (com o (Lat, Long)índice acima) pode encontrar pontos próximos rapidamente com exatamente o mesmo Latitude. Mas para todos os outros pontos, não será muito eficiente.

    Por exemplo, considere que você está procurando lugares próximos a uma vila na África - uma vila que tem o mesmo que LatitudeLondres. Sua consulta gastaria muito tempo calculando as distâncias entre sua vila e todos os (milhões) pontos no Reino Unido que têm a mesma (ou quase a mesma) latitude com ela. E então rejeite esses pontos porque eles estão muito distantes.

    Você pode pensar então que dois índices de árvore B, um on (Latitude)e outro on (Longitude), seriam bons para tais consultas. Afinal, por que os dois índices não deveriam ser usados ​​em uma consulta que possui:

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

    Acho que o DBMS não pode usar dois índices (árvore B) como esse em uma consulta (o MySQL não pode AFAIK). Mesmo que pudesse, não seria muito bom, em termos de desempenho, pois ambas as condições podem não restringir muito a pesquisa. Portanto, após essas duas varreduras de índice, um milhão de linhas encontradas que correspondam a uma condição teriam que ser mescladas com um milhão de linhas da outra. E essa mesclagem provavelmente também exigirá classificação - o que prejudicará o desempenho se os subresultados forem grandes.

    Em geral, qualquer consulta que tenha mais de uma condição de intervalo na mesma tabela é difícil de ser otimizada por índices de árvore B. (para outros SGBDs que possuem outros tipos de índices, como Hash ou Bitmap, não posso falar).

    É por isso que R-trees e outros índices que funcionam bem em buscas espaciais foram inventados em primeiro lugar. Eles meio que "intercalam" ambas as coordenadas (ou todas as 3 ou 4 em índices dimensionais superiores) na estrutura do índice e nenhuma coordenada tem peso maior que as outras.

    • 9

relate perguntas