B +ツリー – 日本語百科事典辞書

B+_tree

「B +ツリー」
B +ツリーがある多値ツリーの変数とが、ノード当たりの子のしばしば多数。B +ツリーは、ルート、内部ノード、およびリーフで構成されます。ルートは、リーフまたは2つ以上の子を持つノードのいずれかです。
B +ツリー
タイプ
ツリー（データ構造）
時間複雑で大きなO記法
アルゴリズム
平均
最悪の場合
スペース
O（n）
O（n）
検索
O（log n）
O（log n + log L）
入れる
O（log n）
O（M * log n + log L）
消去
O（log n）
O（M * log n + log L）
データ値にキー1-7を連結単純B +ツリーの例は、D
1 -d
7。リンクリスト（赤）を使用すると、順番にすばやく移動できます。この特定の木の分岐係数は{b}= 4。
B +ツリーは、と見なすことができるBツリーの各ノードはキーのみ（いないキーと値のペア）が含まれ、そして追加のレベルが連結葉で底部に付加されています。
B +ツリーの主な価値は、ブロック指向のストレージコンテキスト、特にファイルシステムで効率的に取得するためにデータを保存することです。これは主に、二分探索木とは異なり、B +ツリーのファンアウトが非常に高く（ノード内の子ノードへのポインターの数、通常は100以上のオーダー）、必要なI / O操作の数が減少するためです。ツリーで要素を見つけます。
ReiserFSの、NSS、XFS、JFS、ReFSでは、及びBFSは、メタデータのインデックス作成のための木のすべての使用このタイプのファイルシステムを。BFSは、ディレクトリの保存にもB +ツリーを使用します。NTFSは、ディレクトリおよびセキュリティ関連のメタデータのインデックス作成にB +ツリーを使用します。EXT4は、ファイルエクステントのインデックス作成にエクステントツリー（変更されたB +ツリーデータ構造）を使用します。 APFSは、B +ツリーを使用して、ファイルシステムオブジェクトIDからディスク上の場所へのマッピングを保存し、ファイルシステムレコード（ディレクトリを含む）を保存しますが、これらのツリーのリーフノードには兄弟ポインターがありません。 IBM DB2、 Informix、 Microsoft SQL Server、 Oracle 8、 Sybase ASE、、SQLite などのリレーショナルデータベース管理システムは、このタイプのツリーをサポートしています。テーブルインデックス。などのキーと値のデータベース管理システムCouchDBのと東京キャビネットデータアクセスのためにツリーのこのタイプをサポートします。

コンテンツ
1 概要
2 アルゴリズム
2.1 検索 2.2 プレフィックスキーの圧縮 2.3 挿入 2.4 バルクローディング
3 特徴4 実装 5 歴史
6 も参照してください
7 参考文献
8 外部リンク
8.1 実装

概要
B +ツリーの順序または分岐係数bは、ツリー内の内部ノードのノードの容量（つまり、子ノードの数）を測定します。ここではmと呼ばれるノードの実際の子の数は、内部ノードに対して次のように制約されます。
⌈ /2 ⌉
≤ ≤ { lceil b / 2 rceil leq m leq b}
$lceil$
。ルートは例外です。2人の子を持つことが許可されています。たとえば、B +ツリーの順序が7の場合、各内部ノード（ルートを除く）には4〜7個の子がルートには2〜7個の子がリーフノードには子がありませんが、キーの数が少なくとも必要になるように制約されています。
⌈ /2 ⌉
{ lceil b / 2 rceil}

そしてせいぜい {b}

。B +ツリーが空であるか、1つのノードが含まれている状況では、ルートは単一の葉です。このノードは、必要に応じて最大でキーを持たないことが許可されます − 1 {b-1}

。
ノードタイプ
子供のタイプ
子供の最小数
子供の最大数例 = 7 {b = 7}

例 = 100 {b = 100}

