階層構造の取扱い

データベースに階層的なデータを格納する †

Storing Hierarchical Data in a Database

http://www.sitepoint.com/article/hierarchical-data-database/

http://www.sitepoint.com/article/hierarchical-data-database/2

http://www.sitepoint.com/article/hierarchical-data-database/3

Storing Hierarchical Data in a Database

データベースに階層的なデータを格納します。

By Gijs Van Tulder

ハイスヴァントゥルデル著

April 30th 2003

2003年4月30日

Gijs Van Tulder

Gijs is a full time Dutch student in economics and a spare time Web developer.
He spends his time developing scripts using PHP, MySQL and other external programs.
Visit him at http://gvtulder.f2o.org/

Whether you want to build your own forum, publish the messages from a mailing list on your Website, or write your own cms: there will be a moment that you'll want to store hierarchical data in a database.
And, unless you're using a XML-like database, tables aren't hierarchical; they're just a flat list.
You'll have to find a way to translate the hierarchy in a flat file.

あなたが自分用の会議場を作りたいとか、自分のサイトのメーリングリストにメッセージを発表したいとか、自分のCMSに書き込みしたいとか、いずれにしても、データベースに階層的なデータを格納したい時があるでしょう。
そして、あなたがXMLデータベースを使用していない限り、テーブルは階層的になっておらず、単層的(注:flat)なリストになっています。
あなたは、階層構造を単層的なファイルに変形する方法を見つけなければならないでしょう。

Storing trees is a common problem, with multiple solutions.
There are two major approaches: the adjacency list model, and the modified preorder tree traversal algorithm.

ツリー(注:樹形のデータ構造)を格納することは、複数の解決方法がある一般的な問題です。
2つの主要なアプローチがあり、それは隣接リストモデルと、修飾されたツリーの前順走査(木の幹からの探索)アルゴリズムです。

In this article, we'll explore these two methods of saving hierarchical data.
I'll use the tree from a fictional online food store as an example.
This food store organizes its food by category, by colour and by type.
The tree looks like this:

この記事では、階層的なデータを保存する二つの方法を探究します。例として、架空のオンライン食品店を引用して、ツリーを使ってみます。この食品店は、カテゴリー、色、タイプによって、食品を整理しています。このツリーは、次のようになっています。

This article contains a number of code examples that show how to save and retrieve data.
Because I use that language myself, and many other people use or know that language too, I chose to write the examples in PHP.
You can probably easily translate them to your own language of choice.

この記事には、どのようにデータを保存して検索するかを示す、多くのコードの例を含んでいます。私が自分でその言語を使っていて、他の多くの人々がその言語を使っているか知っているという理由で、私はPHPで例を書くことを選びました。あなたはたぶん簡単にそれらを、あなた自身が選択した言語に翻訳することができます。

↑

隣接リストモデル †

The Adjacency List Model

The first, and most elegant, approach we'll try is called the 'adjacency list model' or the 'recursion method'.
It's an elegant approach because you'll need just one, simple function to iterate through your tree.
In our food store, the table for an adjacency list looks like this:

私たちが試みる最初の上品なアプローチは、「隣接モデルリスト」または「再帰法」というものです。それは、あなたが必要とする、ツリーによる繰返しの簡潔な機能なので、上品なアプローチです。私たちの食品店では、隣接リストのためのテーブルが次のようになります。

As you can see, in the adjacency list method, you save the 'parent' of each node.
We can see that 'Pear' is a child of 'Green', which is a child of 'Fruit' and so on.
The root node, 'Food', doesn't have a parent value.
For simplicity, I've used the 'title' value to identify each node.
Of course, in a real database, you'd use the numerical id of each node.

お分かりのように、隣接リスト法で、あなたはそれぞれのノードの「親」を保存しておきます。「梨(Pear)」は「緑(Green)」の子供であり、「緑」は「果物(Fruit)」の子供である、等が分かります。根本のノード「食品(Food)」は、親の値を持っていません。単純に、「タイトル」値を各ノードの識別のために使います。もちろん、実際のデータベースの中では、各ノードの数値IDを使います。

↑

ツリーを用意 †

Give Me the Tree

