English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
definizione
In informatica, l'albero B (inglese: B-tree) è un albero auto-bilanciato che può mantenere i dati ordinati. Questa struttura dati permette di completare le operazioni di ricerca dei dati, accesso sequenziale, inserimento e cancellazione in tempo logaritmico.
Perché introdurre l'albero B?
Prima di tutto, inclusi i red-black tree che abbiamo introdotto prima, sono memorizzatimemoriadi un tipoalbero di ricerca interno.
mentre l'albero B è un'estensione dell'algoritmo di albero bilanciato precedente, che supporta la conservazionedisco o retesimboliricerca esternaQuesti file potrebbero essere molto più grandi di quelli che abbiamo considerato prima (difficili da memorizzare in memoria).
Se il contenuto è salvato su disco, naturalmente sarà causato da una profondità di albero eccessiva che causa una lettura e scrittura I/O su disco eccessivamente frequente (la velocità di lettura e scrittura del disco è limitata), portando a una bassa efficienza di query.
Quindi ridurre la profondità dell'albero è naturalmente molto importante. Pertanto, abbiamo introdotto l'albero B, l'albero di ricerca a multipli vie.
Caratteristiche
Ogni nodo dell'albero può avere al massimo m figli (m>=2);
Oltre al nodo radice e ai nodi foglia, ogni altro nodo ha almeno [ceil(m / 2)] figli (dove ceil(x) è una funzione che prende il valore superiore);
Se il nodo radice non è un nodo foglia, allora ha almeno 2 figli (caso speciale: nodo radice senza figli, ovvero il nodo radice è un nodo foglia, l'albero ha solo un nodo radice);
Tutti i nodi foglia appaiono nello stesso livello (il livello più basso),I nodi foglia sono nodi esterni, che salvano il contenuto, ovvero key e value.
Altri nodi sono nodi interni, che salvano l'indice, ovvero key e next.
Chiavi dei nodi interni key: K[1], K[2], …, K[M-1]; e K[i] < K[i+1];
Puntatori ai nodi di contenuto next: P[1], P[2], …, P[M]; dove P[1] punta all'albero figlio con chiavi minori di K[1], P[M] punta all'albero figlio con chiavi maggiori di K[M-1], gli altri P[i] puntano agli alberi figli con chiavi appartenenti a (K[i-1], K[i]);
Ad esempio: (M=3)
Ricerca e inserimento
Per facilità, è stato utilizzato una chiave sentinella speciale, che è minore di tutte le altre chiavi, rappresentata con *.
All'inizio l'albero B contiene solo un nodo radice, e il nodo radice contiene solo la chiave sentinella durante l'inizializzazione.
Ogni chiave all'interno del nodo interno è associata a un nodo, e i sottoalberi radicate in questo nodo, tutte le chiavi sono maggiori o uguali alla chiave associata a questo nodo, ma minori di tutte le altre chiavi.
Queste convenzioni possono semplificare notevolmente il codice.
Codice
Clicca per scaricare.
Questo codice introduce la chiave sentinella, ma l'output del codice la elimina.
Albero B con chiave sentinella nel codice (salva l'immagine localmente per vedere meglio i testi):
Albero B generato dal codice (salva l'immagine localmente per vedere meglio i testi):
public class BTree<Key extends Comparable<Key>, Value>
{
// numero massimo di figli per un nodo del B-treno = M-1
// (deve essere anche e maggiore di 2)
private static final int M = 4;
private Node root; // radice del B-treno
private int height; // altezza del B-treno
private int n; // numero di coppie chiave-valore nel B-treno
// helper B-tree node data type
private static final class Node
{
private int m; // number of children
private Entry[] children = new Entry[M]; // the array of children
// create a node with k children
private Node(int k)
{
m = k;
}
}
// internal nodes: only use key and next
// external nodes: only use key and value
private static class Entry
{
private Comparable key;
private Object val;
private Node next; // helper field to iterate over array entries
public Entry(Comparable key, Object val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
/**
* Initializes an empty B-tree.
*/
public BTree()
{
root = new Node(0);
}
/**
* Returns true if this symbol table is empty.
* @return {@code true} if this symbol table is empty; {@code false} otherwise
*/
public boolean isEmpty()
{
return size() == 0;
}
/**
* Returns the number of key-value pairs in this symbol table.
* @return the number of key-value pairs in this symbol table
*/
public int size()
{
return n;
}
/**
* Restituisce l'altezza di questo albero B (per debug).
*
* @return l'altezza di questo albero B
*/
public int height()
{
return height;
}
/**
* Restituisce il valore associato alla chiave fornita.
*
* @param key la chiave
* @return il valore associato alla chiave fornita se la chiave è nella tabella dei simboli
* e {@code null} se la chiave non è nella tabella dei simboli
* @throws NullPointerException se {@code key} è {@code null}
*/
public Value get(Key key)
{
if (key == null)
{
throw new NullPointerException("key must not be null");
}
return search(root, key, height);
}
@SuppressWarnings("unchecked")
private Value search(Node x, Key key, int ht)
{
Entry[] children = x.children;
// nodo esterno al livello più basso dei nodi foglia, esplora
if (ht == 0)
{
for (int j = 0; j < x.m; j++)
{
if (eq(key, children[j].key))
{
return (Value) children[j].val;
}
}
}
// nodo interno ricerca ricorsiva dell'indirizzo next
else
{
for (int j = 0; j < x.m; j++)
{
if (j+1 == x.m || less(key, children[j+1].key))
{
return search(children[j].next, key, ht-1);
}
}
}
return null;
}
/**
* Inserisce la coppia chiave-valore nella tabella dei simboli, sovrascrivendo il valore vecchio
* con il nuovo valore se la chiave è già nella tabella dei simboli.
* Se il valore è {@code null}, questo elimina effettivamente la chiave dalla tabella dei simboli.
*
* @param key la chiave
* @param val il valore
* @throws NullPointerException se {@code key} è {@code null}
*/
public void put(Key key, Value val)
{
if (key == null)
{
throw new NullPointerException("key must not be null");
}
Node u = insert(root, key, val, height); // nodo destro generato dopo la scissione
n++;
if (u == null)
{
return;
}
// need to split root重组root
Node t = new Node(2);
t.children[0] = new Entry(root.children[0].key, null, root);
t.children[1] = new Entry(u.children[0].key, null, u);
root = t;
height++;
}
private Node insert(Node h, Key key, Value val, int ht)
{
int j;
Entry t = new Entry(key, val, null);
// external node nodo esterno, anche foglia, situato al livello più basso dell'albero, contiene valori
if (ht == 0)
{
for (j = 0; j < h.m; j++)
{
if (less(key, h.children[j].key))
{
break;
}
}
}
// internal node nodo interno, contiene indirizzi
else
{
for (j = 0; j < h.m; j++)
{
if ((j+1 == h.m) || less(key, h.children[j+1].key))
{
Node u = insert(h.children[j++].next, key, val, ht-1);
if (u == null)
{
return null;
}
t.key = u.children[0].key;
t.next = u;
break;
}
}
}
for (int i = h.m; i > j; i--)
{
h.children[i] = h.children[i-1];
}
h.children[j] = t;
h.m++;
if (h.m < M)
{
return null;
}
else
{ // spezza il nodo
return split(h);
}
}
// spezza il nodo a metà
private Node split(Node h)
{
Node t = new Node(M/2);
h.m = M/2;
for (int j = 0; j < M/2; j++)
{
t.children[j] = h.children[M/2+j];
}
return t;
}
/**
* Restituisce una rappresentazione stringa di questo B-tree (per debug).
*
* @return una rappresentazione stringa di questo B-tree.
*/
public String toString()
{
return toString(root, height, "") + "\n";
}
private String toString(Node h, int ht, String indent)
{
StringBuilder s = new StringBuilder();
Entry[] children = h.children;
if (ht == 0)
{
for (int j = 0; j < h.m; j++)
{
s.append(indent + children[j].key + " " + children[j].val + "\n");
}
}
else
{
for (int j = 0; j < h.m; j++)
{
if (j > 0)
{
s.append(indent + "(" + children[j].key + ")\n");
}
s.append(toString(children[j].next, ht-1, indent + " "));
}
}
return s.toString();
}
// funzioni di confronto - rendi Comparable invece di Key per evitare cast
private boolean less(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) < 0;
}
private boolean eq(Comparable k1, Comparable k2)
{
return k1.compareTo(k2) == 0;
}
/**
* Unit tests the {@code BTree} data type.
*
* @param args the command-line arguments
*/
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();
System.out.println("dimensione: " + st.size());
System.out.println("altezza: " + st.height());
System.out.println(st);
System.out.println();
}
}
Output:
cs.princeton.edu: 128.112.136.12
hardvardsucks.com: null
simpsons.com: 209.052.165.60
apple.com: 17.112.152.32
ebay.com: 66.135.192.87
dell.com: 143.166.224.230
dimensione: 17
altezza: 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
Questo è tutto il contenuto dell'articolo, speriamo che sia utile per la tua apprendimento e che tu sostenga fortemente il tutorial urla.
Dichiarazione: il contenuto di questo articolo è stato raccolto da Internet, di proprietà del rispettivo autore, il contenuto è stato caricato autonomamente dagli utenti di Internet, il sito web non detiene i diritti di proprietà, non è stato editato manualmente e non assume responsabilità legali correlate. Se trovi contenuti sospetti di violazione del copyright, ti preghiamo di inviare una e-mail a notice#oldtoolbag.com (al momento dell'invio dell'e-mail, sostituisci # con @) per segnalare il problema e fornire prove pertinenti. Una volta verificata, il sito eliminerà immediatamente il contenuto sospetto di violazione del copyright.