Árboles B y B+

De qué trata este capítulo

Todos los árboles balanceados que hemos visto hasta ahora daban por hecho que sus nodos viven en memoria rápida, donde seguir un puntero casi no cuesta nada. Los árboles B tiran ese supuesto a la basura. Cuando un árbol indexa datos en disco —como lo hace toda base de datos y todo sistema de archivos—, cada nivel que bajas es una lectura de disco, más o menos cien mil veces más lenta que un acceso a memoria, y lo único que importa es leer la menor cantidad de bloques posible. Un árbol binario, con sus log₂ n niveles, lee muchísimos de más. La respuesta del árbol B es la anchura radical: mete cientos de llaves en cada nodo, dale a cada nodo cientos de hijos, y el árbol queda de apenas tres o cuatro niveles de alto para millones de llaves. En este capítulo construimos el árbol B clásico, vemos cómo sus nodos se llenan y se parten, y por qué el fan-out —no la astucia— es lo que lo convierte en el índice detrás de los datos del mundo.

Un poco de historia

El árbol B lo inventaron en 1970 Rudolf Bayer y Edward McCreight, trabajando en los laboratorios de investigación de Boeing. Estaban resolviendo un problema muy concreto —cómo indexar archivos grandes guardados en los discos lentos de la época para que una búsqueda no obligara a leer el archivo completo— y su respuesta, el árbol multivía balanceado, resultó tan efectiva que nunca hizo falta reemplazarla. Qué significa la "B" es un misterio genuino que los inventores se han negado con toda malicia a aclarar: se han propuesto Bayer, balanced, Boeing y "broad", y McCreight alguna vez bromeó que "entre más piensas en lo que puede significar la B, mejor entiendes los árboles B". La variante que las bases de datos realmente usan, el árbol B+, llegó poco después. Cincuenta años más tarde, los árboles B y B+ indexan toda base de datos relacional (PostgreSQL, MySQL, Oracle, SQLite), los principales sistemas de archivos (NTFS, HFS+, ext4, Btrfs —el nombre literalmente significa "sistema de archivos de árboles B"—) y un sinfín de almacenes llave-valor. Puede que sea la estructura de datos comercialmente más importante jamás inventada.

La intuición

La clave está en darte cuenta de que, en disco, el costo se cuenta en bloques leídos, no en comparaciones. Leer un bloque de disco te trae unos cuantos miles de bytes al precio de un solo seek lento, así que conviene que cada nodo sea exactamente un bloque y meterle todas las llaves que quepan. Un nodo con, digamos, 128 llaves tiene 129 hijos, así que el árbol se ramifica en 129 direcciones en cada nivel en lugar de 2. Ese fan-out lo es todo: un árbol binario sobre un millón de llaves tiene unos 20 niveles de profundidad —20 lecturas de disco por búsqueda— mientras que un árbol B de orden 128 sobre ese mismo millón de llaves tiene 3 niveles, 3 lecturas de disco. El mismo O(log n) asintótico, pero la base del logaritmo es 128 en vez de 2, y en disco esa base es todo el partido.

Mantener balanceado un árbol B usa el mismo movimiento de desbordar-y-promover que ya viste escondido dentro del árbol rojo-negro. Un nodo guarda entre t−1 y 2t−1 llaves (para un grado mínimo t). Para insertar, encuentras la hoja correcta y sueltas ahí la llave. Si un nodo se desborda más allá de 2t−1 llaves, se parte en dos nodos medio llenos y su llave mediana sube al padre —que a su vez puede desbordarse y partirse—. El árbol crece de altura solo cuando la raíz misma se parte, y como eso pasa hasta arriba, todas las hojas quedan siempre exactamente a la misma profundidad. El balance perfecto sale solo de las particiones, sin necesidad de rotaciones.

Complejidad: cómo escala

Buscar, insertar y eliminar son todas $O(\log n)$ —pero la medida que de verdad importa es el número de niveles, ya que cada nivel es una lectura de disco—. Con un fan-out m, la altura es $\log_m n$, muchísimos menos niveles que los $\log_2 n$ de un árbol binario. La gráfica vuelve concreta esa diferencia, trazando los niveles (≈ lecturas de disco por búsqueda) de un árbol B de orden 128 contra los de un árbol binario balanceado:

