意味
コンピューターサイエンスでは、Bツリーは、データを整頓する自己バランスの木です。このデータ構造により、データの検索、順次アクセス、データの挿入、操作の削除を対数時間で完了できます。
なぜBツリーを紹介するのですか？
まず、前に導入した赤と黒の木を含む、入力をメモリに保存する内部検索ツリーです。
Bツリーは、以前のバランスツリーアルゴリズムの拡張です。ディスクまたはネットワークに保存されたシンボルテーブルの外部検索をサポートします。これらのファイルは、以前に検討した入力よりもはるかに大きい場合があります（メモリに保存するのは難しい）。
コンテンツはディスクに保存されているため、ディスクI/Oは、ツリーの深さが大きいため（ディスクの読み取りレートが限られているため）、頻繁に読み書きされ、書き込みが頻繁に記載されています。
その後、木の深さを減らすことが自然に重要です。したがって、bツリー、複数道路検索ツリーを紹介します。
特徴
ツリー内の各ノードには、ほとんどのMの子供が含まれています（m> = 2）。
ルートノードとリーフノードを除き、各ノードには少なくとも[ceil（m/2）]]子供（CEIL（x）は上限をとる関数です）。
ルートノードがリーフノードではない場合、少なくとも2人の子供がいます（特別なケース：子供用のルートノードはありません。つまり、ルートノードはリーフノードであり、ツリー全体には1つのルートノードしかありません）。
すべてのリーフノードは同じレイヤー（下層）に表示され、葉のノードは外部ノードであり、コンテンツ、つまりキーと値を保存します。
他のノードは、インデックスを保存する内部ノード、つまりキーと次のノードです。
内部ノードのキーワード：k [1]、k [2]、…、k [m-1];およびk [i] <k [i+1];
コンテンツノードの横にあるポインター：P [1]、P [2]、…、P [M];ここで、p [1]がキーワードをk [1]未満でサブツリーを指し、p [m]はキーワードをk [m-1]よりも大きいサブツリーに指し、他のp [i]はキーワード（k [i-1]、k [i]）を使用してサブツリーを指します。
例：（m = 3）
見つけて挿入します
便利なため、ここでは特別なセンチネルのキーが使用されます。これは他のすべてのキーよりも小さく、 *で表されます。
最初は、Bツリーには1つのルートノードのみが含まれ、ルートノードには初期化されたときにセンチネルキーのみが含まれます。
内部ノードの各キーは、ノードに関連付けられています。すべてのキーは、このノードに関連付けられているキー以上ですが、他のすべてのキーよりも小さくなっています。
これらの規則は、コードを大幅に簡素化できます。
コード
クリックしてダウンロードします。
このコードの実装により、センチネルキーが導入され、コード出力が排除されます。
コードにSentinelキーを備えたBツリー（画像を局所的に保存して表示すると、単語がより明確になります）：
コードによるBツリー出力（画像を局所的に保存して表示すると、単語がより明確になります）：
パブリッククラスbtree <keyは比較可能な<key>、value> {// b-tree node = m-1 //（2を超えている必要があります）private static final int m = 4;プライベートノードルート。 // Bツリープライベートの高さのルート。 // B-Tree Private Int nの高さ; // B-Treeのキー値ペアの数//ヘルパーB-Treeノードデータ型プライベート静的最終クラスノード{private int m; //子供の数のプライベートエントリ[]子供= new entry [m]; //子供の配列// k子供とノードを作成するプライベートノード（int k）{m = k; }} //内部ノード：キーと次の//外部ノードのみを使用します：キーと値のみを使用します。プライベートオブジェクトval;次のプライベートノード。 //ヘルパーフィールドアレイエントリを繰り返しますthis.val = val; this.next = next; }} /***空のbツリーを初期化します。 */ public btree（）{root = new Node（0）; } /***このシンボルテーブルが空の場合、trueを返します。 * @return {@code true}このシンボルテーブルが空の場合。 {@code false}それ以外の場合 */ public boolean isempty（）{return size（）== 0; } /***このシンボルテーブルのキー価値ペアの数を返します。 * @returnこのシンボルテーブルのキー値ペアの数 */ public int size（）{return n; } /***このBツリーの高さ（デバッグ用）を返します。 * * @returnこのb-treeの高さ */ public int height（）{return height; } /***指定されたキーに関連付けられた値を返します。 * * @paramキーキー * @ @return keyがシンボルテーブルにある場合、指定されたキーに関連付けられている値 *および{@code null}キーがシンボルテーブルにない場合 * @throws nullpointerexception if {@code null} is {@code null} */ public Value get（key key）{key = = null "key（key key） } return search（root、key、height）; } @suppresswarnings（ "Unchecked"）プライベートバリュー検索（Node X、Key Key、int HT）{entry [] children = x.children; //外部ノード最低葉のノードへの外部ノード、トラバースif（ht == 0）{for（int j = 0; j <xm; j ++）{if（eq（key、children [j] .key））{return（value）children [j] .val; }}} //内部ノードは次のアドレスを再帰的に検索します。 }}} nullを返します。 } /** *キー値ペアをシンボルテーブルに挿入し、キーが既にシンボルテーブルにある場合、古い値 *を新しい値に上書きします。 *値が{@code null}の場合、これによりシンボルテーブルからキーが効果的に削除されます。 * * @param key the key * @param val the value * @throws nullpointerexception if {@code key} is {@code null} */ public void put（key key、value val）{if（key == null）{throw new Nullpointerexception（ "keyはnull"）; } node u = insert（root、key、val、height）; // n ++を分割した後に生成された右ノード。 if（u == null）{return; } //ルート再編成ルートノードt = newノード（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;高さ++; }プライベートノード挿入（ノードH、キーキー、値val、int ht）{int j;エントリT = new Entry（key、val、null）; //外部ノード外部ノード。これもリーフノードです。ツリーの下部では、コンテンツ値が保存されます（ht == 0）{for（j = 0; j <hm; j ++）{if（less（key、h.children [j] .key））{break; }}} //ノード内の内部ノードは次のアドレスです{for（j = 0; j <hm; j ++）{if（（j+1 == hm）|| less（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;壊す; }}} for（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）; }} //ハーフプライベートノードスプリット（ノードh）{node t = new Node（m/2）; hm = m/2; for（int j = 0; j <m/2; j ++）{t.children [j] = h.children [m/2+j]; } return t; } /***このBツリーの文字列表現を返します（デバッグ用）。 * * @returnこのBツリーの文字列表現。 */ public string toString（）{returting（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 <hm; j ++）{s.append（indent + children [j] .key + "" + children [j] .val + "/n"）; }} else {for（int j = 0; j <hm; j ++）{if（j> 0）{s.append（indent + "（" + children [j] .key + "）/n"）; } s.Append（toString（children [j] .next、ht-1、indent + ""））; }} s.toString（）;を返します。 } //比較関数 - プライベートブールの少ないキャストを避けるためにキーの代わりに比較可能になります（比較可能なk1、比較可能なk2）{return k1.compareto（k2）<0; } private boolean eq（比較可能なK1、比較可能なK2）{return K1.comPareto（K2）== 0; } /***ユニットテスト{@code btree}データ型をテストします。 * * @param argsコマンドライン引数 */ 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.harvarducks.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（ "size：" + st.size（））; system.out.println（ "height：" + st.height（））; System.out.println（st）; System.out.println（）; }}出力：
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
サイズ：17
高さ：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
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。