¿Los árboles B y otras estructuras de datos quedarán obsoletos con el advenimiento de las unidades de estado sólido?

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é.

A priori, sí, la mayoría de los motores de base de datos tendrán que ser reescritos ya que B-Tree ya no será la estructura de datos más eficiente para almacenar datos, dado que la ubicación es importante en un disco duro donde el disco se mueve lentamente y los datos se obtienen en bloques, lo que significa que cualquier cambio en los datos debe:

1. Mueva la cabeza a la ubicación correcta en el disco (~ 10ms).
2. Espere a que el disco gire (a 10k rpm, eso significa 167 rotaciones por segundo, pero en promedio solo esperamos media rotación, por lo que ~ 3 ms).
3. Lee el bloque (~ 3ms).
4. Modificar en la memoria RAM. (~ 10ns)
5. Mueva la cabeza a la ubicación correcta en el disco nuevamente (~ 10ms nuevamente).
6. Espere a que el disco gire nuevamente (~ 3ms nuevamente).
7. Escriba el bloque (~ 3ms).

Eso es 10 + 3 + 3 + 10 + 3 + 3 = 34 ms

En promedio, hacer lo mismo en un SSD es solo 1 ms, independientemente de la posición en el disco.

Y como una tabla hash es mucho más rápida, podríamos pensar que una tabla hash sería un mejor reemplazo.

El único problema es que las tablas hash no conservan el orden y, por lo tanto, no es posible encontrar el siguiente y el anterior como Van Emde Boas.

Ver:

1. enlace
2. enlace

¿Por qué encontrar el siguiente y el anterior es importante? Imagine que todos los elementos son más grandes que x y más pequeños que z, necesita usar los índices con encontrar anterior y encontrar a continuación.

Bueno, el único problema es que no hemos encontrado tablas hash con habilidades para conservar el orden. Tal vez el tamaño del cubo en el árbol B sea importante, pero eso se resuelve con algoritmos ajenos a la memoria caché.

Por eso diría que este es un problema de final abierto.