Los B-Trees se utilizan con mayor frecuencia para los índices de base de datos en el disco duro, pero tienen ventajas incluso como una estructura de datos en memoria, dada la jerarquía de memoria moderna con múltiples capas de caché y con memoria virtual. Incluso si la memoria virtual está en un SSD, eso no cambiará.
Utilizo una biblioteca de árbol de múltiples vías de estilo B + en memoria que escribí bastante en C ++. puede tener ventajas de rendimiento, la razón por la que se escribió originalmente fue para tratar de utilizar mejor la memoria caché, pero debo admitir que a menudo no funciona de esa manera. El problema es la compensación, lo que significa que los elementos deben moverse dentro de los nodos en las inserciones y eliminaciones, lo que no ocurre con los árboles binarios. Además, algunos de los hacks de codificación de bajo nivel que utilicé para optimizarlo, bueno, probablemente confundan y derrotan al optimizador, dijo la verdad.
De todos modos, incluso si sus bases de datos están almacenadas en un SSD, es todavía un dispositivo de almacenamiento orientado a bloques, y todavía hay una ventaja al usar B-Trees y otros árboles de múltiples vías.
PERO hace unos diez años, se inventaron los algoritmos y las estructuras de datos que ignoran la memoria caché. Estos son ajenos al tamaño y estructura de los cachés, etc. - hacen (asintóticamente) el mejor uso posible de cualquier jerarquía de memoria. Los B-Trees deben "ajustarse" a una jerarquía de memoria particular para hacer el mejor uso (aunque funcionan bastante bien para una amplia variedad de variaciones).
Las estructuras de datos ajenos al caché no se ven a menudo en la naturaleza, si es que lo hacen, pero es hora de que los árboles binarios en memoria pasen a ser obsoletos. Y también pueden valer la pena para los discos duros y SSD, ya que no les importa el tamaño de la página de caché de disco duro o de tamaño de clúster.
El diseño de Van Emde Boas es muy importante en las estructuras de datos que no tienen memoria caché.
El curso de algoritmos OpenCourseware del MIT incluye cierta cobertura de estructuras de datos ajenas a la memoria caché.