Mysql-index-BTree 型 [簡略化]

私は、B ツリー、B ツリー、B+ ツリー、B* ツリー (なぜエマはまだ 4 を持っているのですか? 彼女はほとんど混乱しています)、

など、インターネット上で B-TREE についての要約をたくさん読みました。とても刺激的で素晴らしいですが、長すぎる文章は気が遠くなります。概要の簡易版を作成し、簡単かつモバイルな方法で紹介し、それらの違いについて話しましょう。
1. B-tree

Binary Treeは二分木です。 (K、h、n の式については、ここでは説明しません。興味があれば、自分で検索してみてください...)

(1) すべての非リーフ ノード には、最大 2 つのノードがありますSons(Left および Right);

(2) すべてのノードは キーワードを格納します (3) 非リーフ ノードの左ポインタは、キーワードよりも小さいサブツリーの場合、右ポインタはそのキーワードよりも大きいサブツリーを指します (簡単に言えば、

の左側はそれ自体よりも小さく、右側はそれ自体よりも大きいです

)。

Bツリー

II. B-Tree

Balance Binary Tree (Balance Binary Tree) -- AVL ツリー [ここでの B は実際にはバランスを意味します~]

(1) ルートノードの左側のサブツリーと右側のサブツリーのの深さは最大で 1 異なります (これにより、上の図の右側の極端な現象は発生しません)
。

(2 ) ルート ノードの左のサブツリーと右のサブツリーは両方とも バランスの取れた二分木 です。

(3) すべてのノードにはストレージがありますキーワード; 挿入されたシーケンスが何であっても、バイナリツリーがの各ノードのバランス係数は 1 より大きくなりません。
により、ツリーの深さが確実に最も浅くなります

。そのため、比較の数が減り、時間の複雑さが軽減されます

写真Bツリー

Three.B+Tree

B+ の検索は基本的に B-tree の検索と同じです。違いは、B+ ツリーは葉ノードにのみヒットすることです (B-tree は葉以外のノードにもヒットする可能性があります)

(1)すべてのキーワードはリーフ ノードのリンク リスト (密なインデックス) に表示され、リンク リスト内のキーはたまたま順番に並んでいます ( ルート ノードのみがキーを格納し、ツリーの最後に値があります) )

(2) 非リーフノードはリーフノードのインデックス(スパースインデックス)に相当し、リーフノードは(キーワード)データを格納するデータ層に相当します。 (非ルートノードは、実際にはルートノードを指すインデックスを格納します)

(3) 最初の 2 点のため、非リーフノードにデータを格納することは不可能です。 (B-の3番目の違い)
(4) ルートノードには水平方向のチェーンポインタもあります(手掛かりを素早くたどるのに便利です。このポインタがないと、次の値が隣接する近隣ノードであっても) 、それを取得するには走り回らなければなりません)

一般的に使用するインデックス結果、または通常参照するB-TREE構造は、ほとんどがB+構造を参照していることに注意してください~~

写真B + 木

Four.B *ツリー は、
B+ ツリーの変形です、

(1)B+ツリーの非ルートノードと非リーフノードの兄弟へのポインタを追加します。[上記のB+の項目4を比較し、非ルートノードに水平リンクリストも追加します]

写真B * 木

5.概要:

B ツリー: バイナリ ツリー、

各ノードは 1 つのキーワードのみを格納します。キーワードが等しい場合はヒットし、小さい場合は左のノードに移動します。それが大きい場合は、右のノードに移動します (ただし、B ツリーは複数の挿入と削除の後、異なる構造になる可能性があります )。このため、バランスのとれたバイナリ ツリーは、バランシング アルゴリズムを追加した後に生成されます。 、B ツリーとも呼ばれます

B ツリー: in B ツリーに基づいて、バランスの取れたアルゴリズムとマルチパス検索ツリーが追加されます、

1各ノードは M/2 から M 個のキーワードを格納します。

2. 非リーフ ノードは、単語範囲の子ノードを格納します。すべてのキーワードはツリー全体に 1 回だけ表示されます。

4. リーフ ノードと非リーフ ノードの両方がヒットする可能性があります (データが保存されているかどうか) ;

B+ツリー: Bツリーに基づいて、

1. リンクされたリストポインタをリーフノードに追加します。 2.すべてキー 単語はすべてリーフ ノードに出現します。

3. 非リーフ ノードは、常にリーフ ノードにヒットします。 B* ツリー:

B+ ツリーに基づいて、

非リーフ ノードにリンク リスト ポインター

も追加され、ノードの最小使用率が 1/2 から 2/3 に増加します。

質問: B* の方が効率的ですが、なぜ b* ツリーの使用率が低いと思いますか? ????それともどこで役に立ちますか？ ? たぶん私はまだ少ししか見ていないかもしれません。 。何かを知っている子供たちの靴はお互いから学ぶことができます、アドバイスをください、よろしくお願いします~ 答え: 最近

というファイルシステムがあることを知りました

Reiser4

はこれを使用しているようです構造。著者

ハンス ライザーさん、妻に寝取られたため、妻を殺し、刑務所に入り、それがプロジェクトの進行に直接影響を及ぼしました。 。 。

はじめに:

Linux ファイルシステム ReiserFS 著者の Hans Reiser が妻を殺害した罪で 15 年の懲役刑を言い渡された後も、ReiserFS の開発は停止していませんが、メインの Linux ブランチにはまだマージされていません。少数の開発者グループが、ReiserFS の 4 番目のバージョン (略して Reiser4) の開発を続けており、先月、Linux 3.5.4 カーネルをサポートする新しいバージョンをリリースしました。 上記は Mysql-index-BTree タイプ [簡略化] の内容です。さらに関連する内容については、PHP 中国語 Web サイト (www.php.cn) に注目してください。