ルートノード（ツリー内で唯一のノードである場合）
記録
0 − 1 {b-1}
0〜6 1〜99 ルートノード
内部ノードまたはリーフノード22–7 2〜100
内部ノード
内部ノードまたはリーフノード
⌈/2 ⌉
{ lceil b / 2 rceil}
4–7 50〜100 リーフノード
記録
⌈/2 ⌉
{ lceil b / 2 rceil}
{b}
4–7 50〜100 アルゴリズム編集

検索
B +ツリーのルートは、ツリー内の値の全範囲を表します。ここで、すべての内部ノードはサブインターバルです。
kB +ツリーで値を探しています。ルートから始めて、値を含む可能性のあるリーフを探していますk。各ノードで、どの内部ポインタに従う必要があるかを判断します。内部B +ツリーノードには最大で {d}

≤ {b}

それらのすべてが異なるサブインターバルを表す子。ノードのキー値を検索して、対応するノードを選択します。
関数search（k）は return tree_search（k、root）です
関数：tree_search（K、ノード）である場合、ノードが葉である、次に
戻りノードスイッチ Kがない場合、K ≤k_0
戻りtree_search（K、P_0）場合K_I 戻りtree_search（K、P_ {I +1}） case k_d return tree_search（k、p_ {d}）
この擬似コードは、重複が許可されていないことを前提としています。

プレフィックスキーの圧縮
ファンアウトを増やすことは重要です。これにより、検索をリーフレベルにより効率的に向けることができます。
インデックスエントリは「直接トラフィック」のみを対象としているため、圧縮できます。

挿入
検索を実行して、新しいレコードをどのバケットに入れるかを決定します。
バケットがいっぱいでない場合（最大で） − 1 {b-1}

挿入後のエントリ）、レコードを追加します。
それ以外の場合は、新しいレコードを挿入する
前に
バケットを分割します。
元のノードには⎡（L + 1）/2⎤アイテムがあります
新しいノードには⎣（L + 1）/2⎦アイテムがあります
⎡（L + 1）/2⎤番目のキーを親に移動し、新しいノードを親に挿入します。
分割する必要のない親が見つかるまで繰り返します。
ルートが分割された場合は、親が空であるかのように扱い、上記の概要のように分割します。
B木は葉ではなく根で成長します。

バルクローディング
データレコードのコレクションが与えられた場合、いくつかのキーフィールドにB +ツリーインデックスを作成します。1つのアプローチは、各レコードを空のツリーに挿入することです。ただし、各エントリではルートから開始して適切なリーフページに移動する必要があるため、非常にコストがかかります。効率的な代替手段は、バルクローディングを使用することです。
最初のステップは、検索キーに従ってデータエントリを昇順で並べ替えることです。
ルートとして機能する空のページを割り当て、エントリの最初のページへのポインタをそのページに挿入します。
ルートがいっぱいになると、ルートを分割し、新しいルートページを作成します。
すべてのエントリにインデックスが付けられるまで、リーフレベルのすぐ上の右端のインデックスページにエントリを挿入し続けます。
ノート：
リーフレベルの上の右端のインデックスページがいっぱいになると、分割されます。
このアクションにより、右端のインデックスページがルートに1ステップ近く分割される可能性が
分割は、ルートからリーフレベルまでの右端のパスでのみ発生します。

特徴
ため、BとB +ツリー-ORDER時間インデックスのレベル：
保存されるレコードの最大数は最大= − − 1 {n _ { max} = b ^ {h} -b ^ {h-1}}
保存されるレコードの最小数は分= 2
⌈ 2
⌉ −1 − 2
⌈ 2
⌉ − 2 {n _ { min} = 2 left lceil { tfrac {b} {2}} right rceil ^ {h-1} -2 left lceil { tfrac {b} {2}} right rceil ^ {h-2}}
キーの最小数は k I = 2 ⌈ 2
⌉ −1 − 1
{n _ { mathrm {kmin}} = 2 left lceil { tfrac {b} {2}} right rceil ^ {h-1} -1}
キーの最大数は k= − 1 {n _ { mathrm {kmax}} = b ^ {h} -1}
木を保管するのに必要なスペースは O （（）。
{O（n）}
レコードを挿入するには O （（ログ）。
{O（ log _ {b} n）}

