Árbol concurrente eficiente

Question

Estoy buscando una forma eficiente de implementar una estructura de árbol simultánea. Si eso ayuda, suponga que tengo muchos más accesos de lectura que cambios en la estructura.

El árbol debe apoyar estas operaciones:

• Adición y eliminación de nodos
• Ordenar ramas cada vez que se inserta un nuevo nodo
• iterar sobre todos los nodos (sin ConcurrentModificationException)
• Busque un elemento por ruta

Answer 1

Tome un vistazo a: Concurrent-Trees el código de Google una manera de modificar las estructuras en forma de árbol sin bloquear.

El proyecto proporciona árboles Concurrent Radix y Suffix para Java. Admite lecturas y escrituras concurrentes, y las lecturas están libres de bloqueos. Funciona aplicando parches al árbol de forma atómica. Si bien estos tipos de árbol pueden no ser exactamente lo que usted desea, el enfoque que usa "parcheado" como se describe en TreeDesign es útil para cualquier tipo de estructura arborescente.

Los árboles están diseñados para casos de uso de lectura de concurrencia alta, donde (por ejemplo) un hilo de fondo podría estar insertando o eliminando entradas del árbol mientras que muchos hilos de primer plano continuarían atravesándolo sin impedimentos por las modificaciones.

Answer 2

Puede usar un bloqueo de lector-escritor en su estructura, i n una forma en que varios hilos pueden leer de forma simultánea pero solo un hilo a la vez puede modificarlo. Si algún hilo intenta modificar la estructura, no puede hacerlo hasta que todos los lectores hayan hecho sus lecturas. Si un hilo quiere leer, solo puede hacerlo si un escritor no está trabajando o está en proceso de hacer algunas modificaciones. Tal vez un vistazo a esto podría ayudar:

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

Answer 3

Idea básica con Bloqueo Lectura/Escritura

Para todas Escribir métodos usan siguiente lenguaje:

someWriteMethod(){ 
    writeLock.lock(); 
    // logic 
    writeLock.unlock(); 
} 

Para todos los métodos de lectura de uso similar código:

someReadMethod(){ 
    readLock.lock(); 
    // logic 
    readLock.unlock(); 
} 

• Si al menos un método realiza la escritura, nadie puede obtener el bloqueo de lectura o escritura.
• Si al menos un método realiza la lectura, cualquier número de hilo puede obtener un readlock.
• Si al menos un método realiza la lectura, nadie puede obtener el bloqueo de escritura.

Nota, si su código (reemplazar el comentario lógico anterior) puede arrojar una excepción, asegúrese de liberar bloqueos antes de salir del método en la sección final.

Answer 4

La estructura de Java que está más cerca de lo que puede necesitar es ConcurrentSkipListSet (o tal vez ConcurrentSkipListMap).

---

Si necesita un enfoque más personalizado, puede implementar una estructura de árbol personalizada si tiene un bloqueo de lectura y escritura jerárquico. Aquí es un answerto una pregunta similar acerca de cómo implementar un entrante de bloqueo de lectura-escritura: https://stackoverflow.com/a/6154873/272388