Laboratorio 0006: Indices de Árboles B+

publicado a la‎(s)‎ 17 jul. 2012 0:27 por Hernan Nina Hanco   [ actualizado el 6 ago. 2013 13:42 ]
I) OBJETIVOS
  • Implementar archivos de Índices de Árboles B+.

II) MARCO CONCEPTUAL

Ver la sección
3.3.1. Algoritmos en Árboles B+ de la Guía de Sistemas de Bases de Datos II


III) PRÁCTICAS DE LABORATORIO
1) Implementación básica de un árbol B+

Clase que representa un Nodo de Árbol B+
package org.taqque.indice.arbolbmas;

/**
 *
 * @author hernan
 */
public class Nodo {

    private int n;
    private int m = -1; //último puntero
    private int nK = -1; // última clave
    private Object[] punteros;
    private int[] claves;

    public Nodo(int n) {
        this.n = n;
        punteros = new Object[n];
        for (int i = 0; i < n; i++) {
            punteros[i] = null;
        }
        claves = new int[n - 1];
        for (int j = 0; j < n - 1; j++) {
            claves[j] = -1;
        }
    }
    /*
     * ki minimo valor de la clave de busqueda, si lo hay, mayor que Valor clave buscado
     */

    public int posClave(int valor) {
        int pos = -1;
        for (int i = 0; i <= nK; i++) {
            if (claves[i] != -1) {
                if (claves[i] < valor) {
                    pos = i;
                } else {
                    break;
                }
            }
        }
        return pos;
    }

    public boolean existeClave(int valor) {
        for (int i = 0; i < nK; i++) {
            if (claves[i] == valor) {
                return true;
            }
        }
        return false;
    }

    public void insertarClave(Object p, int k, int pos) {
        desplazarEntradas(pos);
        punteros[pos] = p;
        m++;
        claves[pos] = k;
        nK++;
    }

    private void desplazarEntradas(int pos) {
        for (int i = nK; i >= pos; i--) {
            int k = claves[i];
            claves[i + 1] = k;
        }
        for (int i = m; i >= pos; i--) {
            Object p = punteros[i];
            punteros[i + 1] = p;
        }
    }

    public void copiarEntradasPunteros(Nodo t, int ini, int fin) {
        int j=0;
        for (int i = ini; i <= fin; i++) {
            t.getPunteros()[j++] = punteros[i];
            t.setM(t.getM() + 1);
        }
    }

    public void copiarEntradasClaves(Nodo t, int ini, int fin) {
        int j=0;
        for (int i = ini; i <= fin; i++) {
            t.getClaves()[j++] = claves[i];
            t.setnK(t.getnK() + 1);
        }
    }

    public void borrarEntradas() {
        for (int i = 0; i <= m; i++) {
            punteros[i] = null;
        }
        for (int i = 0; i <= nK; i++) {
            claves[i] = -1;
        }


    }

    public int[] getClaves() {
        return claves;
    }

    public void setClaves(int[] claves) {
        this.claves = claves;
    }

    public Object[] getPunteros() {
        return punteros;
    }

    public void setPunteros(Object[] punteros) {
        this.punteros = punteros;
    }

    public int getM() {
        return m;
    }

    public void setM(int m) {
        this.m = m;
    }

    public int getN() {
        return n;
    }

    public void setN(int n) {
        this.n = n;
    }

    public int getnK() {
        return nK;
    }

    public void setnK(int nK) {
        this.nK = nK;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < n; i++) {
            sb.append("(");
            sb.append(punteros[i] != null ? punteros[i] : "null");
            if (n > i + 1) {
                sb.append("|");
                sb.append(claves[i] != -1 ? claves[i] : "null");
                sb.append(")");
            }
        }
        sb.append(")");
        sb.append("]");
        return sb.toString();
    }
}

Clase que representa un árbol B+
package org.taqque.indice.arbolbmas;

/**
 *
 * @author hernan
 */
public class ArbolBMas {

    private int n;
    private Nodo raiz;

