[アーティクル]
09/28/2010

hierarchyid データ型の使用 (データベースエンジン)

hierarchyid データ型は、システムによって提供されています。階層構造を持つテーブルを作成したり、データの階層構造を別の場所で参照するには、データ型として hierarchyid を使用します。階層データのクエリや操作を Transact-SQL で実行するには、hierarchyid 関数を使用します。

階層データは、階層リレーションシップで相互に関連付けられたデータアイテムのセットとして定義されます。階層リレーションシップでは、あるデータアイテムが別のアイテムの親となります。階層データは、データベースで一般的に使用されます。例を次に示します。

組織構造
ファイルシステム
プロジェクト内のタスクのセット
言語の用語の分類
Web ページ間のリンクのグラフ

SQL Server 2008 の新機能である hierarchyid 型を使用すると、階層データの格納とクエリが容易になります。hierarchyid は、最も一般的な階層データであるツリー構造を表すために最適化されています。

hierarchyid の主要な特性

hierarchyid データ型の値は、ツリー階層における位置を表します。hierarchyid の値には、以下の特性があります。

非常にコンパクト

n 個のノードを持つツリー内の、1 つのノードを表すために必要な平均ビット数は、平均ファンアウト (ノードあたりの子の平均数) によって決まります。ファンアウトが小さい場合 (0 ～ 7)、サイズは約 6*logAn ビットです (A は平均ファンアウト)。平均ファンアウトが 6 レベルで、100,000 人から成る組織階層の場合、1 つのノードには約 38 ビットが必要です。格納時には、これが 40 ビット (5 バイト) に切り上げられます。
深さ優先順で比較

a と b の 2 つの hierarchyid 値がある場合、a<b は、ツリーの深さ優先検査において a が b の前に来ることを意味します。hierarchyid データ型のインデックスは深さ優先順であり、深さ優先検査で近接するノードどうしは、相互に近接して格納されます。たとえば、あるレコードの子は、そのレコードに隣接して格納されます。
任意の挿入および削除のサポート

GetDescendant メソッドを使用すると、指定したノードの右側や左側、または任意の 2 つの兄弟間に、いつでも兄弟を生成できます。階層に対して任意の数のノードを挿入または削除しても、比較の特性は維持されます。ほとんどの挿入や削除では、コンパクトさも維持されます。ただし、2 ノード間に挿入した場合は、hierarchyid 値のコンパクトさがやや失われます。

hierarchyid の制限事項

hierarchyid データ型には、以下の制限事項があります。

hierarchyid 型の列が自動的にツリーを表すことはありません。行と行の間に必要なリレーションシップが反映されるよう、hierarchyid 値を生成して割り当てるのは、アプリケーションの役割です。アプリケーションによっては、hierarchyid 型の列でツリーを表すことが望ましくない場合もあります。値で、別のテーブルで定義された階層内の場所を参照することがあるためです。
hierarchyid 値の生成と割り当てにおいて、同時実行を管理するのはアプリケーションの役割です。アプリケーションで一意キー制約を使用したり、独自のロジックで一意性を適用したりしない限り、列内の hierarchyid 値の一意性は保証されません。
hierarchyid 値で表される階層リレーションシップは、外部キーリレーションシップとは適用方法が異なります。階層リレーションシップでは、A に子 B があるとき、A だけを削除し、存在しないレコードに対するリレーションシップを B が引き続き保持することも可能であり、これが適切な場合もあります。この動作を許容しない場合は、親を削除する前に、アプリケーションで子孫に対するクエリを実行する必要があります。

インデックス作成方法

階層データのインデックスを作成する方法には、次の 2 つがあります。

深さ優先

深さ優先のインデックスで、サブツリー内の行が相互に近接して格納されます。たとえば、ある管理者の管理責任下にあるすべての従業員が、管理者のレコードの近くに格納されます。

各ノードは一緒に格納されます。

幅優先

幅優先の場合、階層の各レベルの行が一緒に格納されます。たとえば、同一の管理者に直属する従業員のレコードが、相互に近接して格納されます。

各階層レベルは、一緒に格納されます。

例

幅優先順を作成するには、GetLevel() メソッドを使用します。次の例では、幅優先と深さ優先の両方のインデックスを作成します。

USE AdventureWorks ; 
GO

CREATE TABLE Organization
   (
    EmployeeID hierarchyid,
    OrgLevel as EmployeeID.GetLevel(), 
    EmployeeName nvarchar(50) NOT NULL
   ) ;
GO