Con 500000 llaves el árbol B midió 3 niveles contra los 19 del binario —unas 6× menos lecturas de disco por búsqueda—, y la proporción crece conforme crecen los datos. En hardware real, donde un seek de disco son milisegundos y un acceso a memoria son nanosegundos, convertir 19 lecturas en 3 es la diferencia entre una base de datos usable y una que no lo es. Dentro de un nodo el árbol B hace más comparaciones (recorre hasta 2t−1 llaves), pero esas ocurren en memoria rápida una vez cargado el bloque, así que salen casi gratis comparadas con la lectura que las trajo.

En qué es bueno y en qué no

El árbol B es la estructura correcta —la única razonable— para un índice ordenado que vive en disco o en cualquier almacenamiento donde el acceso sea por bloques y las lecturas sean el cuello de botella. Eso incluye bases de datos y sistemas de archivos, pero también las partes en disco de los almacenes llave-valor y de los motores de búsqueda. Mantiene los datos ordenados (así que soporta consultas por rango y recorridos ordenados, a diferencia de un índice hash), se mantiene balanceado solo, y minimiza por diseño la operación cara: las lecturas de bloques. Su variante cercana, el árbol B+, que guarda todos los registros reales en las hojas y encadena las hojas entre sí, es la que usan las bases de datos en producción, porque convierte los recorridos por rango en una simple caminata por el nivel de las hojas.

Donde es la herramienta equivocada es en memoria. Cuando cada nodo está a un puntero rápido de distancia, los nodos anchos del árbol B y el recorrido dentro del nodo son puro overhead, y un árbol rojo-negro o AVL —o una tabla hash, si no necesitas orden— resulta más simple y más rápido. Toda la ventaja del árbol B está en el modelo de disco; quítale el disco y su razón de existir se va con él. Su eliminación es además genuinamente enredada (los nodos pueden quedar por debajo del mínimo, obligando a pedir llaves prestadas a los hermanos o a fusionar nodos), que es por lo que este capítulo, igual que el del rojo-negro, se concentra en la inserción, que es donde se revela la idea del balanceo.

Los datos, o las entradas

La gráfica de altura construye árboles B de orden 128 en tamaños crecientes y compara sus niveles contra los de un árbol binario balanceado, midiendo lo que de verdad cuesta dinero: lecturas de disco por búsqueda. La animación usa un árbol B chiquito (orden 4, así que los nodos guardan a lo mucho 3 llaves y se parten rápido) e inserta diez llaves, para que veas cómo los nodos se llenan, se desbordan y se parten, con las medianas subiendo hacia la raíz.

Constrúyelo, una función a la vez

La búsqueda recorre las llaves ordenadas de un nodo y luego baja al hijo correcto: una visita a un nodo (lectura de disco) por nivel:

def search(self, key, node=None, probe=None):
    """O(log_m n) node visits, O(t) work per node. Within a node, scan its sorted keys
    for the key or the child to descend into. Each node visited is one disk read in the
    real thing, so the fat nodes mean very few of them."""
    node = self.root if node is None else node
    if probe is not None:
        probe.append(1)             # count this node visit (a "disk read")
    i = 0
    while i < len(node.keys) and key > node.keys[i]:
        i += 1
    if i < len(node.keys) and node.keys[i] == key:
        return True
    if node.leaf:
        return False
    return self.search(key, node.children[i], probe)

La inserción parte cualquier nodo lleno antes de bajar, para que siempre haya espacio, y parte la raíz para que el árbol crezca de altura:

def insert(self, key):
    """Insert into the correct leaf. To keep every level full enough, split any node
    that's already full BEFORE descending into it, so there's always room. If the root
    itself is full, split it into a new root — the only way a B-tree grows taller, which
    keeps all leaves at the same depth."""
    if self.search(key):
        return
    root = self.root
    if len(root.keys) == 2 * self.t - 1:
        new_root = BTreeNode(leaf=False)
        new_root.children.append(root)
        self._split_child(new_root, 0)
        self.root = new_root
        self._insert_nonfull(new_root, key)
    else:
        self._insert_nonfull(root, key)

La partición es el movimiento de balanceo: corta a la mitad un nodo lleno y sube su mediana al padre:

def _split_child(self, parent, i):
    """Split parent.children[i], a full node, into two half nodes and lift its median
    key up into the parent. This is the B-tree's balancing move — the same overflow-and-
    promote a 2-3-4 tree (and a red-black tree) uses, just with wider nodes."""
    t = self.t
    full = parent.children[i]
    sibling = BTreeNode(leaf=full.leaf)
    median = full.keys[t - 1]
    sibling.keys = full.keys[t:]           # right half of the keys
    full.keys = full.keys[:t - 1]          # left half; median moves up
    if not full.leaf:
        sibling.children = full.children[t:]
        full.children = full.children[:t]
    parent.keys.insert(i, median)
    parent.children.insert(i + 1, sibling)

