データと構造

従来のデータ構造：BツリーとB +ツリーの詳細な分析



Classic Data Structure



この記事の出典： https://www.cnblogs.com/vincently/p/4526560.html

ウィキペディアでは、Bツリーを次のように定義しています。コンピュータサイエンスでは、Bツリーはツリーのようなデータ構造であり、データを格納、並べ替え、O（log n）で時間計算量を許容できます。ルックアップ、シーケンシャル読み取り、挿入、および削除のためのデータ構造を実行します。一般に、Bツリーは、ノードが3つ以上の子ノードを持つことができるバイナリ検索ツリーです。自己平衡二分探索木とは異なり、B木はシステム最適化です バルクデータの読み取りおよび書き込み操作 。 Bツリーアルゴリズムは、レコードを見つけるときに発生する中間プロセスを減らし、それによってアクセスを高速化します。一般的に使用される データベース と ファイルシステム 。」



前の2つの記事では、平衡探索木を紹介しました。 2-3木 、 赤黒木 その後、ファイルシステムやデータベースシステムで一般的に使用されているB / B +ツリーを紹介します。ノードあたりのストレージ数を拡張することで、より高速なポジショニングと連続データへのアクセスが可能になり、検索時間を効果的に短縮できます。ストレージの空間的局所性を改善して、IO操作を削減します。彼は、次のようなファイルシステムやデータベースで広く使用されています。

  • Windows：HPFSファイルシステム
  • Mac：HFS、HFS +ファイルシステム
  • Linux：ResiserFS、XFS、Ext3FS、JFSファイルシステム
  • データベース：ORACLE、MYSQL、SQLSERVERなど。

この記事の作成者のおかげで、この記事がB / B +ツリーの理解に役立つことを願っています。