(激ムズ技術メモ）英語版 wiki での B-tree 説明の翻訳
2008年08月01日05:10
僕は相変わらずB-treeについて研究している。 昨日は、朝まで作業して、そのまま寝ないで本屋さんに直行した。 本屋さんで、本を立ち読みした感じで、随分理解が進んだ。 それで買わないで帰って来てしまったのだ。
もちろん本には、もっと詳しい理論的な背景も説明されていた。その本は１９７０年代とかに書かれた、コンピューターサイエンスのバイブルの様な本で、書いてあることが本当に正しいか説明するために、厳格な計算式や証明などが併記されていた。
そういう難しい理論が既に応用されて一般に定着してしまった２００８年に生きている現代っ子の僕としては、証明までは読む事無いかな、と思った。 それに、証明を必要としないのであれば、wiki にほとんどのことが書かれている。 であれば、もうちょっと頑張って wiki を読みこなしてみようと考えた。
というわけで、翻訳を進めた。 その翻訳結果を下記にコピペしてみようと思う。
更にこういうアプレットがあるので、色々動かして遊んでみた。
http://people.ksp.sk/~kuko/bak/index.html
この人の作ったアプレットが秀逸で、削除のアルゴリズムもステップを追って説明してくれるという優れものだ。 文章があいまいでわかりづらいところは、上記のアプレットを動かしてみることで、具体的なイメージをつかむことができた。
というわけで、論文を見ないでも、B-treeの削除を自分で設計してみようかな、と思うようになってきた。 要するに、バランスを崩さなければ、どんな方法を使ってもよいわけで、全部で多分６ケース出てくる全てのパターンを再帰的に処理すればよいだけの話だ。
あともうちょっとだ。
この翻訳、日本語のwikiに転載しようかな... 。
でもなんか日本語のwikiに真剣に肩入れすると、恐怖の「ワカラン人」と遭遇する危険がある。 彼らはコミュニケーション能力が０で会話が全く通じないので、これとまともにやりあうのは本当に不毛なのだ。 するとどうしても余計なパワーを吸い取られてしまう。
その危険は避けたいんだよな...。
以下 翻訳：
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
Search is performed in the typical manner, analogous to that in a binary search tree.
Starting at the root, the tree is traversed top to bottom, choosing the child pointer whose separation values are on either side of the value that is being searched.
Binary search is typically (but not necessarily) used within nodes to find the separation values and child tree of interest.
-----------------------------------------------------------------------
Algorithms:Insertion
All insertions happen at the leaf nodes.
1. By searching the tree, find the leaf node where the new element should be added.
2. If the leaf node contains fewer than the maximum legal number of elements, there is room for one more. Insert the new element in the node, keeping the node's elements ordered.
3. Otherwise the leaf node is split into two nodes.
3.1 A single median is chosen from among the leaf's elements and the new element.
3.2 Values less than the median are put in the new left node and values greater than the median are put in the new right node, with the median acting as a separation value.
3.3 That separation value is added to the node's parent, which may cause it to be split, and so on.
If the splitting goes all the way up to the root, it creates a new root with a single separator value and two children, which is why the lower bound on the size of internal nodes does not apply to the root.
The maximum number of elements per node is U-1.
When a node is split, one element moves to the parent, but one element is added. So, it must be possible to divide the maximum number U-1 of elements into two legal nodes.
If this number is odd, then U=2L and one of the new nodes contains (U-2)/2 = L-1 elements, and hence is a legal node, and the other contains one more element, and hence it too is legal.
If U-1 is even, then U=2L-1, so there are 2L-2 elements in the node. Half of this number is L-1, which is the minimum number of elements allowed per node.
An improved algorithm supports a single pass down the tree from the root to the node where the insertion will take place, splitting any full nodes encountered on the way. This prevents the need to recall the parent nodes into memory, which may be expensive if the nodes are on secondary storage.
However, to use this improved algorithm, we must be able to send one element to the parent and split the remaining U-2 elements into two legal nodes, without adding a new element. This requires U = 2L rather than U = 2L-1, which accounts for why some textbooks impose this requirement in defining B-trees.
-----------------------------------------------------------------------
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. 以上の処理によって、値はリーフノードから削除される。つまり、前者のケースに該当する。
-----------------------------------------------------------------------
Algorithms : Rebalancing after deletion
削除後のリバランシングのアルゴリズム
If deleting an element from a leaf node has brought it under the minimum size, some elements must be redistributed to bring all nodes up to the minimum.
もし、あるノードから数値を削除することによって、そのノードが数値の最少の個数を下回ってしまう場合､最少個数を下回らないようにいくつかの数値を再分配する必要がある。
In some cases the rearrangement will move the deficiency to the parent, and the redistribution must be applied iteratively up the tree, perhaps even to the root.
リバランシング処理を行うと、場合よって数値の欠乏が親ノードに移動することがある。そういう場合は、繰り返し親ノードへリバランシング処理を適用する必要がある。 繰り返し親ノードに処理を波及することによってルートノードまで処理が及ぶこともありえる。
Since the minimum element count doesn't apply to the root, making the root be the only deficient node is not a problem.
数値の最少個数はルートノードには適用されないため、ルートノードの数値の欠乏は問題にはならない。
The algorithm to rebalance the tree is as follows:
ツリーのリバランシングアルゴリズムは以下の通りである。
1. If the right sibling has more than the minimum number of elements.
ケース１：右側の兄弟ノードが最低個数を上回る数値を持っている場合。
1.1 Add the separator to the end of the deficient node.
数値が不足しているノードの最後に（親ノードの）分割値を追加する。
1.2 Replace the separator in the parent with the first element of the right sibling.
親ノードの分割値を右側兄弟ノードの最初の数値と置き換える。
1.3 Make the first child of the right sibling into the last child of the deficient node
右側兄弟ノードの最初の子ノードを欠乏しているノードの最後の子ノードに加える。
2. Otherwise, if the left sibling has more than the minimum number of elements.
または、もし左側の兄弟ノードが最低個数を上回る数値を持っている場合。
2.1 Add the separator to the start of the deficient node.
欠乏しているノードの先頭に親ノードの分割値を追加する。
2.2 Replace the separator in the parent with the last element of the left sibling.
親ノードの分割値を左側兄弟ノードの最後の数値と置き換える。
2.3 Make the last child of the left sibling into the first child of the deficient node
左側兄弟ノードの最後の子ノードを、欠乏しているノードの最初のノードに加える。
3. If both immediate siblings have only the minimum number of elements
もしも、左右両方の兄弟ノードが最少個数の数値しか持っていなかった場合。
3.1 Create a new node with all the elements from the deficient node, all the elements from one of its siblings, and the separator in the parent between the two combined sibling nodes.
不足するノード内にある全ての数値と、欠乏ノードに対応する兄弟ノードにある全ての数値、親ノードの分割値、それらを全てあわせて新しいノードを作る。
3.2 Remove the separator from the parent, and replace the two children it separated with the combined node.
親ノードから分割値とその二つの子ノードを削除する。（？）
3.3 If that brings the number of elements in the parent under the minimum, repeat these steps with that deficient node, unless it is the root, since the root may be deficient.
もし、上記の処理の結果、親ノードの数値個数が、最低個数を下回ってしまったばあい、上記の処理をその欠乏したノードに対して繰り返す。 但し、ルートノードまで到達したら処理を止める。 ルートノードは最低個数の制約が無い。
The only other case to account for is when the root has no elements and one child. In this case it is sufficient to replace it with its only child.
この他、処理しなければいけない最後のケースとして、ルートが数値も持たず、１つだけ子ノードを保持しているケースである。このケースは、単にその子ノードを置き換えるだけで充分である。
-----------------------------------------------------------------------
Algorithms : Creating a B-tree
When a large amount of information needs to be put into B-tree form, it might be assumed that simply repetitively inserting the data would be the quickest. In practice this is a slow operation due to the rearrangement of the tree that occurs. It is very much quicker to sort the data first, and then insert it as a monolithic block.
-----------------------------------------------------------------------
もちろん本には、もっと詳しい理論的な背景も説明されていた。その本は１９７０年代とかに書かれた、コンピューターサイエンスのバイブルの様な本で、書いてあることが本当に正しいか説明するために、厳格な計算式や証明などが併記されていた。
そういう難しい理論が既に応用されて一般に定着してしまった２００８年に生きている現代っ子の僕としては、証明までは読む事無いかな、と思った。 それに、証明を必要としないのであれば、wiki にほとんどのことが書かれている。 であれば、もうちょっと頑張って wiki を読みこなしてみようと考えた。
というわけで、翻訳を進めた。 その翻訳結果を下記にコピペしてみようと思う。
更にこういうアプレットがあるので、色々動かして遊んでみた。
http://people.ksp.sk/~kuko/bak/index.html
この人の作ったアプレットが秀逸で、削除のアルゴリズムもステップを追って説明してくれるという優れものだ。 文章があいまいでわかりづらいところは、上記のアプレットを動かしてみることで、具体的なイメージをつかむことができた。
というわけで、論文を見ないでも、B-treeの削除を自分で設計してみようかな、と思うようになってきた。 要するに、バランスを崩さなければ、どんな方法を使ってもよいわけで、全部で多分６ケース出てくる全てのパターンを再帰的に処理すればよいだけの話だ。
あともうちょっとだ。
この翻訳、日本語のwikiに転載しようかな... 。
でもなんか日本語のwikiに真剣に肩入れすると、恐怖の「ワカラン人」と遭遇する危険がある。 彼らはコミュニケーション能力が０で会話が全く通じないので、これとまともにやりあうのは本当に不毛なのだ。 するとどうしても余計なパワーを吸い取られてしまう。
その危険は避けたいんだよな...。
以下 翻訳：
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
Search is performed in the typical manner, analogous to that in a binary search tree.
Starting at the root, the tree is traversed top to bottom, choosing the child pointer whose separation values are on either side of the value that is being searched.
Binary search is typically (but not necessarily) used within nodes to find the separation values and child tree of interest.
-----------------------------------------------------------------------
Algorithms:Insertion
All insertions happen at the leaf nodes.
1. By searching the tree, find the leaf node where the new element should be added.
2. If the leaf node contains fewer than the maximum legal number of elements, there is room for one more. Insert the new element in the node, keeping the node's elements ordered.
3. Otherwise the leaf node is split into two nodes.
3.1 A single median is chosen from among the leaf's elements and the new element.
3.2 Values less than the median are put in the new left node and values greater than the median are put in the new right node, with the median acting as a separation value.
3.3 That separation value is added to the node's parent, which may cause it to be split, and so on.
If the splitting goes all the way up to the root, it creates a new root with a single separator value and two children, which is why the lower bound on the size of internal nodes does not apply to the root.
The maximum number of elements per node is U-1.
When a node is split, one element moves to the parent, but one element is added. So, it must be possible to divide the maximum number U-1 of elements into two legal nodes.
If this number is odd, then U=2L and one of the new nodes contains (U-2)/2 = L-1 elements, and hence is a legal node, and the other contains one more element, and hence it too is legal.
If U-1 is even, then U=2L-1, so there are 2L-2 elements in the node. Half of this number is L-1, which is the minimum number of elements allowed per node.
An improved algorithm supports a single pass down the tree from the root to the node where the insertion will take place, splitting any full nodes encountered on the way. This prevents the need to recall the parent nodes into memory, which may be expensive if the nodes are on secondary storage.
However, to use this improved algorithm, we must be able to send one element to the parent and split the remaining U-2 elements into two legal nodes, without adding a new element. This requires U = 2L rather than U = 2L-1, which accounts for why some textbooks impose this requirement in defining B-trees.
-----------------------------------------------------------------------
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. 以上の処理によって、値はリーフノードから削除される。つまり、前者のケースに該当する。
-----------------------------------------------------------------------
Algorithms : Rebalancing after deletion
削除後のリバランシングのアルゴリズム
If deleting an element from a leaf node has brought it under the minimum size, some elements must be redistributed to bring all nodes up to the minimum.
もし、あるノードから数値を削除することによって、そのノードが数値の最少の個数を下回ってしまう場合､最少個数を下回らないようにいくつかの数値を再分配する必要がある。
In some cases the rearrangement will move the deficiency to the parent, and the redistribution must be applied iteratively up the tree, perhaps even to the root.
リバランシング処理を行うと、場合よって数値の欠乏が親ノードに移動することがある。そういう場合は、繰り返し親ノードへリバランシング処理を適用する必要がある。 繰り返し親ノードに処理を波及することによってルートノードまで処理が及ぶこともありえる。
Since the minimum element count doesn't apply to the root, making the root be the only deficient node is not a problem.
数値の最少個数はルートノードには適用されないため、ルートノードの数値の欠乏は問題にはならない。
The algorithm to rebalance the tree is as follows:
ツリーのリバランシングアルゴリズムは以下の通りである。
1. If the right sibling has more than the minimum number of elements.
ケース１：右側の兄弟ノードが最低個数を上回る数値を持っている場合。
1.1 Add the separator to the end of the deficient node.
数値が不足しているノードの最後に（親ノードの）分割値を追加する。
1.2 Replace the separator in the parent with the first element of the right sibling.
親ノードの分割値を右側兄弟ノードの最初の数値と置き換える。
1.3 Make the first child of the right sibling into the last child of the deficient node
右側兄弟ノードの最初の子ノードを欠乏しているノードの最後の子ノードに加える。
2. Otherwise, if the left sibling has more than the minimum number of elements.
または、もし左側の兄弟ノードが最低個数を上回る数値を持っている場合。
2.1 Add the separator to the start of the deficient node.
欠乏しているノードの先頭に親ノードの分割値を追加する。
2.2 Replace the separator in the parent with the last element of the left sibling.
親ノードの分割値を左側兄弟ノードの最後の数値と置き換える。
2.3 Make the last child of the left sibling into the first child of the deficient node
左側兄弟ノードの最後の子ノードを、欠乏しているノードの最初のノードに加える。
3. If both immediate siblings have only the minimum number of elements
もしも、左右両方の兄弟ノードが最少個数の数値しか持っていなかった場合。
3.1 Create a new node with all the elements from the deficient node, all the elements from one of its siblings, and the separator in the parent between the two combined sibling nodes.
不足するノード内にある全ての数値と、欠乏ノードに対応する兄弟ノードにある全ての数値、親ノードの分割値、それらを全てあわせて新しいノードを作る。
3.2 Remove the separator from the parent, and replace the two children it separated with the combined node.
親ノードから分割値とその二つの子ノードを削除する。（？）
3.3 If that brings the number of elements in the parent under the minimum, repeat these steps with that deficient node, unless it is the root, since the root may be deficient.
もし、上記の処理の結果、親ノードの数値個数が、最低個数を下回ってしまったばあい、上記の処理をその欠乏したノードに対して繰り返す。 但し、ルートノードまで到達したら処理を止める。 ルートノードは最低個数の制約が無い。
The only other case to account for is when the root has no elements and one child. In this case it is sufficient to replace it with its only child.
この他、処理しなければいけない最後のケースとして、ルートが数値も持たず、１つだけ子ノードを保持しているケースである。このケースは、単にその子ノードを置き換えるだけで充分である。
-----------------------------------------------------------------------
Algorithms : Creating a B-tree
When a large amount of information needs to be put into B-tree form, it might be assumed that simply repetitively inserting the data would be the quickest. In practice this is a slow operation due to the rearrangement of the tree that occurs. It is very much quicker to sort the data first, and then insert it as a monolithic block.
-----------------------------------------------------------------------
コメント一覧