Míralo funcionar

Aquí tienes un árbol B chiquito (cada nodo guarda a lo mucho 3 llaves) construido insertando diez valores. El verde marca el nodo donde cayó la nueva llave. Avanza paso a paso y observa la mecánica: las llaves se van acumulando ordenadas en un nodo hasta que tiene tres; la siguiente llave lo desbordaría, así que el nodo se parte en dos y su llave mediana sube al padre. Cuando la raíz misma se desborda y se parte, el árbol gana un nivel, y como eso solo pasa hasta arriba, cada hoja se mantiene a la misma profundidad todo el tiempo. Fíjate en qué pocos niveles hacen falta para guardar diez llaves, e imagina cada nodo guardando cien en lugar de tres: así es como tres niveles alcanzan para un millón:

El código completo

Las dos versiones en un solo lugar; cambia entre ellas. La pestaña "desde cero" es el árbol B. La pestaña de librería es el único equivalente honesto: una función que calcula la altura de un árbol binario balanceado sobre las mismas llaves —las lecturas de disco que pagarías sin nodos gordos—, porque Python no trae árbol B; es la estructura que vive dentro de tu base de datos, no en tu librería estándar.

"""The B-tree — the balanced search tree reimagined for disk, and the structure that
indexes essentially every database and filesystem in the world.

A binary search tree branches two ways per node, so it's tall — log₂ n levels. But when
each node lives on disk, every level you descend is a disk read, the slowest thing a
computer does, and tallness is death. The B-tree fixes this by making nodes *fat*: each
node holds many keys and has many children (hundreds, in practice), so the tree is
short — log_m n levels — and a lookup touches only a handful of disk blocks. It stays
balanced the way a 2-3-4 tree does: insert into a leaf, and when a node overflows, split
it and push its middle key up to the parent, growing the tree taller only at the root.

This implementation is the classic B-tree with minimum degree `t`: every node (except the
root) holds between t−1 and 2t−1 keys.
"""


class BTreeNode:
    __slots__ = ("keys", "children", "leaf")

    def __init__(self, leaf=True):
        self.keys = []
        self.children = []
        self.leaf = leaf


class BTree:
    def __init__(self, t=3):
        self.t = t                      # minimum degree: max 2t-1 keys, max 2t children
        self.root = BTreeNode(leaf=True)

    # region: search
    def search(self, key, node=None, probe=None):
        """O(log_m n) node visits, O(t) work per node. Within a node, scan its sorted keys
        for the key or the child to descend into. Each node visited is one disk read in the
        real thing, so the fat nodes mean very few of them."""
        node = self.root if node is None else node
        if probe is not None:
            probe.append(1)             # count this node visit (a "disk read")
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            return True
        if node.leaf:
            return False
        return self.search(key, node.children[i], probe)
    # endregion

    # region: insert
    def insert(self, key):
        """Insert into the correct leaf. To keep every level full enough, split any node
        that's already full BEFORE descending into it, so there's always room. If the root
        itself is full, split it into a new root — the only way a B-tree grows taller, which
        keeps all leaves at the same depth."""
        if self.search(key):
            return
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            new_root = BTreeNode(leaf=False)
            new_root.children.append(root)
            self._split_child(new_root, 0)
            self.root = new_root
            self._insert_nonfull(new_root, key)
        else:
            self._insert_nonfull(root, key)
    # endregion

    # region: split_child
    def _split_child(self, parent, i):
        """Split parent.children[i], a full node, into two half nodes and lift its median
        key up into the parent. This is the B-tree's balancing move — the same overflow-and-
        promote a 2-3-4 tree (and a red-black tree) uses, just with wider nodes."""
        t = self.t
        full = parent.children[i]
        sibling = BTreeNode(leaf=full.leaf)
        median = full.keys[t - 1]
        sibling.keys = full.keys[t:]           # right half of the keys
        full.keys = full.keys[:t - 1]          # left half; median moves up
        if not full.leaf:
            sibling.children = full.children[t:]
            full.children = full.children[:t]
        parent.keys.insert(i, median)
        parent.children.insert(i + 1, sibling)
    # endregion

    def _insert_nonfull(self, node, key):
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_nonfull(node.children[i], key)

    def height(self):
        h, node = 1, self.root
        while not node.leaf:
            node = node.children[0]
            h += 1
        return h

    def inorder(self):
        out = []

        def rec(node):
            for i, k in enumerate(node.keys):
                if not node.leaf:
                    rec(node.children[i])
                out.append(k)
            if not node.leaf:
                rec(node.children[-1])

        rec(self.root)
        return out

