Saltar al contenido principal

Árboles B y B+

¿Qué es un Árbol B?​

Un Árbol B (B-Tree) es una estructura de datos auto-balanceada de búsqueda generalizada, diseñada para trabajar eficientemente con sistemas de almacenamiento secundario (como discos duros o bases de datos). Fue desarrollado por Bayer y McCreight en 1972.

Se usa ampliamente en sistemas de archivos, gestores de bases de datos y sistemas indexados, donde las operaciones de inserción, eliminación y búsqueda deben mantenerse en tiempo logarítmico incluso con grandes volúmenes de datos.

Características principales de un Árbol B (orden m)​

  • Cada nodo interno puede tener como máximo m hijos.
  • Cada nodo (excepto la raíz) tiene al menos [m⁄2] hijos.
  • Cada nodo contiene k claves, donde ⌈m⁄2⌉−1 ≤ k ≤ m−1.
  • Todos los datos están distribuidos en nodos internos y hojas.
  • Las hojas están al mismo nivel.
  • El árbol se rebalancea mediante divisiones de nodos cuando se insertan elementos.

¿Qué es un Árbol B+?​

Un Árbol B+ (B+ Tree) es una variación del Árbol B con diferencias clave:

  • Solo las hojas almacenan los datos reales.
  • Los nodos internos solo contienen claves de guía.
  • Las hojas están enlazadas secuencialmente, facilitando recorridos en orden.
  • Ofrece mejor rendimiento en búsquedas y rangos de valores.

Diferencia entre Árbol B y Árbol B+​

CaracterísticaÁrbol BÁrbol B+
Almacenamiento de datosNodos internos y hojasSolo en hojas
Recorridos secuencialesNo optimizadosEficientes (listas enlazadas)
Nodos hoja enlazadosNoSí
Claves en nodos internosPueden contener datosSolo claves

Estructura de un árbol B (orden 3)​

Estructura de un árbol B+ (orden 3)​

Ejemplo técnico B Tree​

BTreeNode.java
public class BTreeNode {
    int[] keys;
    int t; // Grado mínimo
    BTreeNode[] children;
    int numKeys;
    boolean isLeaf;

    public BTreeNode(int t, boolean isLeaf) {
        this.t = t;
        this.isLeaf = isLeaf;
        this.keys = new int[2 * t - 1];
        this.children = new BTreeNode[2 * t];
        this.numKeys = 0;
    }

    public void traverse() {
        for (int i = 0; i < numKeys; i++) {
            if (!isLeaf) children[i].traverse();
            System.out.print(keys[i] + " ");
        }
        if (!isLeaf) children[numKeys].traverse();
    }

    public BTreeNode search(int key) {
        int i = 0;
        while (i < numKeys && key > keys[i]) i++;
        if (i < numKeys && keys[i] == key) return this;
        if (isLeaf) return null;
        return children[i].search(key);
    }

    public void insertNonFull(int key) {
        int i = numKeys - 1;
        if (isLeaf) {
            while (i >= 0 && keys[i] > key) {
                keys[i + 1] = keys[i];
                i--;
            }
            keys[i + 1] = key;
            numKeys++;
        } else {
            while (i >= 0 && keys[i] > key) i--;
            if (children[i + 1].numKeys == 2 * t - 1) {
                splitChild(i + 1, children[i + 1]);
                if (keys[i + 1] < key) i++;
            }
            children[i + 1].insertNonFull(key);
        }
    }

    public void splitChild(int i, BTreeNode y) {
        BTreeNode z = new BTreeNode(y.t, y.isLeaf);
        z.numKeys = t - 1;

        for (int j = 0; j < t - 1; j++)
            z.keys[j] = y.keys[j + t];

        if (!y.isLeaf)
            for (int j = 0; j < t; j++)
                z.children[j] = y.children[j + t];

        y.numKeys = t - 1;

        for (int j = numKeys; j >= i + 1; j--)
            children[j + 1] = children[j];

        children[i + 1] = z;

        for (int j = numKeys - 1; j >= i; j--)
            keys[j + 1] = keys[j];

        keys[i] = y.keys[t - 1];
        numKeys++;
    }