深さ優先のインデックスでは、ノードのサブツリー内のすべてのノードが同じ場所に配置されます。このため、"このフォルダーとそのサブフォルダーにあるファイルをすべて検索する" など、サブツリーに関するクエリに応答するには、深さ優先インデックスが効率的です。

CREATE CLUSTERED INDEX Org_Breadth_First 
ON Organization(OrgLevel,EmployeeID) ;
GO

CREATE UNIQUE INDEX Org_Depth_First 
ON Organization(EmployeeID) ;
GO

幅優先のインデックスでは、ノードの直接の子すべてが同じ場所に配置されます。このため、"この管理者に直属するすべての従業員を検索する" など、直下の子に関するクエリに応答するには、幅優先インデックスが効率的です。

深さ優先、幅優先、またはこれらの両方を使用するか、また、どちらをクラスター化キーとするか (該当する場合) は、上記の種類のクエリの相対的重要度と、SELECT 操作と DML 操作の相対的重要度によって決まります。インデックス作成方法の詳細な例については、「チュートリアル : hierarchyid データ型の使用」を参照してください。

hierarchyid に代わる方法を使用する場合

hierarchyid を使用せずに階層データを表すためには、次の 2 つの方法があります。

親/子
XML

通常、これらの方法よりも hierarchyid の方が優れています。しかし、次のような状況では、これらの代替方法を使用した方がよい場合があります。

親/子

親/子の方法を使用すると、各行に親への参照が含まれます。次のテーブルでは、親/子リレーションシップにある親と子の行を含めるための、一般的なテーブルを定義します。

USE AdventureWorks ;
GO

CREATE TABLE ParentChildOrg
   (
    EmployeeID int PRIMARY KEY,
    ManagerId int REFERENCES ParentChildOrg(EmployeeID),
    EmployeeName nvarchar(50) 
   ) ;
GO

一般的な操作に関する親/子と hierarchyid の比較

サブツリーのクエリは、hierarchyid を使用した方がはるかに高速です。
直接の子孫のクエリは、hierarchyid を使用するとわずかに遅くなります。
非リーフノードの移動は、hierarchyid を使用すると遅くなります。非リーフノードを挿入する場合、およびリーフノードを挿入または移動する場合も、hierarchyid を使用する場合と同様に複雑になります。

次の条件に当てはまるときは、親/子を使用した方がよい場合があります。

キーのサイズが非常に重要なとき。同じノード数に対して、hierarchyid 値が整数系 (smallint、int、bigint) の値以上であるとき。これが、ごくまれに親/子を使用する場合の唯一の理由です。親/子構造の使用時に必要な共通テーブル式よりも、hierarchyid の方が、I/O の局所性と CPU の複雑さにおいてはるかに優れているためです。
階層の複数セクションにわたるクエリをめったに実行しないとき。つまり、通常のクエリが、階層内の単一ポイントのみを対象とするとき。このようなケースでは、同じ場所への配置は重要でありません。たとえば、個々の従業員の給与処理のみに組織テーブルを使用する場合、親/子の方が優れています。
非リーフサブツリーが頻繁に移動し、かつパフォーマンスが非常に重要なとき。親/子表現では、階層内の行の場所を変更すると、1 行のみが影響を受けます。hierarchyid 使用時に行の場所を変更すると、n 行が影響を受けます (n は移動されるサブツリー内のノード数)。

非リーフサブツリーが頻繁に移動し、かつパフォーマンスが非常に重要だが、ほとんどの移動が正しく定義された階層レベルで行われるときは、上位レベルと下位レベルを 2 つの階層に分割することを検討してください。こうすると、すべての移動が上位階層のリーフレベルになります。たとえば、サービスによってホストされている Web サイトの階層があるとします。サイトには、階層状に配置された多くのページが含まれています。ホストされているサイトは、サイト階層内の他の場所に移動される可能性がありますが、下位ページの配置が変更されることはまれです。これは、次のように表すことができます。
```
CREATE TABLE HostedSites 
   (
    SiteId hierarchyid, PageId hierarchyid
   ) ;
GO
```

XML

XML ドキュメントはツリーです。このため、XML データ型の 1 つのインスタンスで、完全な階層を表すことができます。SQL Server で XML インデックスを作成する際は、階層内の位置を表す hierarchyid 値が内部で使用されます。

次のすべての条件に当てはまるときは、XML データ型を使用した方がよい場合があります。

完全な階層が常に格納および取得されるとき。
アプリケーションによって XML 形式でデータが消費されるとき。
述語検索が非常に限られており、かつパフォーマンスが重要でないとき。