オペレーション
レコードを見つけるには O （（ログ）。
{O（ log _ {b} n）}

オペレーション（以前に配置された）レコードを削除するには、 O （（ログ）。
{O（ log _ {b} n）}

オペレーション
範囲内で発生するk個の要素を使用して範囲クエリを実行するには、 O （（ログ + k ）。
{O（ log _ {b} n + k）}

オペレーション

実装
B +ツリーの葉（最下部のインデックスブロック）は、リンクリストで相互にリンクされていることがよくこれにより、範囲クエリまたはブロックを介した（順序付けられた）反復がより簡単かつ効率的になります（ただし、前述の上限は、この追加がなくても達成できます）。これにより、ツリーのスペース消費やメンテナンスが大幅に増加することはありません。これは、Bツリーに対するB +ツリーの重要な利点の1つを示しています。Bツリーでは、すべてのキーがリーフに存在するわけではないため、このような順序付けられたリンクリストを作成することはできません。したがって、B +ツリーは、データ自体を格納するための効率的な構造を実際に提供できるため、データが通常ディスク上に存在するデータベースシステムインデックスとして特に役立ちます（これは：238で説明されています）。インデックス構造として「代替1」）。
ストレージシステムのブロックサイズがBバイトで、保存するキーのサイズがkの場合、おそらく最も効率的なB +ツリーは次のようなものです。 = k− 1
{b = { tfrac {B} {k}}-1}

。理論的には1回限りは不要ですが、実際には、インデックスブロック（たとえば、リーフブロック内のリンクリスト参照）によって占有されるスペースが少し余分にあることがよくストレージシステムの実際のブロックよりもわずかに大きいインデックスブロックがあると、パフォーマンスが大幅に低下します。したがって、注意を怠るのが望ましいです。
B +ツリーのノードが要素の配列として編成されている場合、配列の半分を平均してシフトする必要があるため、要素の挿入または削除にかなりの時間がかかる場合がこの問題を克服するために、ノード内の要素を配列ではなくバイナリツリーまたはB +ツリーに編成できます。
B +ツリーは、RAMに保存されているデータにも使用できます。この場合、ブロックサイズの妥当な選択は、プロセッサのキャッシュラインのサイズです。
B +ツリーのスペース効率は、いくつかの圧縮技術を使用することで改善できます。1つの可能性は、デルタエンコーディングを使用して、各ブロックに格納されているキーを圧縮することです。内部ブロックの場合、スペースの節約は、キーまたはポインターのいずれかを圧縮することによって実現できます。文字列キーの場合、次の手法を使用してスペースを節約できます。通常、内部ブロックのi番目のエントリにはブロックの最初のキーが含まれます。I + 1
{i + 1}

。完全なキーを保存する代わりに、ブロックの最初のキーの最短のプレフィックスを保存できますI + 1
{i + 1}

これは、ブロックiの最後のキーよりも厳密に（辞書順で）大きいです。ポインタを圧縮する簡単な方法もいくつかの連続したブロックがあると仮定した場合
I 私+ 1
、。私+ k
{i、i + 1、… i + k}

が連続して格納されている場合は、最初のブロックへのポインタと連続するブロックの数のみを格納するだけで十分です。
上記のすべての圧縮技術には、いくつかの欠点がまず、単一の要素を抽出するには、ブロック全体を解凍する必要がこの問題を克服するための1つの手法は、各ブロックをサブブロックに分割し、それらを個別に圧縮することです。この場合、要素の検索または挿入は、完全なブロックではなく、サブブロックを解凍または圧縮するだけで済みます。圧縮技術のもう1つの欠点は、各ブロック内で要素がどの程度圧縮されているかに応じて、格納される要素の数がブロックごとに大幅に異なる可能性があることです。

