バイナリ検索ツリーとm-wayツリーの違い

Question

バイナリ検索ツリーとm-wayツリーの違いを教えてください。

Answer 1

binary search treeには固定ブランチが2つしかないため、実装がずっと簡単です。 B-treesのようなm-wayツリーは、ツリーをメモリではなくディスクに格納する必要がある場合に、一般的に使用されます。例には、ファイルシステムとデータベースインデックスが含まれます。

Answer 2

m-wayツリーは、mの値とm + 1のリンクを持つツリー構造です。

バイナリツリーは、mが1に等しいm-wayツリーの特殊なケースです。ノードあたり1つの値と2つのリンク（左または右のリンクに移動する）を意味します。ここではこのことを示してバイナリツリーの例です：

   +----+ 
      | 20 | 
      +----+ 
      / \ 
     +----+  +----+ 
     | 14 |  | 23 | 
     +----+  +----+ 

メートルウェイツリーは、ノードごとに複数の値を持つことができますが、理論は同じです。値に基づいて下に移動するリンクを選択すると、m + 1の選択肢があります。 （mは2である）、Mウェイツリーは次のようになります。あなたは、効率的なブロックで複数の値を収めることができる場所

   +----+----+ 
       | 17 | 30 | 
       +----+----+ 
     ______/  |  \______ 
    /   |   \ 
+----+----+ +----+----+ +----+----+ 
| 11 | 15 | | 19 | 28 | | 33 | 34 | 
+----+----+ +----+----+ +----+----+ 

これらメートルウェイの木は、多くの場合、状況で使用されています。効率的には、ストレージ・サブシステムの動作に応じて、ディスク・ブロック、セクター、クラスター、シリンダーなどのように、効率的に読み取りおよび書き込みができるものを意味します。例えば

は、のは、それを言わせて：

• ディスクブロックは512バイトです。
• ツリー内の値は122バイトです。
• リンクは4バイトを占有します。

  4 * 122 = 488 
  5 * 4 = 20 
        --- 
        508 
  

  ：508バイトの合計あなたの四つの値と5つのリンクを提供します

  numvals = int ((blocksize - linksize)/(valuesize + linksize)) 
       = int (( 512 -  4 )/( 122 +  4 )) 
       = int (   508  /   126  ) 
       = int (     4.0317     ) 
       =        4 
  

  を次のようにこのような状況で

は、あなたが計算され、ディスクブロックに4つの値を収めることができ

いくつかの浪費（この場合は4バイト）がありますが、効率的に取り出せるブロックごとに整数の値を格納する利点があります。

Answer 3

Mウェイ探索木はでMウェイの木である：

各ノードは、m個の子供とM-1キーフィールド 各ノードのキーは昇順であるています。最初のi子供における キーは、最後のMIの子供におけるi番目のキー キーより小さい次数mのBツリー

次数mの多方向探索木の拡張キーIthよりも大きくされています。このタイプのツリーは、大量のデータをノードに格納できるため、アクセス/格納するデータが2次記憶装置上にある場合に使用されます。次数mの

A B-treeが多方向探索木である：それは、ツリー内の唯一のノードでない限り

ルートは、少なくとも2つのサブツリーを有します。 各非ルートノードおよび各非リーフノードには、最大でm個の空でない子ノードと少なくともm/2個の空でない子ノードがあります。 各非ルートノードおよび各非リーフノードのキーの数は、その非空の子の数より1少ない数です。 すべての葉が同じレベルにあります。