Árbol negro rojo versus b árbol

Question

Tengo un proyecto en el que tengo que lograr una búsqueda rápida, insertar y eliminar operaciones en datos que van desde megabytes hasta terabytes. Había estado estudiando estructuras de datos en los últimos tiempos y analizándolas. Siendo específico, quiero presentar 3 casos y hacer preguntas al respecto:

1. Los datos son mucho más de lo que la memoria puede manejar (rangos de muestra en 10-15 terabytes) de una vez. En este caso, almacenaría la estructura de datos en un disco.

2. Los datos son relativamente menos en comparación con la memoria del sistema y, por lo tanto, se pueden almacenar y operar en la memoria misma para la velocidad.

3. Los datos son más que la memoria libre y suponen que es menor que el tamaño de una posible porción contigua de datos en el archivo de paginación. Por lo tanto, almaceno la estructura de datos en un archivo en el disco y hago una asignación de memoria del archivo.

Las conclusiones que he sacado son:

Para el caso 1, debería usar un árbol B para un acceso más rápido, ya que guarda en el retraso producido por la rotación del disco

Para el caso 2, debería usar un árbol negro rojo para un acceso más rápido ya que los datos están en la memoria y no. de los elementos debían escanearse en un peor de los casos sería menor que uno que tengo que hacer si uso árboles B

Para el caso 3, tengo dudas en este caso, el archivo de página está en el disco usa E/S nativo de SO para operar en archivos, entonces, ¿debería ser una mejor opción o un árbol negro rojo?

Quiero saber dónde salen bien las tres conclusiones anteriores y dónde sale mal y cómo puedo mejorar el rendimiento en los tres casos separados.

Estoy usando el lenguaje C ++, con un árbol negro rojo y un árbol B, ambos que he diseñado desde cero. Estoy usando la biblioteca Boost para la asignación de archivos.

ACTUALIZACIÓN 1 :: estaba leyendo a través de este Publicado en Stackoverflow. Obtuve algunas ideas muy buenas, lo que me hace sentir que el tipo de comparaciones que he hecho en los casos puede ser defectuoso. Se publicó un enlace en el más votado por la respuesta http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html