歴史
Bツリーは、論文Organization and Maintenance of Large OrderedIndicesで最初に説明されました。ACTA Informaticaは1：173から189（1972）によってルドルフ・ベイヤーとエドワード・M・マクライト。B +ツリーの概念を紹介する単一の論文はありません。代わりに、リーフノードですべてのデータを維持するという概念は、興味深い変形として繰り返し取り上げられています。B +ツリーもカバーするBツリーの初期の調査はDouglasComerです。 Comerは、B +ツリーがIBMのVSAMデータアクセスソフトウェアで使用されており、1973年にIBMが公開した記事を参照していると述べています。

も参照してください
二分探索木
Bツリー
分割統治アルゴリズム

参考文献
^ Navathe、Ramez Elmasri、Shamkant B.（2010）。データベースシステムの基礎（第6版）。ニュージャージー州アッパーサドルリバー：ピアソンエデュケーション。pp。652–660。ISBN 9780136086208。
^ http://www.seanster.com/BplusTree/BplusTree.html ^ ジャンパオロ、ドミニク（1999）。Beファイルシステムを使用した実用的なファイルシステム設計（PDF）。モーガンカウフマン。ISBN
1-55860-497-9。2017-02-13にオリジナル（PDF）からアーカイブされました。
^ 「Bツリー」。Appleファイルシステムリファレンス（PDF）。Apple Inc.2020-06-22。NS。122 。2021-03-10を取得。
^ Ramakrishnan Raghu、Gehrke Johannes –データベース管理システム、McGraw-Hill Higher Education（2000）、第2版（en）267ページ ^ SQLiteバージョン3の概要 ^ CouchDBガイド（3番目の段落の後の注を参照）
^ 東京内閣リファレンスアーカイブで2009年9月12日、ウェイバックマシン ^ 「ECS165B：データベースシステム実装講義6」（PDF）。カリフォルニア大学デービス校のCS部門。21〜23ページ。
^ 「ユビキタスBツリー」、ACM Computing Surveys 11（2）：121–137（1979）。

外部リンク
ウィキブックスには、次のトピックに関する本があります：アルゴリズムの実装/ツリー/ B +ツリー
リストの実装に使用されるPythonのB +ツリー
モンジ博士のB +ツリーインデックスノート
マルチスレッドアーキテクチャでのCSB +ツリーのパフォーマンスの評価
キャッシュを意識したB +ツリーのパフォーマンスに対するノードサイズの影響
フラクタルプリフェッチB +ツリー
フィールドのpB +ツリーに向けて：実装選択とパフォーマンス
メインメモリデータベースのキャッシュを意識したインデックス構造
忘却のB（+）ツリーをキャッシュする
Bツリーの力：CouchDB B +ツリーの実装
B +ツリーの視覚化
B + -KerttuPollari-Malmiによる木
データ構造BツリーとB +ツリー

実装
CでのインタラクティブなB +ツリーの実装
C ++でのインタラクティブなB +ツリーの実装
C ++テンプレートライブラリとしてのメモリベースのB +ツリーの実装
以前の2019年の改善
C ++テンプレートライブラリとしてのストリームベースのB +ツリーの実装
オープンソースのJavaScriptB +ツリーの実装
B +ツリーのPerl実装
B +ツリーのJava / C＃/ Python実装
C＃B +ツリーおよび関連する「Aリスト」データ構造
スレッド化とMVCCをサポートするC＃のファイルベースのB + Tree
TypeScript / JavaScript、MITライセンスの高速セミパーシステントインメモリB +ツリー
JavaScript B +ツリー、MITライセンス
JavaScript B +ツリー、インタラクティブおよびオープンソース”