こんにちは。 この記事では、データベースに階層構造を保存する非常に興味深い方法について説明します。これは、一般に受け入れられ、よく知られている3つ（隣接リスト、ネストセット、マテリアライズドパス）とは関係ありません。 インターネットで彼について言及されたことはありませんが、これは非常に驚くべきことです。なぜなら、私の意見では、これが階層構造を保存する最良かつ唯一の方法だからです。 コンソールのようなフォーラムを開発するとき、私はこの方法を使用しましたが、1グラムについては後悔していません。 これは著者の記事であり、コピーアンドペースト方式で挿入された文は1つではありません。
このメソッドは既知であり、異なる方法で呼び出される可能性があります。 もしそうなら、私はそれが実際に何と呼ばれているのかを喜んで知るでしょう。
私見、この方法は、マテリアライズドパスに最も似ていますが、わずかな隣接リストがあります。 隣接リストと比較すると、データベースはわずかに非正規化されますが、利点があるため、重要な役割を果たしません。
メソッドの本質
階層構造ごとに、2つのテーブルを作成します-データを含むテーブルと階層を含むテーブル。 データテーブルに、必要なものを保存します。ここで興味のあるセルはPRIMARY（ `ID`）だけです
階層テーブルには、すべての要素とその親のリストを、各親のレベルとともに保存します。 つまり、要素に5つの親がある場合、5つの形式のレコード（ElemID、ParentID、Level）を格納します。 したがって、最も深い要素を記述するには、ネストのレベルに等しい要素数が必要になります。
あなたは恐ろしいかもしれません：「ああ、これはベースが膨張するからです！」 ただし、これはそれほど重要ではありません。データテーブルの1ダース程度のテキストフィールドと比較して、階層テーブルには3つのintフィールドしかありません。 つまり、行数にもかかわらず、階層テーブルは非常に軽量になります。
例
だから私はどのようなツールキットを使用していますか：
- PHP 5.3。 オブジェクトは参照によって渡されることが重要です。したがって、バージョン4を使用しないか、コードを大幅に改良することをお勧めします。
- mysql。 バージョンはそれほど重要ではないため、MySQLの基本機能が使用されます。 唯一のことは、InnoDBを選択した場合-それが良いと思います
データベース（LGPL）の操作に自分のクラスpastebin.com/f2642074fを使用しています。 接続パラメーターを変更するのはその中にあります。
コード自体について：
データベースに保存する要素を決定します。 これは、プロパティ$ id、$ data、$ children、$ parentを持つクラスElemのオブジェクトです： pastebin.com/f78f943d8
データベースで機能する既製の関数。それらについては後で説明します： pastebin.com/f314afb10
また、データベースに2つのテーブルを作成します。
CREATE TABLE `Elements` (
`ID` int (11) NOT NULL AUTO_INCREMENT,
` Data ` varchar (64) NOT NULL ,
PRIMARY KEY (`ID`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
CREATE TABLE `ElementsHierarchy` (
`ElemID` int (11) NOT NULL ,
`ParentID` int (11) DEFAULT NULL ,
` Level ` int (11) NOT NULL ,
KEY `ElemID` (`ElemID`),
KEY `ParentID` (`ParentID`),
KEY ` Level ` (` Level `)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
* This source code was highlighted with Source Code Highlighter .
例の説明
ベースファイルを接続した直後に、テストデータを取得するためにgenerateData関数を呼び出します。4はレベルごとの要素数、3はネストの深さです。
$tree = generateData(4, 3, null);
右側には、$ツリー配列にある4つの要素の1つが表示されています。
print_r（$ tree）を実行すると、（1 + 4 + 4 * 4 + 4 * 4 * 4）= 85要素、つまり340要素の4つのツリーの配列があることがわかります。 $ elem->データとして、そのレベルがあります。 このようなもの：
#.1
#.1.1
#.1.1.1
#.1.1.2
#.1.2
#.2
#.2.1
#.2.2
テーブルにデータを追加する
それらを挿入するために、insertTreeRecursive関数を作成しました。 要素ごとに、2つまたは3つのクエリが必要です。 1つは、Elementsテーブルにデータを挿入するため、1つは、ElementsHierarchyテーブルから親に関するデータを取得するため、1つは、親データをElementsHierarchyテーブルに挿入するためです。 さて、関数の例の詳細
ここまでは、重いものは何もないと思います。
$elem->setId(Db::execute($query));
テーブル `Elements`に行を挿入し、last_insert_idを取得して現在の要素に割り当てます。 挿入されたレコードIDが37だとしましょう
この要素に親がない場合、a laクエリはデータベースに行きます：
INSERT INTO `ElementsHierarchy`(`ElemID`,`ParentID`,`Level`) VALUES ('ID', NULL, 1)
つまり、要素が欠落要素の最初のレベル（NULL）にある、つまり、親がないことがわかります。
ただし、要素に親がある場合、親のすべての親のリストを取得します（たとえば、最も近い親のIDは15です）。 次のようになります。
各行で、ElemIDを現在の要素のIDに置き換え、レベルを1つ増やし、ID = 15とレベル= 1を配列の最後に追加します。| ElemID | ParentID | レベル|| 15 | NULL | 4 | | 15 | 1 | 3 | | 15 | 5 | 2 | | 15 | 10 | 1 |
次のものを入手しました。
これは、 `ElementsHierarchy`テーブルの最後に追加する構造です。 サイズが430要素の$ツリーでは、階層テーブルに1252行あります。 ネストの平均レベルが低いほど、テーブルは小さくなり、逆も同様です。 ネストの深さにもかかわらず、1つの要素を挿入するには3つの単純なクエリで十分です。| ElemID | ParentID | レベル|| 37 | NULL | 5 | | 37 | 1 | 4 | | 37 | 5 | 3 | | 37 | 10 | 2 | | 37 | 15 | 1 |
テーブルからデータを受け取ります
getRowsByParent関数を使用して、テーブルからデータを取得します。
$tree = getRowsByParent(2);
print_r($tree);
要素＃1.1と、サブセット＃1.1のツリー全体を推定したことがわかります。
しかし、「ParentID」は最も近い親ではなく、検索した親です。 したがって、リクエストをわずかに改善し、リクエストの結果をオブジェクトに発行するサイクルを作成します。 呼ぶ
必要なものを正確に入手できます！ 1つのSELECT！$tree = getTreeByParent(2);
print_r($tree);
わかりましたが、さらに見てみましょう。 しかし、UPDATEテーブルの作成方法は？ テストとして `Elements`テーブルに別のフィールドを追加しましょう：
ALTER TABLE `Elements` ADD `Marked` BOOL NOT NULL
そして、ツリー2の深さにあるすべてのセルをマークします。
getTreeByParent（2）; データベースを見て、すべてが判明したことを確認します。 取り外しはまったく同じように行われます。
この方法とマテリアライズドパスの比較
habrasocietyの提案で、このメソッドのベースとマテリアライズドパスメソッドからのサンプリング速度を比較するテストが行われました。 そして、私は非常に印象的な結果を持っています。 サイズが5 * 10の11111要素の10個の11110ツリー、つまりデータベース内の111110要素を生成し、それらに対してテストを行いました。20個のランダムIDを生成し、データベース内でそれらの下の完全なツリーを探しました。 その結果、すべての場合において、 フル階層はマテリアライズドパスよりも5〜8倍優れています（自分で確認でき、すべてのテストソースがレイアウトされています）。
pastebin.com/f65b2fb7d-テスト中に使用された関数。
pastebin.com/f793f7c74-テスト自体とその結果。
`ElementsMP`ベースの構造：
CREATE TABLE `ElementsMP` (
`ID` int (11) NOT NULL AUTO_INCREMENT,
` Data ` varchar (64) NOT NULL ,
` Path ` varchar (1000) CHARACTER SET latin1 COLLATE latin1_bin DEFAULT NULL ,
PRIMARY KEY (`ID`),
KEY ` Path ` (` Path `)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
* This source code was highlighted with Source Code Highlighter .
また、データベースでは、「パス」フィールドを1000文字より長くすることは許可されていません（＃1071-指定されたキーが長すぎました;キーの最大長は1000バイトです）。つまり、平均IDの長さが4文字の場合、 1000 /（4 + 1）よりも深いツリー、つまり、この場合の最も深いツリーは200要素です。 および平均キー長が5桁の166（サイトに平均50,000件を超えるコメントがある場合）
まとめ
上記のコードには独自の欠陥があるかもしれませんが、すべての欠陥は時間と経験で簡単に修正できると確信しています。 多くの人がこのメソッドを気に入ってくれたら、一緒になってライブラリを書いてもっと便利に作業できるようになると思います。
謝辞
テーマロゴを描いてくれたFreeCR ConfのDkZに感謝します。
このアイデアを私に押し付けてくれたKostyanに感謝します。