たとえば、アプリケーションで複数の組織を追跡し、完全な組織階層を常に格納および取得し、かつ単一の組織に対するクエリを実行しないときには、次の形式のテーブルが効果的な場合があります。

CREATE TABLE XMLOrg 
    (
    Orgid int,
    Orgdata xml
    ) ;
GO

親/子から hierarchyid への移行

現在、ほとんどのツリーは親/子を使用して表されています。親/子構造から hierarchyid を使用したテーブルに移行する最も簡単な方法は、一時列または一時テーブルを使用して、階層の各レベルのノード数を追跡する方法です。親/子テーブルの移行例については、「チュートリアル : hierarchyid データ型の使用」のレッスン 1 を参照してください。

hierarchyid のクエリ変換

階層のクエリのパフォーマンスを最大化するため、SQL Server では、hierarchyid が含まれたクエリに 3 つの変換が自動的に実行されます。これらの変換の結果は、変換済みクエリのプラン表示出力で参照できます。

IsDescendantOf は範囲シークに変換される

列または変数として E を指定すると、E.IsDescendantOf(c) は範囲シークに変換されます。これにより、子孫検索のコストが大幅に削減されます。E の深さ優先インデックスがある場合、この変換が役立ちます。E のすべての子孫が同じ場所に配置されているためです。たとえば、コード例 EmployeeId.IsDescendantOf(@value) は、EmployeeId >= @Value AND EmployeeId <= @Value.DescendantLimit() として実行されます。DescendantLimit は、ノードの有効な子孫すべての最低上限を判断する内部メソッドです。@value がパラメーターであるとは限りません。たとえば、結合条件からの列である場合もあります。

GetAncestor は範囲スキャンおよび残余述語に変換される

GetAncestor(n) では、ノードの n 番目の先祖が取得されます。2 つのノード間に、一般的な IsDescendantOf よりも正確なリレーションシップ (親、子、その上の先祖など) が必要な場合に役立ちます。

たとえば、直接の管理者が @value である従業員すべてを検索するには、次のクエリを実行します。

SELECT * FROM Employees WHERE EmployeeId.GetAncestor(1) = @value

これは @value の子孫の範囲スキャンに変換され、元の述語は残余となります。コードは、次のように変換されます。

SELECT * FROM Employees 
WHERE 
   EmployeeId >= @Value AND EmployeeId <= @value.DescendantLimit() 
   AND EmployeeId.GetAncestor(1) = @value

この影響により、スキャンが @value のサブツリーに限定されます。

GetAncestor は、幅優先インデックスを使用するインデックス参照に変換される

上記のクエリで @value がツリーの上位レベルにある場合、上記の最適化によってスキャン対象の行数が大幅に減ることはありません。n 番目の先祖に関する質問をよく使用する場合は、既に説明したように、アプリケーションで幅優先インデックスを作成することをお勧めします。

幅優先インデックスが存在すると、上記のクエリがさらに次のように変換されます。

SELECT * FROM Employees 
WHERE 
   EmployeeId >=@value AND EmployeeId <= @Value.DescendantLimit() 
   AND @value.GetLevel()+1 = EmployeeId.GetLevel()

GetLevel メソッドが含まれる最終行が、幅優先インデックスのインデックス参照となります。EmployeeId がクラスター化キーである場合、これは幅優先インデックスの 2 列目です。また、2 つの述語は、同じ場所に配置された n 人の @value 直属の部下を正確に指定するインデックス参照となります。

GetAncestor の変換は、直接の親のクエリに限定されません。GetAncestor の引数には、任意の変数または定数を指定できます。

hierarchyid データ型の使用 (データベースエンジン)

hierarchyid の主要な特性

hierarchyid の制限事項

インデックス作成方法

例

hierarchyid に代わる方法を使用する場合

親/子

XML

親/子から hierarchyid への移行

hierarchyid のクエリ変換

IsDescendantOf は範囲シークに変換される

GetAncestor は範囲スキャンおよび残余述語に変換される

GetAncestor は、幅優先インデックスを使用するインデックス参照に変換される

関連項目

参照

概念

その他のリソース

hierarchyid データ型の使用 (データベース エンジン)

hierarchyid の主要な特性

hierarchyid の制限事項

インデックス作成方法

例

hierarchyid に代わる方法を使用する場合

親/子

XML

親/子から hierarchyid への移行

hierarchyid のクエリ変換

IsDescendantOf は範囲シークに変換される

GetAncestor は範囲スキャンおよび残余述語に変換される

GetAncestor は、幅優先インデックスを使用するインデックス参照に変換される

関連項目

参照

概念

その他のリソース

hierarchyid データ型の使用 (データベースエンジン)