Now that we've inserted our tree in the database, it's time to write a display function.
This function will have to start at the root node -- the node with no parent -- and should then display all children of that node.
For each of these children, the function should retrieve and display all the child nodes of that child.
For these children, the function should again display all children, and so on.

ツリーをデータベースに追加したので、表示する関数を書くべき時です。この関数は、根のノード―親のいないノード―からスタートしなければならないでしょう。そして次に、そのノードの全ての子を表示するべきです。各々の子に対して、関数は、その子の全ての子ノードを検索して、表示するべきです。それらの子に対して、関数は全ての子をさらに表示するべきです。

As you might have noticed, there's a regular pattern in the description of this function.
We can simply write one function, which retrieves the children of a certain parent node.
That function should then start another instance of itself for each of these children, to display all their children.
This is the recursive mechanism that gives the 'recursion method' its name.

お気付きのように、この関数の記述には規則的なパターンがあります。私たちは簡潔に、ある親ノードの子を検索する一つの関数を書けます。関数は、すべての子を表示するために、各子ノードに対して、子ノードのもう一つ別のインスタンスを作るべきです。これは「再帰法」という名の再帰的なメカニズムです。

<?php 
// $parent is the parent of the children we want to see 
// $parent は見たい子の親です。
// $level is increased when we go deeper into the tree,
//        used to display a nice indented tree
// $level は、適切に字下げされたツリーを表示するために使われ、
//ツリーに深くに入るほど増加されます。
function display_children($parent, $level) { 
   // retrieve all children of $parent 
   // $parent の全ての子を検索 
   $result = mysql_query('SELECT title FROM tree '.
                          'WHERE parent="'.$parent.'";');

   // display each child 
   // 各々の子を表示
   while ($row = mysql_fetch_array($result)) { 
       // indent and display the title of this child 
       // 子のタイトルを字下げして表示 
       echo str_repeat('  ',$level).$row['title']."\n"; 

       // call this function again to display this 
       // child's children
       // 子の子を表示するために関数を再呼出し
       display_children($row['title'], $level+1); 
   } 
} 
?>

To display our whole tree, we'll run the function with an empty string as $parent and $level = 0: display_children('',0); For our food store tree, the function returns:

全体のツリーを表示するために、$parentを空の文字列に、$levelを0にして、関数を実行します。つまり、display_children('',0)にします。食品店のツリーに対して、関数は以下のように返します。

Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork

食物
果物
赤
チェリー
黄色
バナナ
肉
牛肉
豚肉

Note that if you just want to see a subtree, you can tell the function to start with another node. For example, to display the 'Fruit' subtree, you would run display_children('Fruit',0);

あなたがサブツリーを見たいなら、関数に対して別のノードから始めるように指示できることに注意してください。例えば、「フルーツ」のサブツリーを表示するために、あなたは、display_children('Fruit',0);と実行するでしょう。

↑

ノードへの経路 †

The Path to a Node

With almost the same function, it's possible to look up the path to a node if you only know the name or id of that node.
For instance, the path to 'Cherry' is 'Food' > 'Fruit' > 'Red'.
To get this path, our function will have to start at the deepest level: 'Cherry'.
It then looks up the parent of this node and adds this to the path.
In our example, this would be 'Red'.
If we know that 'Red' is the parent of 'Cherry', we can calculate the path to 'Cherry' by using the path to 'Red'.
And that's given by the function we've just used: by recursively looking up parents, we'll get the path to any node in the tree.

ほとんど同じ関数で、あなたがノードの名前かidを知っていれば、そのノードへの経路を探すことが可能です。例えば、「チェリー」への経路は、「フード」>「フルーツ」>「赤」です。この経路を得るために、私たちの関数は、「チェリー」という最も深いレベルから開始しなければならないでしょう。それは、次に、このノードの親を訪ねて、経路にこれを加えます。私たちの例では、これは「赤」でしょう。もし「赤」が「チェリー」の親であることを知れば、「赤」への経路を使って、「チェリー」への経路を計算できます。再帰的に親を探すことによって、ツリー中のあらゆるノードの経路を得ることが、今まで使ってきた関数でもたらされます。

