database - simulador - clasificacion de arboles estructura de datos
¿Ventaja de los árboles B+sobre BSTs? (2)
Estoy aprendiendo sobre árboles B + en una clase sobre bases de datos y me preguntaba qué ventajas concretas darían los árboles B + sobre los árboles de búsqueda binarios.
Parece que ambos tienen una complejidad promedio de O (logN) para la mayoría de las operaciones notables, pero los árboles B + también tienen un tiempo de búsqueda adicional (¿insignificante?) En cada nodo secundario, donde las BST obviamente solo toman O (1) tiempo para determinar qué nodo secundario para avanzar a
¿Qué ventajas reales hacen que los árboles B + sean más populares en las bases de datos que los BST?
El almacenamiento de datos en la vida real (por ejemplo, en DB) requiere una gran cantidad de datos para ser almacenados. Dado que la recuperación de datos es la operación básica en cuestión, es bastante lento leer los datos del disco que la RAM.
Ahora, esta es la trampa ...
BST almacena datos menores en un nodo en comparación con B + Trees. Esto resulta en el aumento de la altura de BST que los árboles B +. Así que se almacenan en el disco en lugar de RAM.
Cada vez que se deben recuperar datos del árbol, los datos del disco se deben cargar en la memoria principal (lo cual, por supuesto, es un proceso que lleva mucho tiempo) mientras que, en el caso de los árboles B +, los datos ya están allí. en la RAM y el nodo requerido se recupera directamente y los datos se recuperan de ese nodo que puede contener muchos hijos (pero el tiempo total para la recuperación de datos es menor en el caso de árboles B + porque no hay necesidad de cargar datos desde el disco a la RAM).
La principal ventaja del árbol B + (y los árboles B en general) sobre los árboles de búsqueda binarios es que juegan bien con cachés. Si tiene un árbol de búsqueda binario cuyos nodos se almacenan en un orden más o menos aleatorio en la memoria, entonces cada vez que siga un puntero, la máquina tendrá que introducir un nuevo bloque de memoria en la caché del procesador, que es mucho más lento que Accediendo a la memoria ya en caché.
El B + -tree y el B-tree funcionan haciendo que cada nodo almacene una gran cantidad de claves o valores y tenga una gran cantidad de hijos. Por lo general, se empaquetan de una manera que hace posible que un solo nodo encaje bien en la memoria caché (o, si se almacena en el disco, se extraiga del disco en una sola operación de lectura). Luego, tiene que trabajar más para encontrar una clave dentro del nodo o determinar qué niño leer a continuación, pero dado que todos los accesos a la memoria que se realizan en un solo nodo se pueden hacer sin volver al disco, los tiempos de acceso son muy reducidos. Esto significa que aunque, en principio, una BST podría ser mejor en términos de número de accesos a la memoria, el árbol B + y el árbol B pueden funcionar mejor en términos del tiempo de ejecución de esos accesos a la memoria.
El caso de uso típico de un árbol B + o árbol B se encuentra en una base de datos, donde hay una gran cantidad de información y los datos son tan numerosos que no todos caben en la memoria principal. En consecuencia, los datos se pueden almacenar en un árbol B + o en un disco duro en algún lugar. Esto minimiza el número de lecturas de disco necesarias para extraer los datos durante las búsquedas. Algunos sistemas de archivos (como ext4, creo) usan B-trees también por la misma razón: minimizan el número de búsquedas de disco necesarias, que es el verdadero cuello de botella.
¡Espero que esto ayude!