Saltar al contenido
wandres.dev
Iniciar sesión

Caso real

SQLite y BTreeMap

SQLite, la base de datos más desplegada del mundo, guarda cada tabla y cada índice como un B-tree de páginas. Rust no ofrece un árbol binario de búsqueda en su biblioteca estándar: su diccionario ordenado, BTreeMap, es un B-tree en memoria, porque en memoria también hay jerarquía (caché y RAM) y los nodos anchos ahorran saltos y reservas.

Haz la cuenta de por qué una página llena de claves es el tamaño natural: una página de 4096 bytes, claves de 8 bytes y enlaces de 8 bytes. ¿Cuántas claves entran en un nodo y cuántos niveles hacen falta para diez millones de claves?

Una página de 4096 bytes guarda un nodo de B-tree. Cada clave ocupa 8 bytes y cada enlace a un hijo, 8 bytes; un nodo con k claves tiene k + 1 enlaces (ignora cualquier otro dato). ¿Cuántas claves caben como máximo en un nodo, y cuántos niveles llenos hacen falta para guardar 10 000 000 de claves?