    // Eliminación
    public void remove(int key) {
        int idx = findKey(key);

        if (idx < numKeys && keys[idx] == key) {
            if (isLeaf)
                removeFromLeaf(idx);
            else
                removeFromNonLeaf(idx);
        } else {
            if (isLeaf) return; // No existe

            boolean flag = (idx == numKeys);

            if (children[idx].numKeys < t)
                fill(idx);

            if (flag && idx > numKeys)
                children[idx - 1].remove(key);
            else
                children[idx].remove(key);
        }
    }

    private int findKey(int key) {
        int idx = 0;
        while (idx < numKeys && keys[idx] < key) ++idx;
        return idx;
    }

    private void removeFromLeaf(int idx) {
        for (int i = idx + 1; i < numKeys; ++i)
            keys[i - 1] = keys[i];
        numKeys--;
    }

    private void removeFromNonLeaf(int idx) {
        int k = keys[idx];
        if (children[idx].numKeys >= t) {
            int pred = getPredecessor(idx);
            keys[idx] = pred;
            children[idx].remove(pred);
        } else if (children[idx + 1].numKeys >= t) {
            int succ = getSuccessor(idx);
            keys[idx] = succ;
            children[idx + 1].remove(succ);
        } else {
            merge(idx);
            children[idx].remove(k);
        }
    }

    private int getPredecessor(int idx) {
        BTreeNode cur = children[idx];
        while (!cur.isLeaf)
            cur = cur.children[cur.numKeys];
        return cur.keys[cur.numKeys - 1];
    }

    private int getSuccessor(int idx) {
        BTreeNode cur = children[idx + 1];
        while (!cur.isLeaf)
            cur = cur.children[0];
        return cur.keys[0];
    }

    private void fill(int idx) {
        if (idx != 0 && children[idx - 1].numKeys >= t)
            borrowFromPrev(idx);
        else if (idx != numKeys && children[idx + 1].numKeys >= t)
            borrowFromNext(idx);
        else {
            if (idx != numKeys)
                merge(idx);
            else
                merge(idx - 1);
        }
    }

    private void borrowFromPrev(int idx) {
        BTreeNode child = children[idx];
        BTreeNode sibling = children[idx - 1];

        for (int i = child.numKeys - 1; i >= 0; --i)
            child.keys[i + 1] = child.keys[i];

        if (!child.isLeaf)
            for (int i = child.numKeys; i >= 0; --i)
                child.children[i + 1] = child.children[i];

        child.keys[0] = keys[idx - 1];

        if (!child.isLeaf)
            child.children[0] = sibling.children[sibling.numKeys];

        keys[idx - 1] = sibling.keys[sibling.numKeys - 1];

        child.numKeys += 1;
        sibling.numKeys -= 1;
    }

    private void borrowFromNext(int idx) {
        BTreeNode child = children[idx];
        BTreeNode sibling = children[idx + 1];

        child.keys[child.numKeys] = keys[idx];

        if (!child.isLeaf)
            child.children[child.numKeys + 1] = sibling.children[0];

        keys[idx] = sibling.keys[0];

        for (int i = 1; i < sibling.numKeys; ++i)
            sibling.keys[i - 1] = sibling.keys[i];

        if (!sibling.isLeaf)
            for (int i = 1; i <= sibling.numKeys; ++i)
                sibling.children[i - 1] = sibling.children[i];

        child.numKeys += 1;
        sibling.numKeys -= 1;
    }

    private void merge(int idx) {
        BTreeNode child = children[idx];
        BTreeNode sibling = children[idx + 1];

        child.keys[t - 1] = keys[idx];

        for (int i = 0; i < sibling.numKeys; ++i)
            child.keys[i + t] = sibling.keys[i];

        if (!child.isLeaf)
            for (int i = 0; i <= sibling.numKeys; ++i)
                child.children[i + t] = sibling.children[i];

        for (int i = idx + 1; i < numKeys; ++i)
            keys[i - 1] = keys[i];

        for (int i = idx + 2; i <= numKeys; ++i)
            children[i - 1] = children[i];

        child.numKeys += sibling.numKeys + 1;
        numKeys--;
    }
}
BTree.java
public class BTree {
    private final int t;
    private BTreeNode root;