<?php 
// $node is the name of the node we want the path of 
function get_path($node) { 
   // look up the parent of this node 
   $result = mysql_query('SELECT parent FROM tree '. 
                          'WHERE title="'.$node.'";'); 
   $row = mysql_fetch_array($result); 

   // save the path in this array 
   $path = array(); 

   // only continue if this $node isn't the root node 
   // (that's the node with no parent) 
   if ($row['parent']!='') { 
       // the last part of the path to $node, is the name 
       // of the parent of $node 
       $path[] = $row['parent']; 

       // we should add the path to the parent of this node 
       // to the path 
       $path = array_merge(get_path($row['parent']), $path); 
   } 

   // return the path 
   return $path; 
} 
?>

This function now returns the path to a given node.
It returns that path as an array, so to display the path we can use print_r(get_path('Cherry')); If you do this for 'Cherry', you'll see:

この関数は、今や、与えられたノードへの経路を返します。それは、配列として経路を返すので、経路を表示するために、print_r(get_path('Cherry'));を使うことができます。もしあなたがこれを「チェリー」に対してなしたら、あなたは次のような結果を見るでしょう。

Array 
( 
   [0] => Food 
   [1] => Fruit 
   [2] => Red 
)

↑

不都合 †

Disadvantages

As we've just seen, this is a great method.
It's easy to understand, and the code we need is simple, too.
What then, are the downsides of the adjacency list model?
In most programming languages, it's slow and inefficient.
This is mainly caused by the recursion.
We need one database query for each node in the tree.

私たちが見てきたように、これは優れた方法です。理解することが簡単で、必要なコードも単純です。それなら、隣接リストモデルのマイナス面は何でしょうか？ほとんどのプログラミング言語で、遅くて非能率的なことです。これは主に、再帰によって引き起こされます。ツリー中の各ノードごとに、1回のデータベースクエリーが必要になります。

As each query takes some time, this makes the function very slow when dealing with large trees.

各クエリーにある程度の時間がかかることが、大きなツリーを処理するとき、この関数を非常に遅くさせます。

The second reason this method isn't that fast, is the programming language you'll probably use.
Unlike languages such as Lisp, most languages aren't designed for recursive functions.
For each node, the function starts another instance of itself.
So, for a tree with four levels, you'll be running four instances of the function at the same time.
As each function occupies a slice of memory and takes some time to initiate, recursion is very slow when applied to large trees.

この方法が速くない2番目の理由は、あなたの使うプログラミング言語です。Lispのような言語と違って、たいていの言語は再帰関数のために設計されていません。それぞれのノードに対して、関数は、自分のもう一つのインスタンスを開始します。したがって、4階層のツリーに対しては、同時に4個の関数のインスタンスを実行するでしょう。それぞれの関数がメモリの一部分を確保して、さらに初期化するためにある程度の時間を要するので、再帰は大きなツリーに用いられる場合にはとても遅いです。

↑

修正された前順走査のツリー移動 (木の幹からの探索) †

Modified Preorder Tree Traversal

Now, let's have a look at another method for storing trees.
Recursion can be slow, so we would rather not use a recursive function.
We'd also like to minimize the number of database queries.
Preferably, we'd have just one query for each activity.

今、木を蓄える別の方法をちょっと見ましょう。
回帰は遅いことができます、それで、私たちは、むしろ帰納的な機能を使わないでしょう。
私たちは、データベース質問の数を最小限にすることがまた好きでしょう。
できれば、私たちは、それぞれの活動のためのただの1つの質問を持っているでしょう。

We'll start by laying out our tree in a horizontal way.
Start at the root node ('Food'), and write a 1 to its left.
Follow the tree to 'Fruit' and write a 2 next to it.
In this way, you walk (traverse) along the edges of the tree while writing a number on the left and right side of each node.
The last number is written at the right side of the 'Food' node. In this image, you can see the whole numbered tree, and a few arrows to indicate the numbering order.

私たちは、地平線の方法で私たちの木をレイアウトすることから始めるでしょう。根節(「食べ物」)で始まって、そしてそれの左側へ1を書いて下さい。「果物」まで木の後ろについていって、そしてそれの隣に2を書いて下さい。このように、左側の数字と右のそれぞれの節の横腹を書いている間に、あなたは、木の端に沿って(走査)歩きます。最後の数字は、「食べ物」節の右側で書かれます。このイメージで、あなたは、数えられている順序を示すために、全く限られている木と少しの矢を見ることができます。

