definição
Na ciência da computação, uma árvore B é uma árvore de auto-equilíbrio que mantém os dados em ordem. Essa estrutura de dados permite que a pesquisa de dados, acesso seqüencial, inserção de dados e operações de exclusão seja concluído em tempo logarítmico.
Por que apresentar B-Tree?
Primeiro de tudo, incluindo a árvore vermelha e preta que introduzimos anteriormente, é uma árvore de pesquisa interna que armazena a entrada na memória .
B-Tree é uma extensão do algoritmo de árvore de equilíbrio anterior. Ele suporta pesquisas externas por tabelas de símbolos salvas em disco ou rede . Esses arquivos podem ser muito maiores que a entrada que consideramos antes (difícil de armazenar na memória).
Como o conteúdo é armazenado no disco, a E/S do disco leia e escreve com muita frequência devido à grande profundidade da árvore (a taxa de leitura e gravação do disco é limitada), o que leva à eficiência da consulta ineficiente.
Então é naturalmente importante reduzir a profundidade da árvore. Portanto, introduzimos a árvore de pesquisa de múltiplas vias B-Tree.
Características
Cada nó na árvore contém na maioria das crianças (m> = 2);
Exceto pelo nó raiz e nó foliar, cada nó possui pelo menos crianças [teto (m/2)] (onde o teto (x) é uma função que leva o limite superior);
Se o nó raiz não for um nó foliar, haverá pelo menos 2 filhos (caso especial: não há nó raiz para crianças, ou seja, o nó da raiz é um nó foliar e toda a árvore possui apenas um nó raiz);
Todos os nós da folha aparecem na mesma camada (camada inferior) e os nós da folha são nós externos, que salvam o conteúdo, a saber, chave e valor .
Outros nós são nós internos, que salvam o índice, a saber e a seguir .
Palavras-chave dos nós internos: k [1], k [2],…, k [m-1]; e k [i] <k [i+1];
Ponteiros ao lado do nó de conteúdo: P [1], P [2],…, P [M]; onde p [1] aponta para uma subárvore com a palavra-chave menor que k [1], p [m] aponta para uma subárvore com a palavra-chave maior que k [m-1] e outros P [i] apontam para uma subárvore com a palavra-chave (k [i-1], k [i]);
Por exemplo: (M = 3)
Encontre e insira
Por conveniência, uma chave Sentinel especial é usada aqui, que é menor que todas as outras teclas e é representada por *.
No início, a árvore B contém apenas um nó raiz, e o nó raiz contém apenas a tecla Sentinel quando inicializada.
Cada chave em um nó interno está associada a um nó. Todas as teclas são maiores ou iguais à chave associada a este nó, mas menores que todas as outras teclas.
Essas convenções podem simplificar bastante o código.
Código
Clique para baixar.
Esta implementação de código apresenta a chave Sentinel e a saída de código a elimina.
A árvore B com a chave Sentinel no código (salve a imagem localmente para visualizar, e as palavras serão mais claras):
A saída da árvore B pelo código (salve a imagem localmente para visualizar, e as palavras serão mais claras):
classe pública Btree <Key estende comparável <Key>, valor> {// MAX CRIANÇAS POR NO NOTE B-TREE = M-1 // (deve ser uniforme e maior que 2) private estático final int m = 4; raiz de nós privados; // raiz da altura privada int b-tere; // altura do B-Tree privado int n; // Número de pares de valor-chave no nó B-Tree B-Tree // Helper B-Tree Type de dados privados da classe estática {private int m; // Número de crianças de entrada privada [] crianças = nova entrada [M]; // A matriz de crianças // cria um nó com K Children Private Node (int k) {m = k; }} // nós internos: use apenas a tecla e a próxima // nós externos: use apenas a chave e valor da classe estática privada {key comparável privado; objeto privado val; nó privado a seguir; // Campo auxiliar para iterar as entradas da matriz de entrada pública (chave comparável, objeto val, nó a seguir) {this.key = key; this.val = val; this.Next = Next; }} /*** inicializa uma árvore B vazia. */ public btree () {root = new Node (0); } /*** Retorna true se esta tabela de símbolos estiver vazia. * @return {@code true} Se esta tabela de símbolos estiver vazia; {@code false} caso contrário */ public boolean isEmpty () {return size () == 0; } /*** Retorna o número de pares de valor-chave nesta tabela de símbolos. * @return o número de pares de valor-chave nesta tabela de símbolos */ public int size () {return n; } /*** Retorna a altura desta árvore B (para depuração). * * @RETURN A altura desta árvore B */ public int Hight () {return Hight; } /*** Retorna o valor associado à chave fornecida. * * @Param Key A chave * @RETURN O valor associado à chave fornecida se a chave estiver na tabela de símbolos * e {@code null} se a chave não estiver na tabela de símbolos * @throws nullPointerException se {@code key} é {@code null} */ public Valor get (key) (@cod nulo"); } retornar pesquisa (raiz, chave, altura); } @Suppresswarnings ("desmarcado") Pesquisa de valor privada (nó x, chave de chave, int ht) {entradas [] filhos = x.children; // nó externo para o nó foliar mais baixo, travesse if (ht == 0) {for (int j = 0; j <xm; j ++) {if (eq (chave, filhos [j] .Key)) {return (value) crianças [j] .Val; }}} // O nó interno pesquisa recursivamente o próximo endereço {for (int j = 0; j <xm; j ++) {if (j+1 == xm || menos (chave, filhos [j+1] .Key)) {Return Search (j] .next, chave, ht-1); }}} retornar nulo; } /** * Insira o par de valores-chave na tabela de símbolos, substituindo o valor antigo * com o novo valor se a chave já estiver na tabela de símbolos. * Se o valor for {@code null}, isso excluirá efetivamente a chave da tabela de símbolos. * * @param chave a chave * @param val o valor * @throws nullPointerException se {@code key} é {@code null} */ public void put (chave de chave, value val) {if (key == null) {lança new nullPonterException ("key não deve ser null"); } Nó u = insert (root, chave, val, altura); // o nó direito gerado após divisão N ++; if (u == null) {return; } // precisa dividir o nó raiz da reorganização raiz t = novo nó (2); t.Children [0] = nova entrada (root.Children [0] .Key, NULL, ROOT); T.Children [1] = nova entrada (U.Children [0] .Key, Null, U); raiz = t; altura ++; } Inserção privada do nó (nó H, chave de chave, value val, int ht) {int j; Entrada t = nova entrada (chave, val, nula); // Nó externo Nó externo, que também é um nó foliar. Na parte inferior da árvore, o valor do conteúdo é armazenado se (ht == 0) {for (j = 0; j <hm; j ++) {if (menos (chave, h.Children [j] .Key)) {break; }}} // O nó interno dentro do nó é o próximo endereço {for (j = 0; j <hm; j ++) {if ((j+1 == hm) || menos (key, h.Children [j+1] .Key) {node u = insert (h.Children [j ++]. if (u == null) {return null; } t.Key = U.Children [0] .Key; t.next = u; quebrar; }}} 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 {// Nó dividido Return Split (h); }} // O nó dividido em meio nó privado dividido (nó h) {nó t = novo nó (m/2); hm = m/2; for (int j = 0; j <m/2; j ++) {t.children [j] = h.children [m/2+j]; } retornar t; } /*** Retorna uma representação de string deste B-Tree (para depuração). * * @return Uma representação de string desta árvore B. */ public string tostring () {return toString (raiz, altura, "") + "/ n"; } private string tostring (nó h, int ht, string indent) {stringbuilder s = new stringbuilder (); Entrada [] crianças = H.Children; if (ht == 0) {for (int j = 0; j <hm; j ++) {s.append (indent + filhos [j] .key + "" + filhos [j] .val + "/n"); }} else {for (int j = 0; j <hm; j ++) {if (j> 0) {s.append (indent + "(" + filhos [j] .Key + ")/n"); } S.Append (ToString (filhos [j] .next, ht-1, indent + "")); }} return s.toString (); } // Funções de comparação - tornem comparáveis em vez de chave para evitar castes menos booleanos privados (K1 comparável, K2 comparável) {return k1.compareto (k2) <0; } eq booleano privado (comparável K1, comparável k2) {return k1.compareto (k2) == 0; } /*** A unidade testa o tipo de dados {@code btree}. * * @param args os argumentos da linha de comando */ 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 ("Tamanho:" + St.Size ()); System.out.println ("Hight:" + St.Height ()); System.out.println (ST); System.out.println (); }} Saída:
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
Tamanho: 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
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.