Saltar al contenido
wandres.dev
Iniciar sesión

Modelo por capas

Nodos anchos

Un B-tree de orden m es un árbol de búsqueda donde cada nodo guarda varias claves ordenadas y tiene un hijo más que claves:

Un B-tree con nodos anchosLa raíz es un nodo ancho con dos claves, 20 y 40, y tres hijos. El primer hijo, [5 | 10 | 15], tiene claves menores que 20. El segundo, [25 | 30], entre 20 y 40. El tercero, [45 | 50 | 60], mayores que 40. Las tres hojas están al mismo nivel. Las flechas salen de entre las claves de la raíz.204051015claves < 202530entre 20 y 40455060claves > 40raízdos claves, tres hijoslas tres hojas están a la misma profundidad
Cada nodo guarda varias claves ordenadas, y las flechas salen de entre ellas: dos claves en la raíz, tres hijos.

El invariante de orden se generaliza: las claves del primer hijo son menores que 20; las del segundo, entre 20 y 40; las del tercero, mayores que 40.

Y un invariante de forma:

Texto
todas las hojas están a la misma profundidadcada nodo (salvo la raíz) está al menos medio lleno

Con m grande (cientos de claves por nodo), la altura es log en base m de n: muy pequeña. Para buscar, en cada nodo se hace una búsqueda binaria entre sus claves y se baja al hijo que corresponde.

Un B-tree tiene la raíz [30 | 60] y tres hojas como hijos: [10 | 20], [40 | 50] y [70 | 80 | 90]. Buscas 55. ¿Qué nodos visitas y qué resultado obtienes?