We'll call these numbers left and right (e.g. the left value of 'Food' is 1, the right value is 18).
As you can see, these numbers indicate the relationship between each node.
Because 'Red' has the numbers 3 and 6, it is a descendant of the 1-18 'Food' node.
In the same way, we can say that all nodes with left values greater than 2 and right values less than 11, are descendants of 2-11 'Fruit'.
The tree structure is now stored in the left and right values.
This method of walking around the tree and counting nodes is called the 'modified preorder tree traversal' algorithm.

私たちは、これらの数字を左であって、正しい(例えば「食べ物」の左側価値、1、正しい価値が18だということである)と思うでしょう。あなたが見ることができるので、これらの数字は、それぞれの節における関係を示します。「赤」が3番および6を持っているので、それは、1-18の「食べ物」節の子孫です。同じように、私たちは、左の価値が2と右が11未満を評価するよりもすばらしい状態で、すべてがうなずくことが2-11「果物」の子孫だと言うことができます。木構造は、左側と正しい価値で今、しまっておかれます。図表のあたりに歩いて節を数えることのこの方法が呼ばれますその’修正します木移動のアルゴリズムを前注文して下さい。

Before we continue, let's see how these values look in our table:

私たちが続く前に、どのようにこれらの価値が私たちのテーブルをのぞいて見るかを確認しましょう:

Note that the words 'left' and 'right' have a special meaning in SQL.
Therefore, we'll have to use 'lft' and 'rgt' to identify the columns.
Also note that we don't really need the 'parent' column anymore.
We now have the lft and rgt values to store the tree structure.

その単語が「去って」、そして「正しく」SQLで意味しているスペシャルを持っていることに注意して下さい。
それゆえに、私たちは、コラムを明らかにするために「lft」と「rgt」を使う必要があるでしょう。
私たちが実は今はもう「親」コラムを必要としないとまた述べて下さい。
私たちは、木構造をしまっておくために、lftとrgt価値を今、持っています。

↑

木を回収して下さい †

Retrieve the Tree

If you want to display the tree using a table with left and right values, you'll first have to identify the nodes that you want to retrieve.
For example, if you want the 'Fruit' subtree, you'll have to select only the nodes with a left value between 2 and 11.
In SQL, that would be:

もし左のまた正しい価値でテーブルを利用した木を展示したければ、あなたは、初めにそれ持ってきたい節を明らかにする必要があるでしょう。
例えば、もし「果物」subtreeが欲しければ、あなたは、2と11の間に左の価値で節だけを選ぶ必要があるでしょう。
SQLで、それはあるでしょう:

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

That returns:

それは戻ります:

Well, there it is: a whole tree in one query.
To display this tree like we did our recursive function, we'll have to add an ORDER BY clause to this query.
If you add and delete rows from your table, your table probably won't be in the right order.
We should therefore order the rows by their left value.

まあ、そこにそれがあります:1つの質問のすべての木。
私たちの帰納的な機能をしたようにこの木を展示するために、私たちは、この質問への節によって順序を加える必要があるでしょう。
もしあなたがあなたのテーブルから列を加えて削除すれば、あなたのテーブルは、たぶん、権利で順序でないでしょう。
私たちは、彼らの左の価値によって列をそれゆえに命令すべきです。

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;

The only problem left is the indentation.

唯一の問題左方は、ギザギザです。

To show the tree structure, children should be indented slightly more than their parent.
We can do this by keeping a stack of right values.
Each time you start with the children of a node, you add the right value of that node to the stack.
You know that all children of that node have a right value that is less than the right value of the parent, so by comparing the right value of the current node with the last right node in the stack, you can see if you're still displaying the children of that parent.
When you're finished displaying a node, you remove its right value from the stack.
If you count the elements in the stack, you'll get the level of the current node.

