26 de junio - JoseA4718/Portafolio-I-2020 GitHub Wiki
Se realizó el quiz #7, despúes el profe nos puso en parejas a investigar sobre los árboles n-arios y árboles B.
Árboles N-arios
Son árboles con n cantidad de hijos máximo por nodo. En este árbol es difícil acceder al hijo de un nodo debido a que no se sabe cuántos hijos tiene, para esto se puede obtener la cantidad tomando uno de los hijos y preguntándole cuantos hermanos tiene pasándolos a una lista y preguntando el largo de la lista.
Árboles B
En un árbol B de orden m o m-ario:
- Todas las hojas están en el mismo nivel (se asegura que está perfectamente balanceado).
- A los nodos se les llama páginas.
- Todas las páginas internas, excepto la raíz, tienen un máximo de m branches (no vacías) y un mínimo de m/2.
- La cantidad de llaves es la cantidad de branches - 1.
- La raíz tiene un máximo de m branches.
- El propósito del árbol es reducir la profundidad del árbol.
La idea es que se guarde la mayor cantidad de información en el menor espacio posible. Esto significa que todas las páginas tengan al menos m/2 branches, hasta m. Menos de m/2 no se permite. El orden m depende de la capacidad del disco duro.
Insertion:
Se busca la key por insertar en el árbol. Existe una ruta de búsqueda determinada por las llaves en las páginas. Si la llave no está en el árbol, la ruta de búsqueda termina en una hoja. Si la hoja no está llena, se hace la inserción. Si la hoja está llena, se hace un split.