    public BTree(int t) {
        this.t = t;
        this.root = null;
    }

    public void traverse() {
        if (root != null)
            root.traverse();
    }

    public BTreeNode search(int key) {
        return (root == null) ? null : root.search(key);
    }

    public void insert(int key) {
        if (root == null) {
            root = new BTreeNode(t, true);
            root.keys[0] = key;
            root.numKeys = 1;
        } else {
            if (root.numKeys == 2 * t - 1) {
                BTreeNode s = new BTreeNode(t, false);
                s.children[0] = root;
                s.splitChild(0, root);

                int i = 0;
                if (s.keys[0] < key)
                    i++;
                s.children[i].insertNonFull(key);

                root = s;
            } else {
                root.insertNonFull(key);
            }
        }
    }

    public void delete(int key) {
        if (root == null)
            return;

        root.remove(key);

        if (root.numKeys == 0) {
            root = (root.isLeaf) ? null : root.children[0];
        }
    }
}

Ejemplo técnico B+ Tree​

BPlusNode.java
import java.util.ArrayList;
import java.util.List;

/**
 * Represents a node in a B+ Tree.
 * Each node can store multiple keys and child pointers.
 */
public class BPlusNode {
    List<Integer> keys;
    List<BPlusNode> children;
    BPlusNode parent;
    boolean isLeaf;
    BPlusNode next; // For linked leaf nodes

    public BPlusNode(boolean isLeaf) {
        this.isLeaf = isLeaf;
        this.keys = new ArrayList<>();
        this.children = new ArrayList<>();
        this.parent = null;
        this.next = null;
    }

    public boolean isOverflow(int order) {
        return keys.size() > order - 1;
    }

    public boolean isUnderflow(int order) {
        return keys.size() < Math.ceil(order / 2.0) - 1;
    }

    @Override
    public String toString() {
        return keys.toString();
    }
}
package edu.usta.tree.bplus;

import java.util.*;

/**
 * Implementation of a B+ Tree with insert, search, delete and traversal.
 * Order defines the maximum number of children per node.
 */
public class BPlusTree {
    private final int order;
    private BPlusNode root;

    public BPlusTree(int order) {
        this.order = order;
        this.root = new BPlusNode(true);
    }

    /** Search key in the tree */
    public boolean search(int key) {
        BPlusNode node = findLeafNode(root, key);
        return node.keys.contains(key);
    }

    /** Insert a key */
    public void insert(int key) {
        BPlusNode leaf = findLeafNode(root, key);
        insertInLeaf(leaf, key);

        if (leaf.isOverflow(order)) {
            splitNode(leaf);
        }
    }

    /** Delete a key */
    public void delete(int key) {
        BPlusNode leaf = findLeafNode(root, key);
        if (!leaf.keys.contains(key)) return;

        leaf.keys.remove(Integer.valueOf(key));

        if (leaf == root) {
            if (leaf.keys.isEmpty()) root = new BPlusNode(true);
            return;
        }

        if (leaf.isUnderflow(order)) {
            rebalanceAfterDeletion(leaf);
        }
    }

