El documento PODC 2010 compartido por Dan Fox es, de hecho, la primera implementación sin bloqueo de los árboles de búsqueda binarios. Desde entonces ha habido mucho interés en esto.
Hay muchas formas de clasificar estas obras. Algunos son:
- 1. Garantía de progreso: basada en bloqueo (bloqueo) y sin bloqueo / sin espera (sin bloqueo)
- 2. Equilibrado (AVL / árbol rojo-negro) y desequilibrado
Árboles equilibrados
- Tsay y Li desarrollaron un marco en el que bloqueas una ventana de nodos. ver estructuras de árbol concurrentes sin bloqueo para sistemas multiprocesador
- Árbol AVL relajado (PPoPP’10)
- Árboles negros rojos rojos sin espera concurrentes (SSS’13)
Árboles desequilibrados
Las investigaciones recientes se centran más en la versión desequilibrada.
Según cómo se almacenan las claves, tenemos dos variantes de BST:
- ¿Qué puedo hacer con el doctorado en informática teórica además de la enseñanza?
- ¿Cómo puedo investigar sobre la depresión cuando mi especialidad es la visión por computadora y el aprendizaje automático?
- ¿Cuáles son los mejores algoritmos en informática para dominar inicialmente?
- ¿Qué es Google Brain?
- ¿Cuál es más eficiente de usar para la investigación: Matlab o Python? ¿Hay mejores opciones?
- Árbol externo: solo las hojas almacenan las claves
- Árbol interno: árbol de búsqueda binaria tradicional
Los árboles externos son relativamente más fáciles de desarrollar que los internos, ya que no existe una operación de eliminación compleja en la que un nodo interno sea reemplazado por su predecesor / sucesor.
Árboles externos sin bloqueo:
Árboles de búsqueda binaria sin bloqueo (PODC’10)
Árboles de búsqueda binaria rápidos sin bloqueo simultáneos (PPoPP’14)
Árboles internos sin bloqueo:
Un árbol de búsqueda binario interno sin bloqueo (SPAA’12)
Un árbol de búsqueda binaria interna sin bloqueo rápido (ICDCN’15)
Bloqueo de árboles internos:
CITRUS – Actualizaciones concurrentes con RCU (PODC’14)
Árboles de búsqueda binarios concurrentes prácticos mediante ordenamiento lógico (PPoPP’14)
CASTILLO: árbol de búsqueda binario interno rápido y concurrente utilizando bloqueo basado en bordes (PPoPP’15)
Para entender esto, sugeriría leer el primer documento (PODC’10) y luego saltar a leer Castle (PPoPP’15) ya que es el más simple de esta lista.
Para la implementación, creo que Castle (posiblemente el más rápido en términos de rendimiento) es el más fácil de implementar, seguido de Citrus (PODC’14).
Los dos árboles internos sin bloqueo son terriblemente difíciles de implementar.
PD: Toma mis reclamos sobre Castle con una pizca de sal, ya que soy coautor