木構造を見せるために、子供は、わずかに彼らの親よりも多くへこむべきです。
私たちは、たくさんの正しい価値を保つことによってこれをすることができます。
節の子供から始めるたびに、あなたは、稲むらにその節の正しい価値を加えます。
あなたは、その節のすべての子供が権利よりも少なく親の価値である正しい価値を持っていることを知っています、それで、稲むらで最後の右の結節で現在の節の正しい価値を比べることによって、あなたは、まだその親の子供を展示しているかを確認することができます。
節を展示して終えられるときに、あなたは、稲むらからその正しい価値を取り去ります。
もし稲むらで原理を数えれば、あなたは、現在の節の水準を得るでしょう。

<?php 
function display_tree($root) { 
  // retrieve the left and right value of the $root node 
  $result = mysql_query('SELECT lft, rgt FROM tree '. 
                         'WHERE title="'.$root.'";'); 
  $row = mysql_fetch_array($result); 

  // start with an empty $right stack 
  $right = array(); 

  // now, retrieve all descendants of the $root node 
  $result = mysql_query('SELECT title, lft, rgt FROM tree '. 
                         'WHERE lft BETWEEN '.$row['lft'].' AND '. 
                         $row['rgt'].' ORDER BY lft ASC;'); 

  // display each row 
  while ($row = mysql_fetch_array($result)) { 
      // only check stack if there is one 
      if (count($right)>0) { 
          // check if we should remove a node from the stack 
          while ($right[count($right)-1]<$row['rgt']) { 
              array_pop($right); 
          } 
      } 

      // display indented node title 
      echo str_repeat('  ',count($right)).$row['title']."\n"; 

      // add this node to the stack 
      $right[] = $row['rgt']; 
  } 
} 
?>

If you run this code, you'll get exactly the same tree as with the recursive function discussed above.
Our new function will probably be faster: it isn't recursive and it only uses two queries.

もしこのコードを走らせれば、あなたは、上の機能が議論した帰納的であることとちょうど同じ木を得るでしょう。
私たちの新しい機能は、たぶんより速いでしょう:それは帰納的でなく、そして、それは2つの質問を単に使います。

↑

節への道 †

The Path to a Node

With this new algorithm, we'll also have to find a new way to get the path to a specific node.
To get this path, we'll need a list of all ancestors of that node.

この新しいアルゴリズムで、私たちは、特定の節への道を得る新しい方法を見つける必要がまたあるでしょう。
この道を得るために、私たちは、その節のすべての先祖のリストを必要とするでしょう。

With our new table structure, that really isn't much work.
When you look at, for example, the 4-5 'Cherry' node, you'll see that the left values of all ancestors are less than 4, while all right values are greater than 5.
To get all ancestors, we can use this query:

私たちの新しいテーブル構造で、それは本当に多くの仕事ではありません。
あなたが4-5つの「サクランボ」節を、例えば、見るときに、あなたがすべての先祖の左側価値が4未満であることを確認するでしょうが，一方で，すべての正しい価値は、5よりも重大です。
すべての先祖を得るために、私たちはこの質問を使うことができます:

SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

Note that, just like in our previous query, we have to use an ORDER BY clause to sort the nodes.
This query will return:

私たちの前の質問で、私たちが節によって順序を使う必要があるようにそれを書きとめて節を分類して下さい。
この質問は戻るでしょう:

+-------+
| title |
+-------+
| Food  |
| Fruit |
| Red   |
+-------+

We now only have to join the rows to get the path to 'Cherry'.

私たちは、「サクランボ」への道を得るために、今、列に加わるだけでよいです。

↑

何人の子孫 †

How Many Descendants

If you give me the left and right values of a node, I can tell you how many descendants it has by using a little math.

もしあなたが私に節の左側と正しい価値を与えれば、私は、あなたに、いくつの子孫をそれが少しの数学を使うことによって持っているかを話すことができます。

As each descendant increments the right value of the node with 2, the number of descendants can be calculated with:

それぞれ降下性の増加として、2をもつ節の正しい価値、以下で子孫の数が計算されることができます:

descendants = (right - left - 1) / 2

With this simple formula, I can tell you that the 2-11 'Fruit' node has 4 descendant nodes and that the 8-9 'Banana' node is just a child, not a parent.