"""B-trees live in databases and filesystems, not in a Python module — there's no stdlib
B-tree. The point of a B-tree is *height*: because a lookup's cost on disk is the number of
nodes (blocks) it reads, the meaningful comparison is a B-tree's log_m n levels against a
binary tree's log₂ n levels. So the reference here computes the height of a perfectly
balanced BINARY tree over the same number of keys — the number of disk reads you'd pay
without the B-tree's fat nodes.
"""
import math


# region: binary_height
def balanced_binary_height(n):
    """Height (levels, ≈ disk reads per lookup) of a perfectly balanced BINARY search tree
    over n keys: ⌈log₂(n+1)⌉. The B-tree's whole reason to exist is to make this number
    much smaller by branching hundreds of ways instead of two."""
    if n <= 0:
        return 0
    return math.ceil(math.log2(n + 1))
# endregion

Desde cero vs librería

Aquí no hay duelo de velocidad, porque todo el propósito del árbol B es invisible en un benchmark puramente en memoria: las lecturas de disco que ahorra no aparecen cuando todo está en RAM. La comparación real es la que hace la gráfica de altura: 3 niveles contra 19 con medio millón de llaves. Para sentir lo que eso significa, ponlo en tiempo de disco. Un seek aleatorio de disco anda en el orden de un milisegundo; un acceso a memoria, cien nanosegundos. Diecinueve seeks son ~19 milisegundos por búsqueda; tres seeks son ~3. Multiplícalo por los millones de búsquedas que atiende una base de datos y la diferencia es entre un sistema que responde al instante y uno que se arrastra. Por eso importa el árbol B: no calcula una mejor respuesta que un árbol rojo-negro, calcula la misma respuesta tocando seis veces menos la parte lenta de la máquina. Empata tu estructura con la jerarquía de memoria sobre la que corre: la lección más profunda de las estructuras de datos prácticas, y la que el árbol B enseña con más claridad.

Dónde te lo vas a topar en la vida real

Te topas con árboles B cada vez que consultas una base de datos. Crea un índice en PostgreSQL, MySQL, Oracle o SQLite y ya construiste un árbol B+; cada búsqueda indexada y cada recorrido por rango lo caminan. Los sistemas de archivos están construidos sobre ellos: NTFS, HFS+, APFS, los directorios de ext4 y Btrfs (bautizado por la estructura) organizan archivos y metadatos como árboles B para que abrir un archivo dentro de un directorio enorme siga siendo rápido. Los almacenes llave-valor y de documentos (desde BerkeleyDB hasta los motores modernos) usan árboles B o sus primos log-structured para el ordenamiento en disco. Incluso a menor escala, cada vez que los datos son demasiado grandes para la memoria y tienen que quedarse ordenados en almacenamiento, el árbol B es la respuesta. Es, calladamente, una de las estructuras de datos más ejecutadas del planeta.

Puntos clave

Un árbol B es un árbol de búsqueda balanceado con nodos muy anchos —un bloque de disco cada uno—, así que su altura es $\log_m n$ en lugar de $\log_2 n$, convirtiendo una búsqueda de veinte lecturas de disco en una de tres. Se mantiene balanceado partiendo los nodos que se desbordan y promoviendo medianas, dejando todas las hojas a la misma profundidad sin ninguna rotación, y su variante B+ encadena las hojas para hacer rápidos los recorridos por rango. Es la estructura correcta justo cuando los datos viven en disco y las lecturas son el cuello de botella —por eso indexa prácticamente toda base de datos y todo sistema de archivos— y la equivocada en memoria, donde un árbol rojo-negro es más simple.

Con esto cerramos los árboles clásicos. Queda una estructura en este bloque, y es un árbol de naturaleza completamente distinta. Union-Find no guarda datos ordenados ni responde consultas por rango; lleva la cuenta de qué elementos pertenecen al mismo grupo, fusionando grupos y probando pertenencia en tiempo casi constante. Es la estructura detrás del árbol de expansión mínima de Kruskal, de las componentes conexas y de la conectividad en redes, y cierra el bloque de árboles mostrando que un árbol también puede ser una herramienta para agrupar, no solo para buscar.