B ツリーは一般的なデータ構造です。彼と一緒にB+ツリーがあります。 ここで、概念を明確にする必要があります。 B ツリー、B ツリー、B+ ツリーの違いは何ですか?彼らの関係は何ですか? 実際のところ、データ構造には B ツリーと B+ ツリーの 2 種類しかありません。 B ツリーは B ツリーとも呼ばれることがあります。これらは同じものです。 B ツリーの中央にある「-」は「マイナス記号」ではなくハイフンであることに注意してください。英語では B-Tree であり、中国語では B-tree と翻訳されます。翻訳者によってはハイフン「-」を含めることを好むため、B-tree となり、一部の読者は B-tree を B-minus tree と誤読します。 B ツリーを紹介する前に、まず重要な概念である「順序」について見てみましょう。 ツリーの順序は、ツリー内の各ノードの子ノードの最大数です。つまり、一部のノードに 2 つの子ノードがあり、一部のノードに 4 つの子ノードがあり、子ノードの最大数が 5 の場合、ツリーの順序は 5 になります。 この観点から見ると、二分木の次数は 2 です。 次に、B ツリーの主な特性を紹介します。 B ツリーの次数は m であると仮定します。 m 次 B ツリーは、空のツリーか、次のプロパティを持つツリーのいずれかです。 1. 各ノードには最大 m 個の子ノードがあります。少なくとも m/2 (切り上げ) 個のノードがあります。または、次のように表現することもできます: m/2 <= 子ノードの数 <= m。ただし、ルート ノードは例外です。ルート ノードには少なくとも 2 つの子ノードを含めることができます。 2. 各ノードの子ノードの数は、ノードに格納されているキーワードの数より 1 多くなります。つまり、ノードに k 個のキーワードが格納されている場合、ノードには k + 1 個の子ノード (サブツリー) が存在することになります。 3. 各ノード内のk個のキーワードは小さいものから大きいものの順に並べられ、k1、k2、k3、…kkとして記録されます。すると、ノードには p0、p1、p2、... pk と表記される k+1 個のポインターが存在します。さらに、次の図に示すように、p3 が指す子ノード内のすべての要素は k3 より大きく、k4 より小さくなります。これも比較的理解しやすく、覚えやすいです。各ポインタ p は、キーワード k 間のギャップに正確に配置されます。したがって、ギャップのポインタが指す子ノードの要素の値は、当然、ポインタの左側の要素よりも大きく、ポインタの右側の要素よりも小さくなります。 4. B ツリーは厳密にバランスのとれた検索ツリーであり、左と右のサブツリーの高さは等しくなります。リーフ ノードは同じレイヤーにあり、空のノードで表すことができます。 B ツリーの例: 要約する 以上がこの記事の全内容です。この記事の内容が皆様の勉強や仕事に何らかの参考学習価値をもたらすことを願います。123WORDPRESS.COM をご愛顧いただき、誠にありがとうございます。これについてもっと知りたい場合は、次のリンクをご覧ください。 以下もご興味があるかもしれません:
|
<<: ローカルストレージにブール型の値を保存する際の落とし穴を解決する
この間、プロジェクトに取り組んでいるときに、データ間の接続が非常に複雑なモジュールに遭遇しました。テ...
a.htmとb.htmの2つのファイルがあります。同じディレクトリ内のa.htmの内容は次のとおりで...
最初の方法: Junge のワンクリック スクリプトを使用して、LNMP 環境で MYSQL データ...
最近、JS の正規表現マッチングの落とし穴を発見したのですが、その時はあまりにも奇妙だったので、何か...
1. /etc/passwdファイル内のデフォルトシェルが/sbin/nologinではないユーザー...
1. インラインスタイル仮想DOMにインラインスタイルを追加するには、式を使用してスタイルオブジェク...
メソッドが定義されているクラスに応じて、現在のクラスへの静的参照を取得するには、self:: または...
この記事の例では、衝突検出を実装するためのjsの具体的なコードを参考までに共有しています。具体的な内...
1. MySQLをインストールするこの記事はAPT経由でインストールされており、インストールされてい...
1. データベースの文字セットを確認するデータベースの文字セットは、Linux で設定された環境変数...
前提条件: Percona 5.6 バージョン、トランザクション分離レベルは RR mysql>...
このキー属性の機能は何ですか?まずは公式の説明を見てみましょう。 kekey 属性は主に、新しいノー...
MySQL パスワードを忘れた場合の解決策: [root@localhost ~]# mysql -...
MySQL 論理アーキテクチャの概要他のデータベースと比較すると、MySQL は、そのアーキテクチャ...
目次テクノロジースタック効果分析するテクノロジースタックサイドバー用Antdtabは要素を使用します...