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ツリー挿入プロセスの概要

推薦する

JavaScript でプロトタイプ パターンを実装する方法

概要プロトタイプ パターンは、プロトタイプ インスタンスによって作成されるオブジェクトの型を指し、こ...

MySQLデータベースのパスワードを忘れた場合の解決策

先ほど MySQL パスワードを設定したのに、外食したり荷物を受け取ったりするときにパスワードを忘れ...

「さらに表示」ボタンによる複数行テキストの切り捨てに関する考察

最近、たまたまこの小さな要件に遭遇しました。昔、JS を使用してこれを処理したことを覚えていますが、...

Linux カーネル デバイス ドライバーのメモリ管理に関する注意事項

/************************ * Linux メモリ管理 *********...

Mac M1 での Nginx のマルチサイト構成の実装

注: nginxはbrew経由でインストールされますウェブサイトのルートディレクトリ: /opt/h...

ウェブデザイナーが持つべき7つのスキル

Web デザインは科学であると同時に芸術でもあります。 Web デザイン作業は、半分は適切なプログラ...

Docker-compose を使用して Django アプリケーションをオフラインでデプロイする方法

目次開発環境用のDocker-ceをインストールする開発環境用のDocker-composeをインス...

Linux システムで .sh ファイルを実行する方法

Linux システムで .sh ファイルを実行する方法は 2 つあります。たとえば、ルート ディレク...

nginx 設定チュートリアルにおける add_header の落とし穴の詳細な説明

序文add_header は、headers モジュールで定義されたディレクティブです。名前が示すよ...

テーブル設定の背景画像が100%表示されない解決策

開発中に以下の状況が発見されました。 (1) ファイルが.jspファイル拡張子で保存されている場合、...

HTML 代替カラーコードを実現する n 通りの方法 サンプルコード

この記事では、主に HTML のサンプル コードを紹介し、次のように交互に色を変更する方法を共有しま...

Vue マルチページ構成の詳細

目次1. 複数ページの違い2. SPAとMPA 3. Vue Cli スキャフォールディング構成1....

トークンの有効期限が切れたときにページを更新するときに繰り返しプロンプトが表示されないようにする Vue について

トークンの有効期限が切れたら、ページを更新します。ページの読み込み時にバックエンドに複数のリクエスト...

Nginxドメイン名転送のhttpsアクセスの実装

事前に一言:突然、複数のドメイン名のアクセスを https に転送するというタスクを受け取りました。...

Vue はモバイル端末にマルチグリッド入力ボックスを実装

最近、同社は、下図に示すように、h5 ページ操作を完了するという要件を提示しました。 ネットで入手で...