    /** Print the tree level by level */
    public void printTree() {
        Queue<BPlusNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                BPlusNode node = queue.poll();
                System.out.print(node.keys + " ");
                if (!node.isLeaf) queue.addAll(node.children);
            }
            System.out.println();
        }
    }

    /** Find leaf node for a given key */
    private BPlusNode findLeafNode(BPlusNode node, int key) {
        while (!node.isLeaf) {
            int i = 0;
            while (i < node.keys.size() && key >= node.keys.get(i)) i++;
            node = node.children.get(i);
        }
        return node;
    }

    /** Insert key in leaf */
    private void insertInLeaf(BPlusNode leaf, int key) {
        int pos = 0;
        while (pos < leaf.keys.size() && leaf.keys.get(pos) < key) pos++;
        leaf.keys.add(pos, key);
    }

    /** Split an overflowing node */
    private void splitNode(BPlusNode node) {
        int midIndex = node.keys.size() / 2;
        BPlusNode sibling = new BPlusNode(node.isLeaf);
        sibling.parent = node.parent;

        // Move half of the keys
        sibling.keys.addAll(node.keys.subList(midIndex, node.keys.size()));
        node.keys = new ArrayList<>(node.keys.subList(0, midIndex));

        // Leaf split
        if (node.isLeaf) {
            sibling.next = node.next;
            node.next = sibling;
        } else { // Internal split
            sibling.children.addAll(node.children.subList(midIndex + 1, node.children.size()));
            for (BPlusNode child : sibling.children) child.parent = sibling;
            node.children = new ArrayList<>(node.children.subList(0, midIndex + 1));
        }

        int upKey = sibling.keys.get(0);
        if (node.isLeaf) upKey = sibling.keys.get(0); // propagate smallest key up

        if (node.parent == null) {
            BPlusNode newRoot = new BPlusNode(false);
            newRoot.keys.add(upKey);
            newRoot.children.add(node);
            newRoot.children.add(sibling);
            node.parent = newRoot;
            sibling.parent = newRoot;
            root = newRoot;
        } else {
            BPlusNode parent = node.parent;
            int insertPos = 0;
            while (insertPos < parent.keys.size() && parent.keys.get(insertPos) < upKey) insertPos++;
            parent.keys.add(insertPos, upKey);
            parent.children.add(insertPos + 1, sibling);
            if (parent.isOverflow(order)) splitNode(parent);
        }
    }

    /** Rebalance after deletion */
    private void rebalanceAfterDeletion(BPlusNode node) {
        BPlusNode parent = node.parent;
        if (parent == null) return;

        int index = parent.children.indexOf(node);
        BPlusNode leftSibling = (index > 0) ? parent.children.get(index - 1) : null;
        BPlusNode rightSibling = (index < parent.children.size() - 1) ? parent.children.get(index + 1) : null;

        if (leftSibling != null && leftSibling.keys.size() > Math.ceil(order / 2.0) - 1) {
            int borrowedKey = leftSibling.keys.remove(leftSibling.keys.size() - 1);
            node.keys.add(0, borrowedKey);
            parent.keys.set(index - 1, node.keys.get(0));
        } else if (rightSibling != null && rightSibling.keys.size() > Math.ceil(order / 2.0) - 1) {
            int borrowedKey = rightSibling.keys.remove(0);
            node.keys.add(borrowedKey);
            parent.keys.set(index, rightSibling.keys.get(0));
        } else {
            if (leftSibling != null) {
                leftSibling.keys.addAll(node.keys);
                leftSibling.next = node.next;
                parent.keys.remove(index - 1);
                parent.children.remove(node);
            } else if (rightSibling != null) {
                node.keys.addAll(rightSibling.keys);
                node.next = rightSibling.next;
                parent.keys.remove(index);
                parent.children.remove(rightSibling);
            }

            if (parent == root && parent.keys.isEmpty()) {
                root = node;
                node.parent = null;
            } else if (parent.isUnderflow(order)) {
                rebalanceAfterDeletion(parent);
            }
        }
    }

    /** For testing */
    public List<Integer> traverseLeafKeys() {
        List<Integer> result = new ArrayList<>();
        BPlusNode current = root;
        while (!current.isLeaf) current = current.children.get(0);
        while (current != null) {
            result.addAll(current.keys);
            current = current.next;
        }
        return result;
    }
}

Aplicaciones prácticas​

  • Bases de datos (MySQL, PostgreSQL, Oracle): índices tipo B+ Tree.
  • Sistemas de archivos: NTFS (Windows), HFS+ (macOS), Ext4 (Linux).
  • Almacenamiento en disco: lectura secuencial optimizada.
  • Sistemas OLAP: permiten exploración rápida de rangos.

Referencias​