Tツリー

コンピュータ サイエンスにおいて、Tツリーは、Datablitz、eXtremeDB、MySQL Cluster、Oracle TimesTen 、MobileLiteなどのメイン メモリ データベースで使用されるバイナリ ツリー データ構造の一種です。

T ツリーは、インデックスと実際のデータの両方が完全にメモリ内に保持される場合に最適化されたバランスのとれたインデックス ツリー データ構造です。これは、 B ツリーがハード ディスクなどのブロック指向の二次ストレージ デバイスへの保存に最適化されたインデックス構造であるのと同じです。T ツリーは、 AVL ツリーなどのメモリ内ツリー構造のパフォーマンス上の利点を獲得しながら、それらに共通する大きなストレージ スペースのオーバーヘッドを回避しようとします。

T ツリーは、インデックス ツリー ノード自体の中にインデックス データ フィールドのコピーを保持しません。代わりに、実際のデータが常にインデックスとともにメイン メモリ内にあるという事実を利用して、実際のデータ フィールドへのポインタだけを保持します。

Tツリーの「T」は、このタイプのインデックスを最初に説明した元の論文のノードデータ構造の形状を指します。^[1]

T ツリー ノードは通常、親ノードへのポインタ、左と右の子ノード、データ ポインタの順序付けられた配列、およびいくつかの追加の制御データで構成されます。 2 つのサブツリーを持つノードは内部ノードと呼ばれ、サブツリーのないノードはリーフ ノードと呼ばれ、サブツリーが 1 つだけのノードはハーフ リーフノードと呼ばれます。 値がノードの現在の最小値と最大値の間 (両端を含む) にある場合、ノードは値の 境界ノードと呼ばれます。

各内部ノードには、最小データ値の前身（最大下限と呼ばれる）を含むリーフノードまたはハーフリーフノードと、最大データ値の後身（最小上限と呼ばれる）を含むリーフノードまたはハーフリーフノードが存在します。リーフノードとハーフリーフノードには、1からデータ配列の最大サイズまでの任意の数のデータ要素を含めることができます。内部ノードは、事前に定義された最小要素数と最大要素数の間で占有を維持します。

• 検索はルートノードから始まる
• 現在のノードが検索値の境界ノードである場合は、そのデータ配列を検索します。データ配列に値が見つからない場合、検索は失敗します。
• 検索値が現在のノードの最小値より小さい場合は、その左のサブツリーで検索を続行します。左のサブツリーがない場合、検索は失敗します。
• 検索値が現在のノードの最大値より大きい場合は、その右のサブツリーで検索を続行します。右のサブツリーがない場合、検索は失敗します。

• 新しい値の境界ノードを検索します。そのようなノードが存在する場合は、次のようになります。
  • データ配列にまだスペースがあるかどうかを確認し、ある場合は新しい値を挿入して終了します。
  • 使用可能なスペースがない場合は、ノードのデータ配列から最小値を削除し、新しい値を挿入します。次に、新しい値が挿入されたノードの最大の下限値を保持するノードに進みます。削除された最小値がまだそこに収まる場合は、それをノードの新しい最大値として追加します。そうでない場合は、このノードの新しい右サブノードを作成します。
• 境界ノードが見つからなかった場合は、値がまだ収まる場合は最後に検索したノードに値を挿入します。この場合、新しい値は新しい最小値または最大値になります。値が収まらなくなった場合は、新しい左または右のサブツリーを作成します。

新しいノードが追加された場合は、以下で説明するようにツリーを再調整する必要がある場合があります。

• 削除する値の境界ノードを検索します。境界ノードが見つからない場合は終了します。
• 境界ノードに値が含まれていない場合は終了します。
• ノードのデータ配列から値を削除する

ここで、ノード タイプによって区別する必要があります。

• 内部ノード:

ノードのデータ配列の要素数が最小数より少ない場合は、このノードの最大下限値をそのデータ値に移動します。値が削除されたハーフ リーフ ノードまたはリーフ ノードに対して、次の 2 つの手順のいずれかに進みます。

• リーフノード:

これがデータ配列内の唯一の要素である場合は、ノードを削除します。必要に応じてツリーのバランスを再調整します。

• ハーフリーフノード:

ノードのデータ配列をオーバーフローなしでリーフのデータ配列とマージできる場合は、それを実行し、リーフ ノードを削除します。必要に応じてツリーのバランスを再調整します。

T ツリーは、基礎となる自己バランス型二分探索木の上に実装されます。具体的には、Lehman と Carey の記事では、 AVL ツリーのようにバランスが取れた T ツリーについて説明しています。つまり、ノードの子ツリーの高さが 2 レベル以上異なると、バランスが崩れます。これは、ノードの挿入または削除後に発生する可能性があります。挿入または削除後、ツリーはリーフからルートまでスキャンされます。不均衡が見つかった場合は、1 回のツリー回転または 2 回のツリー回転が実行され、ツリー全体のバランスが保たれることが保証されます。

回転の結果、内部ノードのアイテム数が最小数より少なくなると、ノードの新しい子ノードのアイテムが内部ノードに移動されます。

T ツリーは、かつてはパフォーマンス上の利点からメイン メモリ データベースに広く使用されていましたが、最近の非常に大規模なメイン メモリ データベースの傾向では、プロビジョニング コストがより重視されるようになりました。最近の NOSQL データベース システムでは、数兆件のレコードが保存されることが多く、実際の値を含む単一のインデックスを保存するのにも、メモリ コストが数十テラバイト、場合によっては数百テラバイトを超えることがあります。

• ツリー（グラフ理論）
• ツリー（集合論）
• ツリー構造
• 指数木

• Bツリー（2-3ツリー、2-3-4ツリー、B+ツリー、B*ツリー、UBツリー）
• 踊る木
• フュージョンツリー
• k -d ツリー
• オクトリー
• クワッドツリー
• Rツリー
• 基数木
• トップツリー

• Oracle TimesTen FAQ の T-Tree に関するインデックスのエントリ
• Oracle ホワイトペーパー: Oracle TimesTen 製品とテクノロジー
• T-Tree について言及した DataBlitz プレゼンテーション
• オープンソースの T*-tree ライブラリ