(超技術ネタ） B-TREEからノードを削除するアルゴリズム
2008年07月26日02:46
＊＊ B-TREEからノードを削除するアルゴリズム方法について考える日記 ＊＊
目的：B-TREEからノードを削除するアルゴリズム方法について考える
方法： wikiの説明 http://en.wikipedia.org/wiki/B-treeを 多少編集したうえで、翻訳してみる。
初学者はまず以下のビデオを見る。
以下、wiki の 翻訳を試みる。
--------------------------------------
英単語 一覧：
and so ＝ そこで だから
former 前者
latter 後者
as with ～のように
likewise 同様に
--------------------------------------
翻訳スタート！
ノードの構造
0. Each internal node's elements act as separation values which divide its subtrees.
0. それぞれのノード内に複数の数値を持っている。 また、ノードは更に下位のノードへの参照を持っている。 ノード内の複数の数値はそれぞれ、下位のノードを分割する値としての役割を果たしている。
1. Internal nodes in a B-tree nodes which are not leaf nodes are usually represented as an ordered set of elements and child pointers.
1. 末端のノードのことをリーフと呼ぶ。 また、リーフノードでないノードを中間ノードと呼ぶ。 中間ノードは、一般的に、その中間ノードの下位のノードへの参照と並べ替え済みの数値を代表した存在になる。
2. Every internal node contains a maximum of U children and other than the root a minimum of L children.
2. 全ての中間ノードは最大でＵ個の下位のノードを持ち、最小でＬ個の下位ノードを持つ。但し、ルートのみＬ個以下のノードは許される。
3. For all internal nodes other than the root, the number of elements is one less than the number of child pointers;
→ the number of elements is between L-1 and U-1.
3. ルートノードを除く全ての中間ノードにおいて、ノードが持つ数値の個数は下位ノードの個数から１引いた数になる。 よって、数値の個数は Ｌ－１とＵ－１の間の数値を取る。
4. The number U must be either 2L or 2L-1;
→ thus each internal node is at least half full.
4. Ｕは 必ず ２Ｌ または ２Ｌ－１ のどちらかになる。 よって、それぞれの中間ノードは、最低でも、最大個数Ｕの１／２以上の個数の数値を持つ。 以下、この状態を半満杯と呼ぶ。 また最大個数Ｕ個の数値を持つノードの状態を満杯と呼ぶ。
5. This relationship between U and L implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes (if there is room to push one element up into the parent).
5. このＵとＬの関係は、二つの「半満杯」のノードを結合するとひとつの合法なノードを作ることができると言うことや、１つの満杯なノードを分割することによって２つの合法なノードがつくられることを暗に表している。
6. These properties make it possible to delete and insert new values into a B-tree and adjust the tree to preserve the B-tree properties.
6. これらの性質は、あるひとつのB-treeに対して、合法的に数値の削除、新しい数値の追加、B-treeの性質を保存するための調整、という３つの作業を行うことを可能とする。
7. Leaf nodes have the same restriction on the number of elements, but have no children, and no child pointers.
7. リーフノードは、下位のノードを持たないこと以外は、中間ノードと同じ制約を持つ。
8. The root node still has the upper limit on the number of children, but has no lower limit. For example, when there are fewer than L-1 elements in the entire tree, the root will be the only node in the tree, and it will have no children at all.
8. ルートノードは下位ノードの最大数Ｕ個の制約は持っているが、最定数Ｕの制約は持たない。 例えば、Ｌ－１個よりも少ない個数の数値しか持たない場合、ルートノードは全体の構造の中で唯一のノードとなってしまうため、いずれにしても下位ノードは持つことができない。
A B-tree of depth n+1 can hold about U times as many items as a B-tree of depth n, but the cost of search, insert, and delete operations grows with the depth of the tree. As with any balanced tree, the cost grows much more slowly than the number of elements.
ｎ＋１ の深さを持つ B-treeは、約 ｎ×Ｕ 個の数値を持つが、検索・挿入・削除の各処理にかかる時間はツリーの深さと共に増加する。 バランスツリーと同様に、処理時間の増加スピードは、数値の個数の増加スピードより、ゆっくりとしている。
Some balanced trees store values only at the leaf nodes, and so have different kinds of nodes for leaf nodes and internal nodes.
ある種のバランスツリーは数値をリーフノードのみに保存しているが、B-treeでは、リーフノードや中間ノードにも値を保持している。
B-trees keep values in every node in the tree, and may use the same structure for all nodes. However, since leaf nodes never have children, a specialized structure for leaf nodes in B-trees will improve performance.
B-treeでは 全てのノードに値を保存しており、全てのノードは同じ構造を持っている。 しかしながら、リーフノードは下位のノードを持っていないため、リーフノードに対して特化した構造を与えることによって、B-treeのパフォーマンスは向上する。
--------------------------------------
Algorithms:Search
数値検索のアルゴリズム
Algorithms:Insertion
数値挿入のアルゴリズム
挿入・検索のアルゴリズムは翻訳するよりも以下のリンクを見たほうが理解し易いので、省略。
http://jp.youtube.com/watch?v=coRJrcIYbF4
http://slady.net/java/bt/view.php?w=450&h=300
--------------------------------------
Algorithms: Deletion
削除のアルゴリズム
There are two popular strategies for deletion from a B-Tree.
削除するための二つの方法が知られている。
1. locate and delete the item, then restructure the tree to regain its invariants
1. 該当するアイテムを検索後、削除する。 その後、残りのノードをツリーを再構築する。
2. do a single pass down the tree, but before entering (visiting) a node, restructure the tree so that once the key to be deleted is encountered, it can be deleted without triggering the need for any further restructuring
2. シングルパスダウン処理を行う。 但し、ノード追跡時、ノードに突入する前に、あらかじめ、削除すべき値が見つかってもそれ以上再構築が発生しないよう前もって再構築する。
The algorithm below uses the former strategy.
以下のアルゴリズムは前者の方法を利用する。
There are two special cases to consider when deleting an element:
削除する時に考えなければいけないケースは２つある。
1. the element in an internal node may be a separator for its child nodes.
1. 中間ノードが持っている数値が、分割値になる可能性がある場合。
2. deleting an element may put it under the minimum number of elements and children.
2. 数値を削除した結果、そのノードが最小の数値個数と下位ノード数しか持たない場合。
Each of these cases will be dealt with in order.
これらの問題は、次のように対処される。
1. Deletion from a leaf node
1. リーフノードから削除
1.1 Search for the value to delete.
1.1 削除すべき数値を検索する。
1.2 If the value is in a leaf node, it can simply be deleted from the node, perhaps leaving the node with too few elements; so some additional changes to the tree will be required.
1.2 もし、数値がリーフノードに合った場合、単純に削除できる。 場合によっては、規則よりも少なすぎる個数の数値のまま放置することになる。 そのような場合、あとで追加の処理が必要になる。
2. Deletion from an internal node
2. 中間ノードからの削除
Each element in an internal node acts as a separation value for two subtrees, and when such an element is deleted, two cases arise.
それぞれの中間ノード内に持っている数値は分割値としての役割を果たしているが、その様な数値が削除された場合、２つのケースが生じる。
In the first case, both of the two child nodes to the left and right of the deleted element have the minimum number of elements, namely L-1.
まず、最初のケースは、分割値を中央とした左右のノードが両方とも最小の個数（L-1）の数値しか持たないケースである。
They can then be joined into a single node with 2L-2 elements, a number which does not exceed U-1 and so is a legal node.
それらの数値は2L-2個の数値を持つ１つのノードにまとめることができる。 この時、2L-2は U-1を超えないため適格なノードとなる。
Unless it is known that this particular B-tree does not contain duplicate data, we must then also (recursively) delete the element in question from the new node.
新しく出来たノードから問題となる数値を再帰的に削除する必要がある。但し、この B-treeが 重複する数値を持っていないと前もってわかっている場合は不要。
In the second case, one of the two child nodes contains more than the minimum number of elements.
２番目のケースは、二つの下位ノードのうち、どちらか片方が最小の個数以上の数値を持っている場合である。
Then a new separator for those subtrees must be found.
その場合、新しい分割値を探し出す必要がある。
Note that the largest element in the left subtree is the largest element which is still less than the separator.
左側の下位ツリー内で最大の数値が 分割値よりも小さいことに注意。
Likewise, the smallest element in the right subtree is the smallest element which is still greater than the separator.
同様に、右側の下位ツリーでの最小の値が分割値よりも大きい。
Both of those elements are in leaf nodes, and either can be the new separator for the two subtrees.
それらの数値はリーフノードにあり、そのどちらもが新しい下位ツリーの分割値になれる。
1. if the value is in an internal node, choose a new separator (either the largest element in the left subtree or the smallest element in the right subtree), remove it from the leaf node it is in, and replace the element to be deleted with the new separator.
1. もし、目的の削除する数値が中間ノードの中にあった場合、新しい分割値を選ぶ。 その際、左側の下位ツリーの最大の数値を選んでも、右側下位ツリーの最小の数値を選んでもよい。 選んだ分割値をリーフノードから削除し、新しい分割値を目的の削除する数値と置き換える。
2. This has deleted an element from a leaf node, and so is now equivalent to the previous case.
2. ？？？
--------------------------------------
こ こ ま で
--------------------------------------
感想：
こうやって一通り読んでみると、案外冗長で読みにくい文章だったことがわかる。
以下の討論を読んでみると、その他色々な有用な情報が得られた。
http://en.wikipedia.org/wiki/Talk:B-tree
特に大学の先生が話している話はムチャムチャ興味深い。
I am teaching B-trees at San Jose State University. I have three sources (other than the Wikipedia article) that pairwise disagree on this L-U issue. Here are what they say:
(1) The well-known algorithms textbook, Introduction to Algorithms, by Corment, Leiserson, Rivest, and Stein (CLRS), defines B-trees in terms of one parameter t, the "minimal degree" (p. 439). Thus L = t and U = 2t. It is required that t be an integer, so in particular U has to be even.
(2) The B-tree animation applet of slady (linked from the article) also uses a single parameter, which he calls the "order". He doesn't explain it, but experiments with the applet give, for order 1, L=2 and U = 3, and for order 2, L=3 and U = 5. In particular you always get U odd, so the animation applet can't duplicate any of the trees discussed in CLRS. (Do you suppose this confuses my students?!)
(3) Knuth's "Art of Computer Programming", vol. 3, p. 473, defines B-trees in terms of the "order" m. Comparing it to the Wikipedia articla, we see U=m and L = ceiling(m/2); we need ceiling since m is not required to be even. So CLRS covers the case when m is even, m = 2t; but Knuth also allows the case L=t and U = 2t-1; this seems to be the case the applet covers, where the "order" you enter in the applet is t-1.
Some restriction on the relation between L and U has to be made; when we split a full node (containing U-1 elements) upon inserting a new key, we will get two new nodes containing U/2 elements each (for even U) or one with floor(U/2) and one with ceiling(U/2) elements, for odd U. We must require that L be at most floor(U/2) so that these nodes are legal. Moreover, L can't be too small either, or deletion won't work right. On 1 April 2006 I edited the article to correct this point, and also to correct the description of the deletion algorithm. --User and date unknown
ここらあたりからは、きちんと英語のコンピューターサイエンスの原書を読む必要がありそうだ。
目的：B-TREEからノードを削除するアルゴリズム方法について考える
方法： wikiの説明 http://en.wikipedia.org/wiki/B-treeを 多少編集したうえで、翻訳してみる。
初学者はまず以下のビデオを見る。
以下、wiki の 翻訳を試みる。
--------------------------------------
英単語 一覧：
and so ＝ そこで だから
former 前者
latter 後者
as with ～のように
likewise 同様に
--------------------------------------
翻訳スタート！
ノードの構造
0. Each internal node's elements act as separation values which divide its subtrees.
0. それぞれのノード内に複数の数値を持っている。 また、ノードは更に下位のノードへの参照を持っている。 ノード内の複数の数値はそれぞれ、下位のノードを分割する値としての役割を果たしている。
1. Internal nodes in a B-tree nodes which are not leaf nodes are usually represented as an ordered set of elements and child pointers.
1. 末端のノードのことをリーフと呼ぶ。 また、リーフノードでないノードを中間ノードと呼ぶ。 中間ノードは、一般的に、その中間ノードの下位のノードへの参照と並べ替え済みの数値を代表した存在になる。
2. Every internal node contains a maximum of U children and other than the root a minimum of L children.
2. 全ての中間ノードは最大でＵ個の下位のノードを持ち、最小でＬ個の下位ノードを持つ。但し、ルートのみＬ個以下のノードは許される。
3. For all internal nodes other than the root, the number of elements is one less than the number of child pointers;
→ the number of elements is between L-1 and U-1.
3. ルートノードを除く全ての中間ノードにおいて、ノードが持つ数値の個数は下位ノードの個数から１引いた数になる。 よって、数値の個数は Ｌ－１とＵ－１の間の数値を取る。
4. The number U must be either 2L or 2L-1;
→ thus each internal node is at least half full.
4. Ｕは 必ず ２Ｌ または ２Ｌ－１ のどちらかになる。 よって、それぞれの中間ノードは、最低でも、最大個数Ｕの１／２以上の個数の数値を持つ。 以下、この状態を半満杯と呼ぶ。 また最大個数Ｕ個の数値を持つノードの状態を満杯と呼ぶ。
5. This relationship between U and L implies that two half-full nodes can be joined to make a legal node, and one full node can be split into two legal nodes (if there is room to push one element up into the parent).
5. このＵとＬの関係は、二つの「半満杯」のノードを結合するとひとつの合法なノードを作ることができると言うことや、１つの満杯なノードを分割することによって２つの合法なノードがつくられることを暗に表している。
6. These properties make it possible to delete and insert new values into a B-tree and adjust the tree to preserve the B-tree properties.
6. これらの性質は、あるひとつのB-treeに対して、合法的に数値の削除、新しい数値の追加、B-treeの性質を保存するための調整、という３つの作業を行うことを可能とする。
7. Leaf nodes have the same restriction on the number of elements, but have no children, and no child pointers.
7. リーフノードは、下位のノードを持たないこと以外は、中間ノードと同じ制約を持つ。
8. The root node still has the upper limit on the number of children, but has no lower limit. For example, when there are fewer than L-1 elements in the entire tree, the root will be the only node in the tree, and it will have no children at all.
8. ルートノードは下位ノードの最大数Ｕ個の制約は持っているが、最定数Ｕの制約は持たない。 例えば、Ｌ－１個よりも少ない個数の数値しか持たない場合、ルートノードは全体の構造の中で唯一のノードとなってしまうため、いずれにしても下位ノードは持つことができない。
A B-tree of depth n+1 can hold about U times as many items as a B-tree of depth n, but the cost of search, insert, and delete operations grows with the depth of the tree. As with any balanced tree, the cost grows much more slowly than the number of elements.
ｎ＋１ の深さを持つ B-treeは、約 ｎ×Ｕ 個の数値を持つが、検索・挿入・削除の各処理にかかる時間はツリーの深さと共に増加する。 バランスツリーと同様に、処理時間の増加スピードは、数値の個数の増加スピードより、ゆっくりとしている。
Some balanced trees store values only at the leaf nodes, and so have different kinds of nodes for leaf nodes and internal nodes.
ある種のバランスツリーは数値をリーフノードのみに保存しているが、B-treeでは、リーフノードや中間ノードにも値を保持している。
B-trees keep values in every node in the tree, and may use the same structure for all nodes. However, since leaf nodes never have children, a specialized structure for leaf nodes in B-trees will improve performance.
B-treeでは 全てのノードに値を保存しており、全てのノードは同じ構造を持っている。 しかしながら、リーフノードは下位のノードを持っていないため、リーフノードに対して特化した構造を与えることによって、B-treeのパフォーマンスは向上する。
--------------------------------------
Algorithms:Search
数値検索のアルゴリズム
Algorithms:Insertion
数値挿入のアルゴリズム
挿入・検索のアルゴリズムは翻訳するよりも以下のリンクを見たほうが理解し易いので、省略。
http://jp.youtube.com/watch?v=coRJrcIYbF4
http://slady.net/java/bt/view.php?w=450&h=300
--------------------------------------
Algorithms: Deletion
削除のアルゴリズム
There are two popular strategies for deletion from a B-Tree.
削除するための二つの方法が知られている。
1. locate and delete the item, then restructure the tree to regain its invariants
1. 該当するアイテムを検索後、削除する。 その後、残りのノードをツリーを再構築する。
2. do a single pass down the tree, but before entering (visiting) a node, restructure the tree so that once the key to be deleted is encountered, it can be deleted without triggering the need for any further restructuring
2. シングルパスダウン処理を行う。 但し、ノード追跡時、ノードに突入する前に、あらかじめ、削除すべき値が見つかってもそれ以上再構築が発生しないよう前もって再構築する。
The algorithm below uses the former strategy.
以下のアルゴリズムは前者の方法を利用する。
There are two special cases to consider when deleting an element:
削除する時に考えなければいけないケースは２つある。
1. the element in an internal node may be a separator for its child nodes.
1. 中間ノードが持っている数値が、分割値になる可能性がある場合。
2. deleting an element may put it under the minimum number of elements and children.
2. 数値を削除した結果、そのノードが最小の数値個数と下位ノード数しか持たない場合。
Each of these cases will be dealt with in order.
これらの問題は、次のように対処される。
1. Deletion from a leaf node
1. リーフノードから削除
1.1 Search for the value to delete.
1.1 削除すべき数値を検索する。
1.2 If the value is in a leaf node, it can simply be deleted from the node, perhaps leaving the node with too few elements; so some additional changes to the tree will be required.
1.2 もし、数値がリーフノードに合った場合、単純に削除できる。 場合によっては、規則よりも少なすぎる個数の数値のまま放置することになる。 そのような場合、あとで追加の処理が必要になる。
2. Deletion from an internal node
2. 中間ノードからの削除
Each element in an internal node acts as a separation value for two subtrees, and when such an element is deleted, two cases arise.
それぞれの中間ノード内に持っている数値は分割値としての役割を果たしているが、その様な数値が削除された場合、２つのケースが生じる。
In the first case, both of the two child nodes to the left and right of the deleted element have the minimum number of elements, namely L-1.
まず、最初のケースは、分割値を中央とした左右のノードが両方とも最小の個数（L-1）の数値しか持たないケースである。
They can then be joined into a single node with 2L-2 elements, a number which does not exceed U-1 and so is a legal node.
それらの数値は2L-2個の数値を持つ１つのノードにまとめることができる。 この時、2L-2は U-1を超えないため適格なノードとなる。
Unless it is known that this particular B-tree does not contain duplicate data, we must then also (recursively) delete the element in question from the new node.
新しく出来たノードから問題となる数値を再帰的に削除する必要がある。但し、この B-treeが 重複する数値を持っていないと前もってわかっている場合は不要。
In the second case, one of the two child nodes contains more than the minimum number of elements.
２番目のケースは、二つの下位ノードのうち、どちらか片方が最小の個数以上の数値を持っている場合である。
Then a new separator for those subtrees must be found.
その場合、新しい分割値を探し出す必要がある。
Note that the largest element in the left subtree is the largest element which is still less than the separator.
左側の下位ツリー内で最大の数値が 分割値よりも小さいことに注意。
Likewise, the smallest element in the right subtree is the smallest element which is still greater than the separator.
同様に、右側の下位ツリーでの最小の値が分割値よりも大きい。
Both of those elements are in leaf nodes, and either can be the new separator for the two subtrees.
それらの数値はリーフノードにあり、そのどちらもが新しい下位ツリーの分割値になれる。
1. if the value is in an internal node, choose a new separator (either the largest element in the left subtree or the smallest element in the right subtree), remove it from the leaf node it is in, and replace the element to be deleted with the new separator.
1. もし、目的の削除する数値が中間ノードの中にあった場合、新しい分割値を選ぶ。 その際、左側の下位ツリーの最大の数値を選んでも、右側下位ツリーの最小の数値を選んでもよい。 選んだ分割値をリーフノードから削除し、新しい分割値を目的の削除する数値と置き換える。
2. This has deleted an element from a leaf node, and so is now equivalent to the previous case.
2. ？？？
--------------------------------------
こ こ ま で
--------------------------------------
感想：
こうやって一通り読んでみると、案外冗長で読みにくい文章だったことがわかる。
以下の討論を読んでみると、その他色々な有用な情報が得られた。
http://en.wikipedia.org/wiki/Talk:B-tree
特に大学の先生が話している話はムチャムチャ興味深い。
I am teaching B-trees at San Jose State University. I have three sources (other than the Wikipedia article) that pairwise disagree on this L-U issue. Here are what they say:
(1) The well-known algorithms textbook, Introduction to Algorithms, by Corment, Leiserson, Rivest, and Stein (CLRS), defines B-trees in terms of one parameter t, the "minimal degree" (p. 439). Thus L = t and U = 2t. It is required that t be an integer, so in particular U has to be even.
(2) The B-tree animation applet of slady (linked from the article) also uses a single parameter, which he calls the "order". He doesn't explain it, but experiments with the applet give, for order 1, L=2 and U = 3, and for order 2, L=3 and U = 5. In particular you always get U odd, so the animation applet can't duplicate any of the trees discussed in CLRS. (Do you suppose this confuses my students?!)
(3) Knuth's "Art of Computer Programming", vol. 3, p. 473, defines B-trees in terms of the "order" m. Comparing it to the Wikipedia articla, we see U=m and L = ceiling(m/2); we need ceiling since m is not required to be even. So CLRS covers the case when m is even, m = 2t; but Knuth also allows the case L=t and U = 2t-1; this seems to be the case the applet covers, where the "order" you enter in the applet is t-1.
Some restriction on the relation between L and U has to be made; when we split a full node (containing U-1 elements) upon inserting a new key, we will get two new nodes containing U/2 elements each (for even U) or one with floor(U/2) and one with ceiling(U/2) elements, for odd U. We must require that L be at most floor(U/2) so that these nodes are legal. Moreover, L can't be too small either, or deletion won't work right. On 1 April 2006 I edited the article to correct this point, and also to correct the description of the deletion algorithm. --User and date unknown
ここらあたりからは、きちんと英語のコンピューターサイエンスの原書を読む必要がありそうだ。
コメント一覧
