¿Cuál es la forma más eficiente de almacenar y consultar árboles?

Question

Necesito analizar 1 TB + de registros de acceso web y, en particular, necesito analizar las estadísticas relacionadas con las URL solicitadas y los subconjuntos de las URL (ramas secundarias). Si es posible, quiero que las consultas sean rápidas en pequeños subconjuntos de datos (por ejemplo, 10 millones de solicitudes). se solicitó

Por ejemplo, dado un registro de acceso con las siguientes URL:

/ocp/about_us.html 
/ocp/security/ed-209/patches/urgent.html 
/ocp/security/rc/ 
/ocp/food/ 
/weyland-yutani/products/ 

quiero hacer consultas tales como:

• contar el número de solicitudes de todo 'abajo'/ocp.
• Igual que el anterior, pero solo cuenta las solicitudes de nodos secundarios en/ocp/security
• Devuelve las 5 URL principales más solicitadas.
• Igual que el anterior, excepto el grupo por una profundidad arbitraria,

por ejemplo Para la última consulta anterior, la profundidad de 2 para los datos volvería:

2: /ocp/security/ 
1: /ocp/ 
1: /ocp/food/ 
1: /weyland-yutani/products/ 

creo que el enfoque ideal sería probablemente utilizar una columna DB y tokenize las direcciones URL de tal manera que hay una columna para cada elemento de la URL . Sin embargo, me gustaría encontrar una forma de hacer esto con las aplicaciones de código abierto si es posible. HBase es una posibilidad, pero el rendimiento de la consulta parece demasiado lento para ser útil para las consultas en tiempo real (también, realmente no quiero estar en el negocio de volver a implementar SQL)

Soy consciente de que hay comerciales aplicaciones para hacer este tipo de análisis, pero por diversas razones quiero implementar esto por mi cuenta.

Answer 1

Antes de invertir demasiado tiempo en el diseño de una estructura de datos jerárquica en la parte superior de una base de datos relacional, considere la lectura "Naive Trees" section (starting at slide 48) en la excelente presentación SQL anti-patrones Strike Back por Bill Karwin. Bill se describen los siguientes métodos para el desarrollo de una jerarquía:

1. Path enumeración (diapositiva 55)
2. conjuntos anidados (diapositiva 58)
3. mesa de cierre (deslice 68)

Answer 2

Es posible que desee consultar el tipo de datos HIERARCHYID en SQL Server 2008 o su equivalente en Oracle.

Answer 3

árboles no son generalmente muy eficiente en bases de datos. Quiero decir: si diseñas el árbol para que sea verdaderamente recursivo, con elementos que apuntan a sus padres, obtendrás muchas consultas para encontrar todos los nodos secundarios.

Pero puede optimizar el árbol, según sus necesidades.

Poner cualquier parte de la url en una columna no es una mala idea. Debe limitar la profundidad a una cierta cantidad de subnodos. Podría tener índices en cualquier columna, lo que lo hace muy rápido.

consultas sobre una estructura de este tipo son muy simples:

Select count(*) From Hits where node1 = 'ocp' AND node2 = 'security'; 

Hacer una estadística de acceso:

SELECT node1, node2, count(*) as "number of hits" 
FROM hits 
GROUP BY node1, node2 
ORDER BY count(*) DESC 

obtendrá

node1   node2  number of hits 
'ocp'      23345 
'ocp'   'security' 1020 
'ocp'   'food'  234 
'weyland-yutani' 'products'  22 

También podría almacenar la URL como es y filtra usando regex. Esto es más flexible, pero más lento, porque no tiene índices. Solo necesita limitar la longitud total de la url, no la cantidad de subnodos.

Creo que podría hacer esto con cualquier base de datos lo suficientemente buena como para almacenar una gran cantidad de datos. Por ejemplo MySql.

Answer 4

El libro, The Art of Sql, de Stephane Faroult tiene un excelente capítulo (7 - Tratar con datos jerárquicos) que explica y compara 3 métodos para almacenar y consultar árboles utilizando bases de datos relacionales.

Si está realizando una implementación seria de fortaleza industrial, estudiar el capítulo será un tiempo bien empleado.

Answer 5

Creo que la manera más eficiente de almacenar este tipo de datos es en una tabla de explosión de partes (o jerarquía).

Una tabla de explosión de partes consta de tres columnas: una identidad, un elemento principal y una descripción. Para los datos del ejemplo, la tabla podría ser algo como esto:

Identity Parent Description 
0  Null ocp 
1  0  about_us.html 
2  0  security 
3  2  ed-209 
4  3  patches 
5  4  urgent.html 
6  2  rc 
7  0  food 
8  Null weyland-yutani 
9  8  products 

Como la tabla de URL (explosión) está siendo poblada, rellenar una tabla que registra la hoja de cada URL. De los datos de ejemplo:

Leaf ID 
------- 
1 
5 
6 
7 
9 

Creo que puede responder todas sus preguntas comenzando con estas dos tablas.