この単純な公式で、私は、あなたに，2-11の「果物」節が4つの子孫節を持っている、および8-9つの「バナナ」節がちょうど親ではなく子供だと話すことができます。

↑

木移動を自動化して †

Automating the Tree Traversal

Now that you've seen some of the handy things you can do with this table, it's time to learn how we can automate the creation of this table.
While it's a nice exercise the first time and with a small tree, we really need a script that does all this counting and tree walking for us.

あなたがこのテーブルであなたがすることができるその便利な物の一部を見たので、どのように私たちがこのテーブルの創造を自動化することができるかを知る時間です。
それが初めてと小さい木で素晴らしい運動である間、私たちは、すべてのこの数えることをする台本と私たちのために歩いている木を本当に必要とします。

Let's write a script that converts an adjacency list to a modified preorder tree traversal table.

それが隣接リストを変える台本を書きましょうひとつの修正します木移動テーブルを前注文して下さい。

<?php 
function rebuild_tree($parent, $left) { 
  // the right value of this node is the left value + 1 
  $right = $left+1; 

  // get all children of this node 
  $result = mysql_query('SELECT title FROM tree '. 
                         'WHERE parent="'.$parent.'";'); 
  while ($row = mysql_fetch_array($result)) { 
      // recursive execution of this function for each 
      // child of this node 
      // $right is the current right value, which is 
      // incremented by the rebuild_tree function 
      $right = rebuild_tree($row['title'], $right); 
  } 

  // we've got the left value, and now that we've processed 
  // the children of this node we also know the right value 
  mysql_query('UPDATE tree SET lft='.$left.', rgt='. 
               $right.' WHERE title="'.$parent.'";'); 

  // return the right value of this node + 1 
  return $right+1; 
} 
?>

This is a recursive function.
You should start it with rebuild_tree('Food',1);
The function then retrieves all children of the 'Food' node.

これは帰納的な機能です。
あなたがそれを始めるべきですで(「食べ物」、1)_木を再建して下さい;
機能は、「食べ物」節のすべての子供をその時に回収します。

If there are no children, it sets its left and right values.
The left value is given, 1, and the right value is the left value plus one.
If there are children, this function is repeated and the last right value is returned.
That value is then used as the right value of the 'Food' node.

もしそこにが決して子供でなければ、それは、その左のまた正しい価値をセットします。
価値が与えられる左側、1と正しい価値は、プラスの1人左側価値です。
もし子供がいれば、この機能は繰り返され、そして、最後の正しい価値は、返されます。
その価値は、「食べ物」節の正しい価値としてその時に使われます。

The recursion makes this a fairly complex function to understand.
However, this function achieves the same result we did by hand at the beginning of this section.
It walks around the tree, adding one for each node it sees.
After you've run this function, you'll see that the left and right values are still the same (a quick check: the right value of the root node should be twice the number of nodes).

回帰は、理解するために、これをとても複雑な機能にします。
しかし、この機能は、この部分の始まりで手で私たちがしたという同じ結果を成し遂げます。
それが見るそれぞれの節のために1人を足して、それは図表のあたりに歩きます。
この機能を走らせた後で、あなたは、左側と正しい価値がまだ同じであることを確認するでしょう(速いチェック:根節の正しい価値は、2度節の数であるべきです)。

↑

節を加えること †

Adding a Node

How do we add a node to the tree?
There are two approaches: you can keep the parent column in your table and just rerun the rebuild_tree() function

a simple but not that elegant function;
or you can update the left and right values of all nodes at the right side of the new node.

どのように私たちは、木に節を加えますか?
2つの申し出があります:あなたがあなたのテーブルとただの再上映の親コラムを保つことができますその_木を再建して下さい()機能

薬草(しかしその上品な機能ではない);
あるいは、あなたは、新しい節の右側ですべての節の左側と正しい価値を更新することができます。

The first option is simple.
You use the adjacency list method for updating, and the modified preorder tree traversal algorithm for retrieval.
If you want to add a new node, you just add it to the table and set the parent column.
Then, you simply rerun the rebuild_tree() function.
This is easy, but not very efficient with large trees.