    public ArbolBMas(int n) {
        this.n = n;
        raiz = new Nodo(n);
    }

    public Nodo buscar(int valor) {
        Nodo c = buscarNodo(valor);
        // si hay un valor de de la clave ki en C tal que ki=V
        // entonces el puntero Pi conduce al registro o cajon deseado.
        if (c.existeClave(valor)) {
            return c;
        } else // no existe ningun registro con el valor de la clave k
        {
            return null;
        }
    }

    public Nodo buscarNodo(int valor) {
        Nodo c = raiz;
        while (!esHoja(c)) {
            // ki minimo valor de la clave de busqueda, si lo hay, mayor que Valor buscado
            int i = c.posClave(valor);

            if (i == -1) // no hay tal valor ki 
            {
                // buscar en el nodo señalado por el último puntero
                // m - último puntero
                int m = c.getM();
                // hacer que ahora C sea el puntero que se apunta desde pm
                c = (Nodo) c.getPunteros()[m];
            } else // existe el ki
            {
                c = (Nodo) c.getPunteros()[i];
            }
        }
        return c;
    }

    public boolean esHoja(Nodo nodo) {
        Object[] punteros = nodo.getPunteros();
        if (punteros[0] instanceof Nodo) {
            return false;
        }
        return true;
    }

    public void insertar(int k, Object p) {
        // Hallar el nodo hoja L que debe contener el valor de la clave k
        Nodo l = buscarNodo(k);
        // Si L tiene menos de n-1 valores de clave
        if (l.getnK() + 1 < n - 1) {
            insertarEnHoja(l, k, p);
        } else // L ya tiene n-1 valores de la clave, debemos dividirlo
        {
            // Crear un nodo L'
            Nodo lPrima = new Nodo(n);
            // Copiar L.P1 .... L.Kn-1 a un bloque de memoria T que pueda almacenar n pares (puntero y valor clave)
            Nodo t = new Nodo(n + 1);
            l.copiarEntradasPunteros(t, 0, l.getM());
            l.copiarEntradasClaves(t, 0, l.getnK());
            insertarEnHoja(t, k, p);
            lPrima.getPunteros()[n-1] = l.getPunteros()[n-1];
            l.getPunteros()[n-1] = lPrima;
            l.borrarEntradas();
            int ini = 0;
            int fin = Math.round((t.getN()) / 2);
            t.copiarEntradasPunteros(l, ini, fin-1);
            t.copiarEntradasClaves(l, ini, fin-1);
            
            t.copiarEntradasPunteros(lPrima, fin, t.getM());
            t.copiarEntradasClaves(lPrima, fin, t.getnK());
                    
            int kPrima = lPrima.getClaves()[0];
            insertarEnPadre(l, kPrima, lPrima);
        }
    }

    public void insertarEnHoja(Nodo l, int k, Object p) {
        int k0 = l.getClaves()[0];
        // Si k < L.K1 la primera clave de L, insertar p,k antes de L.P1
        if (k < k0 || k0 == -1) {
            l.insertarClave(p, k, 0);
        } else {
            int pos = l.posClave(k);
            System.out.println("Pos: "+pos);
            l.insertarClave(p, k, pos+1);
        }

    }
    public void insertarEnPadre(Nodo N, int k, Nodo nPrima) {
        if (N == raiz) // si n es la raíz
        {
            Nodo r = new Nodo(n);
            r.getPunteros()[0] = N;
            r.getClaves()[0] = k;
            r.getPunteros()[1] = nPrima;
            r.setM(2);
            raiz = r;
            return;
        }
    }
    

    public static void main(String[] args) {
        ArbolBMas arbol = new ArbolBMas(4);
        arbol.insertar(2, null);
        arbol.insertar(3, null);
        arbol.insertar(5, null);
        arbol.insertar(7, null);
        System.out.println(arbol.raiz);
    }
}

Tarea
  1. Implementar un archivo de Indice con estructura de árbol B+ para una determinada relación.

Comments