データベースから最高のパフォーマンスでツリー構造のデータを取得するにはどうすればよいでしょうか? たとえば、データベースにフォルダー階層があるとします。folder-database-row には、 ID、Name、およびParentID列があります。
特別なアルゴリズムを使用してすべてのデータを一度に取得し、データベース呼び出しの量を最小限に抑えてコードで処理しますか?
それとも、データベースへの多くの呼び出しを使用して、データベースから直接構造を取得しますか?
たぶん、データベース行のx量、階層の深さなどに基づいて異なる答えがあるでしょうか?
編集: Microsoft SQL Server を使用していますが、他の観点からの回答も興味深いものです。
それは、ツリーへのアクセス方法に大きく依存します。
巧妙な手法の 1 つは、すべてのノードに文字列 ID を与えることです。ここで、親の ID は、子の予測可能な部分文字列です。たとえば、親は '01' で、子は '0100'、'0101'、'0102' などになります。このようにして、データベースからサブツリー全体を一度に選択できます。
SELECT * FROM treedata WHERE id LIKE '0101%';
基準は最初の部分文字列であるため、ID 列のインデックスはクエリを高速化します。
ツリーを RDMS に格納するすべての方法の中で最も一般的なのは、隣接リストとネストされたセットです。ネストされたセットは読み取り用に最適化されており、1 回のクエリでツリー全体を取得できます。隣接リストは書き込み用に最適化されており、簡単なクエリで追加できます。
隣接リストを使用すると、各ノードには、親ノードまたは子ノードを参照する列があります (他のリンクも可能です)。それを使用して、親子関係に基づいて階層を構築できます。残念ながら、ツリーの深さを制限しない限り、1 つのクエリですべてを取得することはできず、通常は更新よりも読み取りが遅くなります。
ネストされた集合モデルでは、その逆が当てはまり、読み取りは高速で簡単ですが、番号付けシステムを維持する必要があるため更新が複雑になります。ネストされたセット モデルは、事前順序に基づく番号付けシステムを使用してすべてのノードを列挙することにより、親子関係と並べ替え順序の両方をエンコードします。
ネストされたセット モデルを使用しましたが、大きな階層の読み取りを最適化するのは複雑ですが、それだけの価値があります。ツリーを作成してノードに番号を付ける演習をいくつか行えば、コツをつかむことができます。
この方法に関する私の調査は、記事「Managing Hierarchical Data in MySQL 」から始まりました。
私が取り組んでいる製品では、いくつかのツリー構造が SQL Server に格納されており、上記の手法を使用してノードの階層をレコードに格納しています。すなわち
tblTreeNode
TreeID = 1
TreeNodeID = 100
ParentTreeNodeID = 99
Hierarchy = ".33.59.99.100."
[...] (actual data payload for node)
もちろん、階層を維持することはトリッキーなビットであり、トリガーを利用します。ただし、親または子の階層には必要なすべての情報があるため、挿入/削除/移動での生成は再帰的ではありません。
したがって、ノードのすべての子孫を取得できます。
SELECT * FROM tblNode WHERE Hierarchy LIKE '%.100.%'
挿入トリガーは次のとおりです。
--Setup the top level if there is any
UPDATE T
SET T.TreeNodeHierarchy = '.' + CONVERT(nvarchar(10), T.TreeNodeID) + '.'
FROM tblTreeNode AS T
INNER JOIN inserted i ON T.TreeNodeID = i.TreeNodeID
WHERE (i.ParentTreeNodeID IS NULL) AND (i.TreeNodeHierarchy IS NULL)
WHILE EXISTS (SELECT * FROM tblTreeNode WHERE TreeNodeHierarchy IS NULL)
BEGIN
--Update those items that we have enough information to update - parent has text in Hierarchy
UPDATE CHILD
SET CHILD.TreeNodeHierarchy = PARENT.TreeNodeHierarchy + CONVERT(nvarchar(10),CHILD.TreeNodeID) + '.'
FROM tblTreeNode AS CHILD
INNER JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
WHERE (CHILD.TreeNodeHierarchy IS NULL) AND (PARENT.TreeNodeHierarchy IS NOT NULL)
END
更新トリガーは次のとおりです。
--Only want to do something if Parent IDs were changed
IF UPDATE(ParentTreeNodeID)
BEGIN
--Update the changed items to reflect their new parents
UPDATE CHILD
SET CHILD.TreeNodeHierarchy = CASE WHEN PARENT.TreeNodeID IS NULL THEN '.' + CONVERT(nvarchar,CHILD.TreeNodeID) + '.' ELSE PARENT.TreeNodeHierarchy + CONVERT(nvarchar, CHILD.TreeNodeID) + '.' END
FROM tblTreeNode AS CHILD
INNER JOIN inserted AS I ON CHILD.TreeNodeID = I.TreeNodeID
LEFT JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
--Now update any sub items of the changed rows if any exist
IF EXISTS (
SELECT *
FROM tblTreeNode
INNER JOIN deleted ON tblTreeNode.ParentTreeNodeID = deleted.TreeNodeID
)
UPDATE CHILD
SET CHILD.TreeNodeHierarchy = NEWPARENT.TreeNodeHierarchy + RIGHT(CHILD.TreeNodeHierarchy, LEN(CHILD.TreeNodeHierarchy) - LEN(OLDPARENT.TreeNodeHierarchy))
FROM tblTreeNode AS CHILD
INNER JOIN deleted AS OLDPARENT ON CHILD.TreeNodeHierarchy LIKE (OLDPARENT.TreeNodeHierarchy + '%')
INNER JOIN tblTreeNode AS NEWPARENT ON OLDPARENT.TreeNodeID = NEWPARENT.TreeNodeID
END
もう 1 つ、ツリー ノードでの循環参照を防止するためのチェック制約を示します。
ALTER TABLE [dbo].[tblTreeNode] WITH NOCHECK ADD CONSTRAINT [CK_tblTreeNode_TreeNodeHierarchy] CHECK
((charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy],(charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy]) + 1)) = 0))
また、ツリーごとに複数のルート ノード (null 親) を防止し、関連するノードが異なる TreeID に属さないようにするためのトリガーをお勧めします (ただし、これらは上記よりも少し簡単です)。
このソリューションが適切に実行されるかどうかを確認するために、特定のケースを確認する必要があります。お役に立てれば！
Celko はこれについて書いています (2000):
http://www.dbmsmag.com/9603d06.html
そして他の人々は尋ねました：
データベースにディレクトリ/階層/ツリー構造を格納する方法は?
階層データを取得するための MYSQL での再帰ストアド プロシージャのパフォーマンス
フラットテーブルをツリーに解析する最も効率的/エレガントな方法は何ですか?
最後に、Rails の「acts_as_tree」(読み取りが多い) プラグインと「acts_as_nested_set」(書き込みが多い) プラグインを見ることができます。それらを比較する良いリンクがありません。
階層に対する一般的な種類のクエリがいくつかあります。他のほとんどの種類のクエリは、これらのバリエーションです。
親から、すべての子を検索します。
a. 特定の深さまで。たとえば、私の直接の親が与えられた場合、深さ 1 までのすべての子は私の兄弟になります。
b. 木の根元へ。
子から、すべての親を見つけます。
a. 特定の深さまで。たとえば、私の直接の親は深さ 1 の親です。
b. 無限の深さへ。
(a) ケース (特定の深さ) は、SQL の方が簡単です。特殊なケース (深さ = 1) は、SQL では些細なことです。ゼロ以外の深さはより困難です。有限であるがゼロではない深さは、有限数の結合を介して行うことができます。(b) 無限の深さ (上へ、下へ) の場合は、非常に困難です。
ツリーが巨大(何百万ものノード) である場合、何をしようとしても傷の世界にいることになります。
ツリーが 100 万ノード未満の場合は、すべてをメモリにフェッチして、そこで作業します。オブジェクト指向の世界では、人生ははるかに単純です。行をフェッチし、行が返されたらツリーを構築するだけです。
巨大なツリーがある場合、2 つの選択肢があります。
無制限のフェッチを処理するための再帰カーソル。これは、構造のメンテナンスが O(1) であることを意味します。いくつかのノードを更新するだけで完了です。ただし、子を持つノードごとにカーソルを開く必要があるため、フェッチは O(n*log(n)) です。
巧妙な「ヒープ番号付け」アルゴリズムにより、各ノードの親子関係をエンコードできます。各ノードに適切な番号が付けられると、簡単な SQL SELECT を 4 種類のクエリすべてに使用できます。ただし、ツリー構造を変更するには、ノードの番号を付け直す必要があるため、取得のコストに比べて変更のコストがかなり高くなります。
データベースに多くのツリーがあり、ツリー全体しか取得できない場合、ツリー ID (またはルート ノード ID) と各ノードの親ノード ID をデータベースに格納し、すべてのノードを取得します。特定のツリー ID、およびメモリ内のプロセス。
ただし、サブツリーを取得する場合は、特定の親ノード ID のサブツリーしか取得できないため、各ノードのすべての親ノードを格納して上記の方法を使用するか、複数の SQL クエリを実行する必要があります。 SQL の再コンパイルを防ぐために同じプリペアド ステートメントを再利用できますが (ノードが同じタイプであり、すべてが単一のテーブルに格納されていると仮定して)、ツリーに循環がないことを願っています。実際、データベースの最適化がクエリに適用されている場合は、それが望ましい場合があります。調べるためにいくつかのテストを実行したい場合があります。
ツリーを 1 つだけ保存している場合、質問はサブツリーのみをクエリする質問の 1 つになり、2 番目の回答が適用されます。
私は、parentID に関連付けられた ID を格納する単純な方法のファンです。
ID ParentID
1 null
2 null
3 1
4 2
... ...
保守が容易で、非常にスケーラブルです。
「実体化されたパス」または「遺伝的ツリー」のGoogle...
Oracle には、ツリーを取得するための SELECT ... CONNECT BY ステートメントがあります。
この記事は、いくつかの取得方法と、系統を派生列として格納する方法を示しているため、興味深いものです。リネージは、結合をあまり行わずに階層を取得するためのショートカット メソッドを提供します。