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

14

Muchas aplicaciones de bases de datos (¿quizás la mayoría?) hoy en día usan B-Trees y variaciones para almacenar datos, porque esta estructura de datos optimiza las operaciones de lectura, escritura y búsqueda en un disco duro (y estas operaciones a su vez desempeñan un papel importante en la eficiencia global de las bases de datos).

¿Deberían las unidades de estado sólido (SSD, por sus siglas en inglés) ubicarse por completo en los discos duros tradicionales (HDD), sin embargo, podríamos decir que los B-Trees y las variaciones se volverán obsoletos, dando espacio a las estructuras de datos que son más eficientes operando en la memoria de acceso directo? Si es así, ¿cuáles serán esas estructuras? (por ejemplo, tablas hash, árboles AVL)

    
pregunta Daniel Scocco 18.10.2011 - 17:01

2 respuestas

21

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

    
respondido por el Steve314 18.10.2011 - 17:29
3

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.

    
respondido por el Wilhelm Van Ende Boas 16.04.2013 - 21:48

Lea otras preguntas en las etiquetas