¿Por qué los nodos de índice o una propiedad indexada serían mejores en una base de datos de gráfico?

Question

Acabo de entrar en las bases de datos de gráficos, y parece que me encuentro con un problema al decidir entre usar un "nodo de índice" o una "propiedad indexada" para rastrear cosas como "tipo de nodo". Como no tengo experiencia real hasta ahora, no tengo información para basarme en la decisión y ambos enfoques parecen ser igualmente válidos.

Entonces, la pregunta es: ¿Cuáles son las ventajas y desventajas entre dos enfoques, y cómo la escala (es decir, el número de nodos) afecta la decisión?

Para un escenario de ejemplo, supongamos que hay dos tipos de "cosas": User y Product, y los bordes entre los nodos de usuario y los nodos de producto no importan tanto, pero lo que nos interesa es si queremos las propiedades type: User y type: Product en cada nodo, o si queremos que cada nodo tenga un borde apuntando hacia atrás en un nodo User y un nodo Product, respectivamente.

¿Qué enfoque es mejor bajo qué circunstancias?

_{Nota: Estoy viendo a Neo4j y a Titan en particular, pero creo que esto tenderá a aplicarse en términos más generales también.}

Answer 1

en primer lugar, hay que preguntarse: ¿el tipo de un vértice/nodo necesidad de ser indexados? Es decir ¿necesita recuperar vértices/nodos por su tipo, digamos, recuperar todos los vértices de 'usuario' del gráfico o necesita responder consultas que comienzan recuperando todos los vértices de un tipo dado y luego filtrar/procesarlos más?

Si la respuesta a esta pregunta es sí, le sugiero que almacene el tipo como una propiedad de cadena que está indexada. O bien, si está desarrollando en un lenguaje basado en jvm, puede definir un tipo de enumeración y usarlo como el tipo de propiedad para más seguridad de tipo y comprobación automática de errores. Titan admite clases/enumeraciones arbitrarias definidas por el usuario como tipos de propiedad y las comprimirá para una huella de memoria baja.

Sin embargo, la desventaja de este enfoque es que no se escalará porque está creando un índice de baja selectividad. Lo que eso significa es que es probable que haya muchos vértices de tipo 'usuario' o 'producto' y todos ellos deben estar asociados con la entrada de índice para 'usuario' o 'producto' respectivamente. Esto hace que mantener y consultar este índice sea muy costoso y difícil de escalar (imagine que Facebook tenía un índice de 'tipo': la entrada de 'foto' tendría miles de millones de vértices). Si todavía no te preocupa el escalado, entonces esto puede funcionar.

Si la respuesta a la pregunta es no, entonces sugiero modelar tipos como vértices/nodos en el gráfico. Es decir. tiene un vértice de "usuario" y un vértice de "producto" y un borde etiquetado como "tipo" de cada usuario al vértice de "usuario", etc.

La ventaja de este enfoque es que utiliza el gráfico para modelar sus datos en lugar de tener valores de cadena fuera de su base de datos representan información de tipo crucial. A medida que crea su aplicación, la base de datos de gráficos se convertirá en su componente central y durará mucho tiempo. A medida que los lenguajes de programación y los desarrolladores van y vienen, no quiere que el modelado de datos y el tipo de información vayan con ellos y se enfrente a la pregunta: "¿Qué significa SPECIAL_USER?" Más bien, tenga un vértice SPECIAL_USER y añádale información de procedencia, es decir, quién creó este tipo, qué representa y una breve descripción: todo en la base de datos.

Un problema con este enfoque es que los vértices de 'usuario' y 'producto' tendrán muchos bordes incidentes en ellos a medida que la aplicación escala. En otras palabras, está creando supernodos que crean problemas de escala. Es por eso que Titan introdujo el concepto de un borde unidireccional. Un borde unidireccional es como un enlace en la web: el vértice inicial apunta a otro vértice, pero ese vértice ignora el borde. Como no desea atravesar el vértice del "usuario" para todos los vértices de usuario, no está perdiendo nada, sino que aumenta la escalabilidad y el rendimiento.

Answer 2

¿Qué tipo de consulta desea realizar? En Neo4j, se crearía un índice User y una Product o incluso combinarlos en uno, y luego ser capaz de hacer cosas como

start bob = node:User(name='Bob') match .... 

e incluso realizar búsquedas textuales. Para verificar fácilmente si un nodo es un Usuario o Producto, podría tener la propiedad aún en los nodos, solo para un cruce conveniente y rápido. Si no está atravesando desde Usuario/Producto hasta los nodos de instancia (realiza las búsquedas de índice para eso), incluso puede hacer el control teniendo una relación PRODUCT o USER con los nodos de tipo (super), que le dan un check-in -traversal como

start s = node:User(name='Bob') match s-[r]-(product)-[typeRel:PRODUCT]->() return product 

HTH

Answer 3

Aquí se ha perdido una razón muy importante para la indexación. Supongamos que tiene un gráfico complejo con muchas propiedades diferentes, y muchos tipos de nodos diferentes, y desea hacer coincidir un patrón con una "persona" que tiene un montón de propiedades.

Sin índices, no tiene más opción que recorrer el gráfico, un gráfico en el que tal vez solo el 0,01% de los nodos son de tipo persona. Y los cruces pueden no llegar a las regiones no conectadas del gráfico.

En cambio, si tengo una persona indexada, simplemente repito a través de cada persona, y busco localmente alrededor de cada persona para ver si su patrón coincide.

Debería poder ver al instante que el primero de estos enfoques escala con el tamaño total del gráfico, pero el segundo solo escala con el número total de personas en el gráfico.

Moral: si prevé un caso de uso donde habrá muchas búsquedas del gráfico con un tipo particular de nodo como nodo vinculado en su patrón (por ejemplo, aquí muchas búsquedas de "personas con patrón X"), entonces debe indexar estos nodos para un mejor rendimiento de búsqueda.

Si va a buscar cosas como "todos los nodos dentro de los dos enlaces de la persona Peter", indexar a la persona por su nombre sería crítico y permitiría un rendimiento de tiempo constante independientemente del tamaño del gráfico, ya que esencialmente está buscando la ubicación de Peter en una tabla hash.