最初のオプションは単純です。
あなたは、更新する隣接リスト方法を使います、そして、修正されたことは、情報検索のための木移動アルゴリズムを前注文します。
もし新しい節を加えたければ、あなたは、テーブルにそれをちょうど加えて、そして親コラムをセットしました。
その時に、あなたが単に再上映しますその_木を再建して下さい()作用して下さい。
これは、大樹で簡単な、しかしとても能率的ではありません。

The second way to add, and delete nodes is to update the left and right values of all nodes to the right of the new node.
Let's have a look at an example.
We want to add a new type of fruit, a 'Strawberry', as the last node and a child of 'Red'.
First, we'll have to make some space.
The right value of 'Red' should be changed from 6 to 8, the 7-10 'Yellow' node should be changed to 9-12 etc.
Updating the 'Red' node means that we'll have to add 2 to all left and right values greater than 5.

節を加えて削除する第2の方法は、新しい節の右側にすべての節の左側と正しい価値を更新することです。
例をちょっと見ましょう。
私たちは、最後の節としての果物、「イチゴ」、と「赤」の子供の新しい一種を加えたいです。
第1に、私たちは、ある空間を作る必要があるでしょう。
「赤」の正しい価値は、6から8に変えられるべきです、7-10の「黄色」節は、私たちが5よりもうまくすべての左のまた正しい価値に2を加える必要があるだろう9-12などの「赤」節方法を更新することに変わるべきです。

We'll use the query:

私たちは質問を使うでしょう:

UPDATE tree SET rgt=rgt+2 WHERE rgt>5; 
UPDATE tree SET lft=lft+2 WHERE lft>5;

Now we can add a new node 'Strawberry' to fill the new space. This node has left 6 and right 7.

私たちが新しい節「イチゴ」を加えることができる今は、新しい空間を満たします。この節は、6と右7を去りました。

INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';

If we run our display_tree() function, we'll see that our new 'Strawberry' node has been successfully inserted into the tree:

私たちが私たちの表示_木を走らせるか()機能、私たちは、私たちの新しい「イチゴ」節が木へうまく挿入されたことを確認するでしょう:

Food 
 Fruit 
   Red 
     Cherry 
     Strawberry 
   Yellow 
     Banana 
 Meat 
   Beef 
   Pork

↑

不利 †

Disadvantages

At first, the modified preorder tree traversal algorithm seems difficult to understand.
It certainly is less simple than the adjacency list method. However, once you're used to the left and right properties, it becomes clear that you can do almost everything with this technique that you could do with the adjacency list method, and that the modified preorder tree traversal algorithm is much faster.
Updating the tree takes more queries, which is slower, but retrieving the nodes is achieved with only one query.

はじめは、修正されたことは、移動アルゴリズムが理解するために難しいようである木を前注文します。
それは、隣接リスト方法よりも確かにあまり単純ではありません。しかし、一旦あなたが左側と正しい所有物に慣れているならば、あなたが隣接リスト方法であなたがすることができたことがするこのテクニックですべてをほとんどすることができることがはっきりするようになる、および修正されたことが木移動アルゴリズムを前注文することは、はるかに速いです。
木がより多くの詰問をすることを更新して、どちらがより遅いかしかし節を回収することは、1つの質問だけで成し遂げられます。

↑

結論 †

Conclusion

You're now familiar with both ways to store trees in a database.
While I have a slight preference for the modified preorder tree traversal, in your particular situation the adjacency list method might be better.
I'll leave that to your own judgement.

あなたは、今、木をデータベースに保存する両方の方法をよく知っています。
私は僅かな好みを持っていて、なぜなら、修正されたことが木移動を前注文する間、あなたの特定の状況で、隣接リスト方法は、より良いでしょう。
私は、それをあなた自身の判決に委ねるでしょう。

One last note: as I've already said I don't recommend that you use the title of a node to refer to that node.
You really should follow the basic rules of database normalization.
I didn't use numerical ids because that would make the examples less readable.

1枚の最新(最後)のメモ:私がすでに言ったように、私は、その節を参照するために、あなたが節のタイトルを使うことを勧めません。
あなたは、データベース正常化の基本的原則に本当に従うべきです。
私は、それが例をあまり読みやすくなくしたので数のidsを使いませんでした。

↑