Caso real
El maple tree de Linux
El kernel de Linux guardaba las regiones de memoria de cada proceso en un árbol rojinegro, más una lista y una caché auxiliar. En 2022 las reemplazó por el «maple tree», un árbol de rangos con muchas claves por nodo, del estilo de un B-tree: menos saltos de puntero, mejor uso de la caché y mejor con varios procesadores leyendo a la vez.
Haz la cuenta con 500 000 claves. Un árbol binario balanceado con los niveles llenos guarda 2^h − 1 claves en h niveles. Uno con nodos de hasta 99 claves y 100 hijos guarda 100^h − 1. ¿Cuántos niveles, es decir, cuántos saltos de puntero, necesita cada uno?