¿Qué modelo jerárquico debo usar? Adyacencia, anidado o enumerado?

Question

Tengo una tabla que contiene una ubicación de todas las ubicaciones geográficas del mundo y sus relaciones.

Aquí hay un ejemplo que muestra la jerarquía. Verá que los datos se almacenan realmente ya que los tres

• Ruta Enumerados
• lista de adyacencia
• conjuntos anidados

Los datos, obviamente, nunca cambia tampoco. A continuación se muestra un ejemplo de los antepasados ​​directos de la ubicación de Brighton en Inglaterra que tiene un WOEID de 13911.

Tabla: geoplanet_places (tiene 5.6million filas) Ampliación de imagen: http://tinyurl.com/68q4ndx

que luego tener otra tabla llamada entities. Esta tabla almacena mis artículos que me gustaría asignar a una ubicación geográfica. Guardo algo de información básica, pero lo más importante es que almaceno el woeid que es una clave foránea de geoplanet_places.

Eventualmente la tabla entities contendrá varios miles de entidades. Y me gustaría una forma de poder devolver un árbol completo de todos los nodos que contienen entidades.

Planeo crear algo para facilitar el filtrado y la búsqueda de entidades en función de su ubicación geográfica y ser capaz de descubrir cuántas entidades se pueden encontrar en ese nodo en particular.

Así que si sólo tengo una entidad en mi mesa entities, podría tener algo como esto

`Tierra (1)

Reino Unido (1)

Inglaterra (1)

East Sussex (1)

Brighton City (1)

Brighton (1) `

Lets luego decir que no tengo otra entidad que se encuentra en Devon, a continuación, se mostraría algo como:

Tierra (2)

Estados Kingom (2)

Inglaterra (2)

Devon (1)

East Sussex (1) ...etc.

No es necesario publicar el (conteos) que indicará cuántas entidades están "adentro" de cada ubicación geográfica. Puedo vivir generando mi objeto cada hora y almacenarlo en la memoria caché.

El objetivo, es ser capaz de crear una interfaz que podría comenzar mostrando sólo los países que tienen las entidades ..

Así como

Argentina (1021), Chile (291), ..., United States (32,103), United Kingdom (12,338)

Luego, el usuario hará clic en una ubicación, como United Kindom, y luego recibirá todos los nodos secundarios inmediatos que son descendientes de Reino Unido Y tienen una entidad en ellos.

Si hay 32 condados en United Kindgdom, pero solo 23 de ellos eventualmente cuando desgloses tienen entidades almacenadas en ellos, entonces no quiero mostrar los otros 9. Solo son ubicaciones.

Este sitio acertadamente demuestra la funcionalidad que se desea lograr: http://www.homeaway.com/vacation-rentals/europe/r5

Como recomiendan que manejo una estructura de datos?

Cosas que estoy usando.

• PHP MySQL
• Solr

I Plan de tener los niveles de detalle efectuarse tan pronto como sea posible. Quiero crear una interfaz AJAX que será inmejorable para buscar.

También me gustaría saber en qué columnas recomendaría indexar.

Answer 1

lo general, hay tres tipos de consultas en las jerarquías que causan problemas:

1. Volver todos los antepasados ​​
2. Volver a todos los descendientes
3. Volver a todos los niños (descendientes inmediatos).

He aquí una pequeña tabla que muestra el rendimiento de diferentes métodos de MySQL:

     Ancestors Descendants Children  Maintainability InnoDB 
Adjacency list   Good  Decent  Excellent  Easy   Yes 
Nested sets (classic) Poor  Excellent Poor/Excellent Very hard  Yes 
Nested sets (spatial) Excellent Very good Poor/Excellent Very hard  No 
Materialized path  Excellent Very good Poor/Excellent Hard   Yes 

En children, poor/excellent significa que la respuesta depende de si usted está mezclando el método con la lista de adyacencia, i. mi. almacenando el parentID en cada registro.

Para su tarea, necesita los tres consultas:

1. Todos los antepasados ​​para mostrar la cosa Tierra/UK/Devon
2. Todos los niños para mostrar "destinos en Europa" (los artículos)
3. Todos los descendientes mostrarán "Destinos en Europa" (los recuentos)

Iré por caminos materializados, ya que este tipo de jerarquía rara vez cambia (solo en caso de guerra, revuelta, etc.).

crear una columna varchar llamados path, índice y llenarlo con el valor de la siguiente manera:

1:234:6345:45454: 

donde los números son claves primarias de los padres adecuados, en el orden correcto (1 para Europa, 234 de Reino Unido, etc.)

También necesitará una tabla llamada levels para mantener los números del 1 en 20 (o el nivel máximo de anidación que desee).

Para seleccionar todos los antepasados:

SELECT pa.* 
FROM  places p 
JOIN  levels l 
ON  SUBSTRING_INDEX(p.path, ':', l.level) <> p.path 
JOIN  places pa 
ON  pa.path = CONCAT(SUBSTRING_INDEX(p.path, ':', l.level), ':') 
WHERE p.id = @id_of_place_in_devon 

Para seleccionar todos los niños y los recuentos de lugares dentro de ellos:

SELECT pc.*, COUNT(pp.id) 
FROM places p 
JOIN places pc 
ON  pc.parentId = p.id 
JOIN places pp 
ON  pp.path BETWEEN pc.path AND CONCAT(pc.path, ':') 
     AND pp.id NOT IN 
     (
     SELECT parentId 
     FROM places 
     ) 
WHERE p.id = @id_of_europe 
GROUP BY 
     pc.id 

Answer 2

Esta es la consulta que se me ocurrió. Es una adaptación de lo que sugieres Quassnoi.

SELECT pa.*, level, SUBSTRING_INDEX(p.ancestry, '/', l.level), p.* 
FROM  geoplanet_places p 
JOIN  levels l 
ON  SUBSTRING_INDEX(p.ancestry, '/', l.level) <> p.ancestry 
JOIN  geoplanet_places pa 
ON  pa.woeid = SUBSTRING_INDEX(SUBSTRING_INDEX(p.ancestry, '/', l.level),'/',-1) 
WHERE p.woeid = "13911" 

Esto devuelve a todos los padres de Brighton.

El problema con su consulta fue que no se devolvió la ruta a los padres, sino a cualquier nodo que compartió la misma ruta.

SELECT  pa.*, GROUP_CONCAT(pa.name ORDER BY pa.lft asc),group_concat(pa.lft ), pa.ancestry 
              FROM  geo_places p 
              JOIN  levels l 
              ON  SUBSTRING_INDEX(CONCAT(p.ancestry, p.woeid,'/'), '/', l.level) <> p.ancestry 
              JOIN  geo_places pa 
              ON  pa.woeid = SUBSTRING_INDEX(SUBSTRING_INDEX(CONCAT(p.ancestry, p.woeid,'/'), '/', l.level),'/',-1) 
              WHERE p.woeid IN ("12767488","12832668","12844837","131390","131391","12846428","24534461") 
              GROUP BY p.woeid