I) OBJETIVOS
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
|
DOCENCIA UNIVERSITARIA > Sistemas de Bases de Datos II > Laboratorio de Sistemas de Bases de Datos II >