Estoy leyendo en B Trees y parece que logran las operaciones de conjunto dinámico en el tiempo O (lg n). El árbol negro rojo (TreeMap en java) también logra la misma operación en el mismo marco de tiempo de forma asintótica. Así que me gustaría saber qué hace que los árboles B sean más útiles para la base de datos y los sistemas de archivos¿Por qué necesitamos una estructura de datos separada como B-Tree para la base de datos y el sistema de archivos?
La razón principal de la existencia de B-Trees es utilizar mejor el comportamiento de los dispositivos que leen y escriben grandes cantidades de datos. Dos propiedades son importantes para que el árbol B mejor que los árboles binarios cuando los datos tiene que ser almacenado en el disco:
Por lo tanto, podemos usar los pros del segundo hecho, al tiempo que minimizamos el número de accesos al disco.
Entonces, en lugar de simplemente almacenar un solo número en cada nodo que nos dice si debemos continuar hacia la izquierda o hacia la derecha, podemos crear un índice más grande que nos diga si debemos continuar al primer 1/100 , al segundo o al 99-th (imagine libros en una biblioteca ordenados por su primera letra, luego por el segundo, y así sucesivamente). Siempre que todos estos datos se ajusten a un solo sector, se cargarán de todos modos, por lo que también podríamos usarlo por completo.
Esto da como resultado aproximadamente el registro b N búsquedas, donde N es el número de registros. Este número, aunque asintóticamente lo mismo que log N, en realidad es unas pocas veces más pequeño con suficiente N yb, y como estamos hablando de almacenar datos en el disco para su uso en bases de datos, etc., la cantidad de datos suele ser lo suficientemente grande como para justificar esto.
El resto de la decisión de diseño se realiza principalmente para que este funcione de manera eficiente, ya que modificar un árbol N-ary es más complicado que uno binario.
Gracias! Al menos, he leído unos 50 artículos sobre el uso del árbol B, pero nadie mencionó el segundo acceso de disco que B tree convierte en un profesional. – ernesto
Los árboles RB son árboles de búsqueda binarios. Los árboles B pueden tener más de dos nodos secundarios. De hecho, la cantidad de nodos secundarios es variable.
Por lo tanto, puede variar el número de nodos secundarios de forma que el tamaño de un nodo sea siempre un múltiplo del tamaño del bloque del sistema de archivos. Esto reduce el desperdicio al leer: no puede leer menos de un bloque de todos modos, siempre tiene que leer el bloque completo, por lo que puede llenarlo con datos útiles. Aumentar el número de nodos secundarios también reducirá la profundidad del árbol, disminuyendo así la cantidad promedio de "saltos" (es decir, lecturas de disco), lo que de nuevo aumenta el rendimiento.
Recuerde: árboles B se utilizan generalmente para almacenar estructuras de datos que son órdenes de magnitud más grande que la memoria, mientras que los árboles RB se utilizan normalmente para almacenar estructuras de datos que son órdenes de magnitud más pequeña que la memoria. De hecho, los árboles B están diseñados específicamente como una estructura de datos en disco en lugar de una estructura de datos en memoria.
Ésta es la frase clave de la (el énfasis es mío) Wikipedia article:
el árbol B se optimizado para los sistemas que leen y escriben grandes bloques de datos
Nosotros necesitan diferentes algoritmos porque la velocidad de acceso en la memoria es mucho más rápida que en el disco. Un árbol rojo/negro hace que muchos accesos a la memoria, por lo que funciona bien con la velocidad de acceso rápido de la memoria. Un b-tree realiza menos accesos de mayor tamaño porque el disco al que se accede es lento.
Wikipedia tiene una muy buena descripción de los problemas que resuelve B-Tree: http://en.wikipedia.org/wiki/B-tree#The_database_problem. –
@IvanVergiliev ¿Te importaría resumir la sección relevante de la wiki en forma de respuesta para que yo pueda aceptarla? – Geek