definición
En la informática, un árbol B es un árbol de equilibrio que mantiene los datos en orden. Esta estructura de datos permite que la búsqueda de datos, el acceso secuencial, la inserción de datos y las operaciones de eliminación se completen en el tiempo logarítmico.
¿Por qué introducir b-tree?
En primer lugar, incluido el árbol rojo y negro que presentamos anteriormente, es un árbol de búsqueda interno que almacena la entrada en la memoria .
El árbol B es una extensión del algoritmo de árbol de balance anterior. Admite búsquedas externas para tablas de símbolos guardadas en disco o red . Estos archivos pueden ser mucho más grandes que la entrada que consideramos antes (difícil de almacenar en la memoria).
Dado que el contenido se almacena en el disco, la E/S del disco lee y escribe con demasiada frecuencia debido a la gran profundidad del árbol (la tasa de lectura y escritura del disco es limitada), lo que conduce a una eficiencia de consulta ineficiente.
Entonces es naturalmente importante reducir la profundidad del árbol. Por lo tanto, introducimos el árbol de búsqueda B de múltiples vías.
Características
Cada nodo en el árbol contiene en la mayoría de los niños M (m> = 2);
Excepto por el nodo raíz y el nodo de hoja, cada nodo tiene al menos [techo (m/2)] niños (donde el techo (x) es una función que toma el límite superior);
Si el nodo raíz no es un nodo de hoja, habrá al menos 2 niños (caso especial: no hay nodo raíz para los niños, es decir, el nodo raíz es un nodo de hoja, y todo el árbol tiene solo un nodo raíz);
Todos los nodos de hoja aparecen en la misma capa (capa inferior), y los nodos de hoja son nodos externos, que guardan el contenido, a saber, la clave y el valor .
Otros nodos son nodos internos, que guardan el índice, a saber, la clave y siguiente .
Palabras clave de los nodos internos: K [1], K [2], ..., K [M-1]; y k [i] <k [i+1];
Pointers al lado del nodo de contenido: P [1], P [2], ..., P [M]; Donde P [1] apunta a un subárbol con la palabra clave menor que K [1], P [M] apunta a un subárbol con la palabra clave mayor que K [M-1], y otros P [i] apunta a un subárbol con la palabra clave (k [i-1], k [i]);
Por ejemplo: (M = 3)
Encontrar e insertar
Por conveniencia, aquí se usa una clave Sentinel especial, que es más pequeña que todas las demás claves y está representada por *.
Al principio, el árbol B solo contiene un nodo raíz, y el nodo raíz solo contiene la tecla centinela cuando se inicializa.
Cada clave en un nodo interno está asociada con un nodo. Todas las claves son mayores o iguales a la clave asociada con este nodo, pero más pequeñas que todas las demás claves.
Estas convenciones pueden simplificar enormemente el código.
Código
Haga clic para descargar.
Esta implementación del código presenta la clave Sentinel, y la salida del código la elimina.
El árbol B con la tecla Sentinel en el código (guarde la imagen localmente para ver, y las palabras serán más claras):
La salida del árbol B por el código (guarde la imagen localmente para ver y las palabras serán más claras):
clase pública BTree <Key extiende <key>, valor> {// niños máximos por nodo b-tree = m-1 // (debe ser uniforme y mayor que 2) static final final int m = 4; raíz de nodo privado; // raíz de la altura de int privada b-tree; // Altura del b-tree privado int n; // Número de pares de valor clave en el B-tree B-tree // Helper B-tree Tipo de datos de datos privados nodo de clase final estática {private int m; // Número de niños Entrada privada [] Niños = Nueva entrada [M]; // La matriz de niños // Crear un nodo con k niños nodo privado (int k) {m = k; }} // nodos internos: solo use la tecla y siguiente // nodos externos: solo use la tecla y valor de entrada de clase estática privada {clave comparable privada; objeto privado val; Nodo privado Siguiente; // campo auxiliar para iterar sobre las entradas de matriz Entrada pública (clave comparable, objeto val, nodo siguiente) {this.key = key; this.val = val; this.next = siguiente; }} /*** Inicializa un árbol B vacío. */ public btree () {root = new Node (0); } /*** Devuelve verdadero si esta tabla de símbolos está vacía. * @return {@code true} Si esta tabla de símbolos está vacía; {@code false} de lo contrario */ public boolean isEmpty () {return size () == 0; } /*** Devuelve el número de pares de valor clave en esta tabla de símbolos. * @return el número de pares de valor clave en esta tabla de símbolos */ public int size () {return n; } /*** Devuelve la altura de este árbol B (para la depuración). * * @return la altura de este b-tree */ public int altura () {return Height; } /*** Devuelve el valor asociado con la clave dada. * * @param clave La clave * @return El valor asociado con la clave dada si la clave está en la tabla de símbolos * y {@code null} Si la clave no está en la tabla de símbolos * @throws nullPointerException si {@code key} es {@code null} */ public value obtener (tecla clave) {if == null) {@code new nullPoin nulo"); } Búsqueda de retorno (raíz, tecla, altura); } @Suppleswarnings ("sin verificar") búsqueda de valor privado (nodo x, clave clave, int ht) {entry [] children = x.children; // nodo externo al nodo de hoja más bajo, Traverse if (ht == 0) {for (int j = 0; j <xm; j ++) {if (eq (key, niños [j] .key)) {return (valor) niños [j] .val; }}} // El nodo interno busca recursivamente la siguiente dirección más {for (int j = 0; j <xm; j ++) {if (j+1 == xm || }}} return null; } /** * Inserta el par de valores clave en la tabla de símbolos, sobrescribiendo el valor anterior * con el nuevo valor si la clave ya está en la tabla de símbolos. * Si el valor es {@code null}, esto elimina efectivamente la clave de la tabla de símbolos. * * @param clave La tecla * @param val el valor * @throws nullPointerException si {@code key} es {@code null} */ public void put (tecla clave, valor val) {if (key == null) {tirar nueva nullPointerException ("clave no debe ser null"); } Nodo u = insertar (raíz, tecla, val, altura); // El nodo derecho generado después de la división n ++; if (u == null) {return; } // necesita dividir el nodo raíz de reorganización raíz t = nuevo nodo (2); t.children [0] = nueva entrada (root.children [0] .key, null, root); T.Children [1] = nueva entrada (U.Children [0] .Key, Null, U); raíz = t; altura ++; } Insertar de nodo privado (nodo H, clave clave, valor val, int ht) {int j; Entrada t = nueva entrada (clave, val, nulo); // nodo externo nodo externo, que también es un nodo de hoja. En la parte inferior del árbol, el valor de contenido se almacena si (ht == 0) {for (j = 0; j <hm; j ++) {if (menos (key, h.children [j] .key)) {break; }}} // El nodo interno dentro del nodo es la siguiente dirección más {for (j = 0; j <hm; j ++) {if ((j+1 == hm) || menos (clave, h.children [j+1] .key)) {nodo u = insert (h.children [j ++]. Next, key, val, ht-1); if (u == null) {return null; } T.Key = U.Children [0] .Key; t.next = u; romper; }}} para (int i = hm; i> j; i--) {H.Children [i] = H.Children [i-1]; } h.children [j] = t; H.M ++; if (hm <m) {return null; } else {// Split Node Return Split (H); }} // Nodo dividido en la mitad del nodo privado (nodo h) {nodo t = nuevo nodo (m/2); hm = m/2; para (int j = 0; j <m/2; j ++) {t.children [j] = h.children [m/2+j]; } return t; } /*** Devuelve una representación de cadena de este árbol B (para la depuración). * * @return una representación de cadena de este árbol B. */ public string toString () {return toString (root, altura, ") +"/ n "; } private String toString (nodo h, int ht, string sandent) {stringBuilder s = new StringBuilder (); Entrada [] Niños = H.Children; if (ht == 0) {for (int j = 0; j <hm; j ++) {s.append (indent + niños [j] .key + "" + niños [j] .val + "/n"); }} else {for (int j = 0; j <hm; j ++) {if (j> 0) {s.append (sandent + "(" + niños [j] .key + ")/n"); } s.append (toString (niños [j] .next, ht-1, sangría + "")); }} return s.ToString (); } // Funciones de comparación: haga comparable en lugar de clave para evitar moldes privados menos (K1 comparable, K2 comparable) {return k1.compareto (k2) <0; } eq booleano privado (K1 comparable, comparable K2) {return k1.compareto (k2) == 0; } /*** Unidad prueba el tipo de datos {@code btree}. * * @param args los argumentos de línea de comandos */ public static void main (string [] args) {btree <string, string> st = new btree <string, string> (); St.put ("www.cs.princeton.edu", "128.112.136.12"); St.put ("www.cs.princeton.edu", "128.112.136.11"); St.put ("www.princeton.edu", "128.112.128.15"); St.put ("www.yale.edu", "130.132.143.21"); St.put ("www.simpsons.com", "209.052.165.60"); St.put ("www.apple.com", "17.112.152.32"); St.put ("www.amazon.com", "207.171.182.16"); St.put ("www.ebay.com", "66.135.192.87"); St.put ("www.cnn.com", "64.236.16.20"); St.put ("www.google.com", "216.239.41.99"); St.put ("www.nytimes.com", "199.239.136.200"); St.put ("www.microsoft.com", "207.126.99.140"); St.put ("www.dell.com", "143.166.224.230"); St.put ("www.slashdot.org", "66.35.250.151"); St.put ("www.espn.com", "199.181.135.201"); St.put ("www.weather.com", "63.111.66.11"); St.put ("www.yahoo.com", "216.109.118.65"); System.out.println ("cs.princeton.edu:" + St.get ("www.cs.princeton.edu")); System.out.println ("hardvardsucks.com:" + St.get ("www.harvardsucks.com")); System.out.println ("Simpsons.com:" + St.get ("www.simpsons.com")); System.out.println ("Apple.com:" + St.get ("www.apple.com")); System.out.println ("eBay.com:" + St.get ("www.ebay.com")); System.out.println ("Dell.com:" + St.get ("www.dell.com")); System.out.println ("Tamaño:" + St.Size ()); System.out.println ("Altura:" + St.Height ()); System.out.println (ST); System.out.println (); }} Producción:
Cs. Princeton.edu: 128.112.136.12
hardvardsks.com: nulo
Simpsons.com: 209.052.165.60
Apple.com: 17.112.152.32
eBay.com: 66.135.192.87
Dell.com: 143.166.224.230
Tamaño: 17
Altura: 2
www.amazon.com 207.171.182.16
www.apple.com 17.112.152.32
www.cnn.com 64.236.16.20
(www.cs.princeton.edu)
www.cs.princeton.edu 128.112.136.12
www.cs.princeton.edu 128.112.136.11
www.dell.com 143.166.224.230
(www.ebay.com)
www.ebay.com 66.135.192.87
www.espn.com 199.181.135.201
www.google.com 216.239.41.99
(www.microsoft.com)
www.microsoft.com 207.126.99.140
www.nytimes.com 199.239.136.200
(www.princeton.edu)
www.princeton.edu 128.112.128.15
www.simpsons.com 209.052.165.60
(www.slashdot.org)
www.slashdot.org 66.35.250.151
www.weather.com 63.111.66.11
(www.yahoo.com)
www.yahoo.com 216.109.118.65
www.yale.edu 130.132.143.21
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.