Bツリーの特性の紹介

Bツリーの特性の紹介

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 をご愛顧いただき、誠にありがとうございます。これについてもっと知りたい場合は、次のリンクをご覧ください。

以下もご興味があるかもしれません:
  • MySQL ハッシュインデックスと B ツリーインデックスの違い
  • SQLite における B ツリー実装の詳細の分析
  • ビットマップインデックスとBツリーインデックスのどちらを使用するかを選択する方法
  • Bツリー挿入プロセスの概要
  • BツリーとB+ツリーの使用に基づくデータ検索とデータベースインデックスの詳細な紹介
  • MySQL Bツリーインデックスとインデックス最適化の概要についての簡単な説明
  • 完全なBツリーアルゴリズムのJava実装コード
  • C言語Bツリーの深い理解
  • Bツリーの削除プロセスの紹介

<<:  ローカルストレージにブール型の値を保存する際の落とし穴を解決する

>>:  Bツリー挿入プロセスの概要

推薦する

MySql データベースにおける単一テーブル クエリと複数テーブル結合クエリの効率の比較

この間、プロジェクトに取り組んでいるときに、データ間の接続が非常に複雑なモジュールに遭遇しました。テ...

HTML で #include ファイルを使用する例

a.htmとb.htmの2つのファイルがあります。同じディレクトリ内のa.htmの内容は次のとおりで...

lnmp を使用して MySQL データベースのルート パスワードをリセットする 2 つの方法

最初の方法: Junge のワンクリック スクリプトを使用して、LNMP 環境で MYSQL データ...

JS 正規マッチングの落とし穴の記録

最近、JS の正規表現マッチングの落とし穴を発見したのですが、その時はあまりにも奇妙だったので、何か...

Linuxテキスト処理ツールの詳細な説明

1. /etc/passwdファイル内のデフォルトシェルが/sbin/nologinではないユーザー...

4つのReactコンポーネントにおけるDOMスタイル設定の詳細な説明

1. インラインスタイル仮想DOMにインラインスタイルを追加するには、式を使用してスタイルオブジェク...

PHP クラスにおける static と self の違いの簡単な分析

メソッドが定義されているクラスに応じて、現在のクラスへの静的参照を取得するには、self:: または...

衝突検出を実装するためのjs

この記事の例では、衝突検出を実装するためのjsの具体的なコードを参考までに共有しています。具体的な内...

Ubuntu に MySQL 5.7 をインストールし、データ ストレージ パスを構成する方法

1. MySQLをインストールするこの記事はAPT経由でインストールされており、インストールされてい...

Linux で Oracle データベースをバックアップするためのスケジュールされたタスクの設定に関するチュートリアル

1. データベースの文字セットを確認するデータベースの文字セットは、Linux で設定された環境変数...

innodb_autoinc_lock_mode の表現と値の選択方法についての簡単な説明

前提条件: Percona 5.6 バージョン、トランザクション分離レベルは RR mysql>...

Vue3におけるキーの役割と動作原理についての簡単な説明

このキー属性の機能は何ですか?まずは公式の説明を見てみましょう。 kekey 属性は主に、新しいノー...

MySQLのパスワードを忘れた場合の対処方法

MySQL パスワードを忘れた場合の解決策: [root@localhost ~]# mysql -...

MySQL 上級学習ノート (パート 3): MySQL 論理アーキテクチャの紹介、MySQL ストレージ エンジンの詳細な説明

MySQL 論理アーキテクチャの概要他のデータベースと比較すると、MySQL は、そのアーキテクチャ...

Vueは、サイドナビゲーションバーをタブページに関連付けるサンプルコードを実装します。

目次テクノロジースタック効果分析するテクノロジースタックサイドバー用Antdtabは要素を使用します...