はじめに
これは平衡な多分木の一つであるB木についての記事です。
B木の中で最も簡単な形である「2-3木」について書いています。
この記事の図は以下を用いて作成しました。
visualization
関連記事：
参考：
これで分かった2-3木
B木とは
B木は多分木の平衡探索木です。つまり、一つのノードに2より多い子を持ちます。一つのノードに対する子の最大数がm個である時、そのB木を「オーダーmのB木」と呼びます。
B木の中でもオーダー3のものを「2-3木」、オーダー4のものを「2-3-4木」と呼びます。
データベースのインデックスは一般的にこのB木で実現されています。
B木は「すべてのパス上のノードの数は等しい」という重要な特徴を持っています。二分木の場合は一つのノードが2つまでしか子を持てないため、どう頑張っても完全にバランスをとることはできません。
対してB木は多分木です。一つのノードが3つ以上の子を持つことができるので、二分木よりも自在に木を変形しバランスをとることができます。
2-3木とは
この記事では、B木の最も簡単な形である「2-3木」に関して書きます。
2-3木は一つのノードが2つまで値を持つことができます。
また、値を一つだけ持っているノードの子は必ず2つ、値を2つ持っているノードの子は必ず3つです。
上図は2-3木の一例です。完全に平衡していることがわかりますね。
値を一つ持つ場合は子が必ず2つ、のルールを満たしています。
ここに、「8」を追加すると下図になります。
「6」の右の子が要素を二つ持つことで、バランスを保ったまま、かつ高さを変えずに「8」を追加できました。
このように、「2-3木」では一つのノードが二つの値を持つことができます。
さらに「9」を追加してみます。
すると、「6」のノードが「8」も持つようになり、そのノードは3つの子を持つようになりました。
それぞれの子の値と枝の位置を見ると、「6」の左の子が「5」、右の子が「7」、「8」の左の子が「7」、右の子が「9」となっていることがわかります。
相変わらずバランスが取れており、高さも変わっていませんね。
このように2-3木は完全にバランスを保つことができる木構造です。
操作
2-3木は一つのノードに値を最大2つ、子を最大3つ持てるので、次のようにノードクラスを定義しました
public class BNode {
public int value1;
public int value2;
public BNode left;
public BNode middle;
public BNode right;
public BNode(int value) {
this.value1 = value;
}
}
また、要素や子は左から詰めていくことにします
検索
検索の考えは二分探索木と変わりません。
根から値を確認し、探している値であれば検索は終了します。ノードの値が探している値より大きければ左の子に、小さければ右の子に移動して比較を続けます。葉まで到達してしまったら探している値がなかったと判断します。
public String search(BNode node, int target, String path) {
if (node == null) {
return "";
}
if (node.has(target)) {
return path + ", " + target;
}
if (node.value1 > target) {
return search(node.left, target, path + ", " + node.value1);
}
if (!node.existsValue2() && node.value1 < target) {
return search(node.middle, target, path + ", " + node.value1);
}
if (node.value1 < target && target < node.value2) {
return search(node.middle, target, path + ", " + node.value1 + "/" + node.value2);
}
return search(node.right, target, path + ", " + node.value2);
}
public static void main() {
Printer p = new Printer();
BNode root = new BNode(4);
BNode left = new BNode(2);
BNode middle = new BNode(6);
root.left = left;
root.middle = middle;
left.left = new BNode(1);
left.middle = new BNode(3);
middle.left = new BNode(5);
middle.middle = new BNode(7);
p.printB(root, "", false, "");
/**
├── 4/0
│ ├── L:2/0
│ │ ├── L:1/0
│ │ ├── M:3/0
│ ├── M:6/0
│ │ ├── L:5/0
│ │ ├── M:7/0
*/
System.out.println(search(root, 7, ""));
// , 4, 6, 7
}
追加
まずは挿入場所のノードを探します。子として追加するのではなく、そのノードの値として追加します。
ノードが値を一つのみ持っている時、二つ目の値として追加して完了です。
挿入場所のノードがすでに2つ値を持っている場合は追加後に変形します。追加するとそのノードは要素を3つ持っていることになりますので、中央の値を親、それ以外をそれぞれ左の子、右の子とすることで二分木の形に変形します。中央の値を挿入場所のノードの親に追加します。追加時のロジックは上記の繰り返しです。
public BNode add(BNode node, int target) {
node = addLeaf(node, target);
if(node.needsSplit()) {
node = split(node);
}
return node;
}
public BNode addLeaf(BNode node, int target) {
if (node == null) {
return new BNode(target);
}
if (node.value1 > target) {
if (node.left == null) {
node.put(new BNode(target));
} else {
node.left = addLeaf(node.left, target);
if(node.left.needsSplit()) {
node.put(split(node.left));
}
}
} else if ((!node.existsValue2() && node.value1 < target)
|| (node.value1 < target && target < node.value2)) {
if (node.middle == null) {
node.put(new BNode(target));
} else {
node.middle = addLeaf(node.middle, target);
if(node.middle.needsSplit()) {
node.put(split(node.middle));
}
}
} else {
if (node.right == null) {
node.put(new BNode(target));
} else {
node.right = addLeaf(node.right, target);
if(node.right.needsSplit()) {
node.put(split(node.right));
}
}
}
return node;
}
/**
* nodeが3つの値を持つ場合、中央の値を親、それ以外を左の子、右の子とする
* ※この実装では値と枝が左に寄るようにしているので、実際は左の子と真ん中の子とする
*/
public BNode split(BNode node) {
BNode upNode = new BNode(node.extraValue);
upNode.left = new BNode(node.value1);
upNode.left.left = node.left;
upNode.left.middle = node.middle;
upNode.middle = new BNode(node.value2);
upNode.middle.left = node.right;
upNode.middle.middle = node.extraChild;
return upNode;
}
public class BNode {
// すでに記事内に記載した部分は割愛
/**
* 左に寄るように追加する
*/
public void put(BNode node) {
if (value1 == 0) {
this.value1 = node.value1;
this.left = node.left;
this.middle = node.middle;
} else if (value2 == 0) {
if (value1 > node.value1) {
this.value2 = this.value1;
this.value1 = node.value1;
this.right = this.middle;
this.middle = node.middle;
this.left = node.left;
} else {
this.value2 = node.value1;
this.middle = node.left;
this.right = node.middle;
}
} else {
if (node.value1 < value1) {
this.extraValue = this.value1;
this.value1 = node.value1;
this.extraChild = this.right;
this.right = this.middle;
this.middle = node.middle;
this.left = node.left;
} else if (this.value1 < node.value1 && node.value1 < this.value2) {
this.extraValue = node.value1;
this.extraChild = this.right;
this.right = node.middle;
this.middle = node.left;
} else if (this.value2 < node.value1) {
this.extraValue = this.value2;
this.value2 = node.value1;
this.extraChild = node.middle;
this.right = node.left;
}
}
}
public boolean needsSplit() {
return extraValue != 0;
}
}
// 動作確認
public static void main() {
Printer p = new Printer();
BNode root = b.add(null, 4);
root = add(root, 5);
root = add(root, 6);
root = add(root, 1);
root = add(root, 8);
root = add(root, 2);
root = add(root, 9);
root = add(root, 3);
p.printB(root, "", false, "");
/**
├── 5/0
│ ├── L:2/0
│ │ ├── L:1/0
│ │ ├── M:3/4
│ ├── M:8/0
│ │ ├── L:6/0
│ │ ├── M:9/0
*/
}
削除
実際のパターンはたくさんありますが、考え方は以下の3つです。
①削除対象のノードの親が3つの子を持っている場合
この時は削除対象のノードを削除しても子が二つになるだけなので2-3木のルールに反しません。よって単純にノードを削除するだけで済みます。
②削除対象のノードの親が2つの子を持っている、かつ、親の兄弟が3つの子を持っている場合
削除対象のノードを削除すると、親の子は一つになり、2-3木のルールを逸脱します。
そこで、親の兄弟から一つ子をもらいます。親が2つ、親の兄弟が2つの子を持つことで、バランスが取れます。
③削除対象のノードの親が2つの子を持っている、かつ、親の兄弟が2つの子を持っている場合
2 の場合と同様、2-3木のルールを逸脱します。
兄弟から子をもらってしまうと、今度は兄弟が1つしか子を持たなくなってしまうので、2と同じ方法は取れません。
この場合は、親と親の兄弟を融合しましょう。
親の値と親の兄弟はそれぞれ1つずつ値を持っていますので、ノードAでその二つの値を持ちます。
親の一つの子と、親の兄弟の2つの子をノードAの子とすれば融合が完了します。
public BNode deleteB(BNode node, int target) {
node = delete(node,target);
if(node.isEmpty()){
// 根が空のノードなら左の子を根とする
return node.left;
}
return node;
}
public BNode delete(BNode node, int target) {
if (node == null) {
return null;
}
if (node.value1 == target) {
if (node.middle == null) {
return node.remove(target);
} else {
int min = getMin(node.middle);
// 葉（右部分木の最小値）と交換して葉を削除
node.middle = delete(node.middle, min);
node.value1 = min;
}
} else if (node.value2 == target) {
if (node.right == null) {
return node.remove(target);
} else {
int min = getMin(node.right);
// 葉（右部分木の最小値）と交換して葉を削除
node.right = delete(node.middle, min);
node.value2 = min;
}
} else if (node.value1 > target) {
node.left = delete(node.left, target);
} else if ((!node.existsValue2() && node.value1 < target)
|| (node.value1 < target && target < node.value2)) {
node.middle = delete(node.middle, target);
} else {
node.right = delete(node.right, target);
}
return borrow(node);
}
public int getMin(BNode node) {
if (node.left == null) {
return node.value1;
}
return getMin(node.left);
}
public BNode borrow(BNode node) {
if (!node.needsBorrow()) {
return node;
}
if (node.existsValue2()) {
if (node.left == null) {
if (node.middle.existsValue2()) {
node.left = new BNode(node.value1);
node.value1 = node.middle.value1;
node.middle.value1 = node.middle.value2;
node.middle.value2 = 0;
} else {
node.left = new BNode(node.value1, node.middle.value1);
node.value1 = node.value2;
node.value2 = 0;
node.middle = node.right;
node.right = null;
}
return node;
}
if (node.left.isEmpty()) {
if (node.middle.existsValue2()) {
node.left.value1 = node.value1;
node.value1 = node.middle.value1;
node.middle.value1 = node.middle.value2;
node.middle.value2 = 0;
node.left.middle = node.middle.left;
node.middle.left = node.middle.middle;
node.middle.middle = node.middle.right;
} else {
node.left.value1 = node.value1;
node.value1 = node.value2;
node.value2 = 0;
node.left.value2 = node.middle.value1;
node.left.middle = node.middle.left;
node.left.right = node.middle.right;
node.middle = node.right;
node.right = null;
}
return node;
}
if (node.middle == null) {
if (node.right.existsValue2()) {
node.middle = new BNode(node.value2);
node.value2 = node.right.value1;
node.right.value1 = node.right.value2;
node.right.value2 = 0;
} else {
node.right.value2 = node.right.value1;
node.right.value1 = node.value2;
node.value2 = 0;
node.middle = node.right;
}
return node;
}
if (node.middle.isEmpty()) {
if (node.right.existsValue2()) {
node.middle.value1 = node.value2;
node.value2 = node.right.value1;
node.right.value1 = node.right.value2;
node.right.value2 = 0;
node.middle.middle = node.right.left;
node.right.left = node.right.middle;
node.right.middle = node.right.right;
node.right.right = null;
} else {
node.middle.value1 = node.value2;
node.middle.value2 = node.right.value1;
node.value2 = 0;
node.middle.middle = node.right.left;
node.middle.right = node.right.middle;
node.right = null;
}
return node;
}
if (node.right == null) {
if (node.middle.existsValue2()) {
node.right = new BNode(node.value2);
node.value2 = node.middle.value2;
node.middle.value2 = 0;
} else {
node.middle.value2 = node.value2;
node.value2 = 0;
}
return node;
}
if (node.right.isEmpty()) {
if (node.middle.existsValue2()) {
node.right.value1 = node.value2;
node.value2 = node.middle.value2;
node.middle.value2 = 0;
node.right.middle = node.right.left;
node.right.left = node.middle.right;
node.middle.right = null;
}else{
node.middle.value2 = node.value2;
node.value2 = 0;
node.middle.right = node.right.left;
node.right = null;
}
return node;
}
} else {
if (node.left == null) {
if (node.middle.existsValue2()) {
node.left = new BNode(node.value1);
node.value1 = node.middle.value1;
node.middle.value1 = node.middle.value2;
node.middle.value2 = 0;
} else {
BNode newNode = new BNode(0);
newNode.left = new BNode(node.value1, node.middle.value1);
node = newNode;
}
return node;
}
if (node.left.isEmpty()) {
if (node.middle.existsValue2()) {
node.left.value1 = node.value1;
node.value1 = node.middle.value1;
node.middle.value1 = node.middle.value2;
node.middle.value2 = 0;
node.left.middle = node.middle.left;
node.middle.left = node.middle.middle;
node.middle.right = null;
} else {
node.value2 = node.middle.value1;
node.left = node.left.left;
node.middle = node.middle.left;
node.right = node.middle.middle;
}
return node;
}
if (node.middle == null) {
if (node.left.existsValue2()) {
node.middle = new BNode(node.value1);
node.value1 = node.left.value2;
node.left.value2 = 0;
} else {
BNode newNode = new BNode(0);
newNode.left = new BNode(node.left.value1, node.value1);
node = newNode;
}
return node;
}
if (node.middle.isEmpty()) {
if (node.left.existsValue2()) {
node.middle.value1 = node.value1;
node.value1 = node.left.value2;
node.left.value2 = 0;
node.middle.middle = node.middle.left;
node.middle.left = node.left.right;
node.left.right = null;
} else {
node.value2 = node.value1;
node.value1 = node.left.value1;
node.right = node.middle.left;
node.middle = node.left.middle;
node.left = node.left.left;
}
}
}
return node;
}
public class BNode {
public boolean isEmpty() {
return value1 == 0 && value2 == 0;
}
public BNode remove(int value) {
if (value1 == value) {
this.value1 = value2;
this.value2 = 0;
} else {
this.value2 = 0;
}
if (value1 == 0 && value2 == 0) {
return null;
}
return this;
}
public boolean needsBorrow() {
if (this.value2 == 0) {
return (this.left == null && this.middle != null) || (this.left != null && this.middle == null)
|| (this.left != null && this.left.isEmpty()) || (this.middle != null && this.middle.isEmpty());
}
return (this.left != null && (this.middle == null || this.right == null))
|| (this.middle != null && (this.left == null || this.right == null))
|| (this.right != null && (this.left == null || this.middle == null))
|| (this.left != null && this.left.isEmpty())
|| (this.middle != null && this.middle.isEmpty())
|| (this.right != null && this.right.isEmpty());
}
}
// 動作確認
public static void b() {
Printer p = new Printer();
B b = new B();
BNode root = b.add(null, 4);
root = b.add(root, 5);
root = b.add(root, 6);
root = b.add(root, 1);
root = b.add(root, 8);
root = b.add(root, 2);
root = b.add(root, 9);
root = b.add(root, 3);
p.printB(root, "", false, "");
/**
├── 5/0
│ ├── L:2/0
│ │ ├── L:1/0
│ │ ├── M:3/4
│ ├── M:8/0
│ │ ├── L:6/0
│ │ ├── M:9/0
*/
root = b.deleteB(root, 1);
p.printB(root, "", false, "");
/**
├── 5/0
│ ├── L:3/0
│ │ ├── L:2/0
│ │ ├── M:4/0
│ ├── M:8/0
│ │ ├── L:6/0
│ │ ├── M:9/0
*/
root = b.deleteB(root, 5);
p.printB(root, "", false, "");
/**
├── 3/6
│ ├── L:2/0
│ ├── M:4/0
│ └── R:8/9
*/
}
B木が使われる理由
AVL木などの平衡二分木と比べると、B木は実は遅いです。これは、値の比較回数がB木の方が多いためです。
二分木の場合、ノードが持つ値は一つなので、その値と比べて大きいか小さいかだけを判断すれば良いのに対して、B木は値を複数個持つので、それぞれと比べる必要があります。明らかに比較回数が多いですよね。
B木の強みは、高さが平衡二分木と比べて低い、かつ完全にバランスできることです。一つの高さに格納できる値が多い分高さを低く保つことができます。完全に平衡であることでどの値にアクセスするときでもかかる時間が安定します。
高さが低いということは、パス上のノードの個数が少ない、つまり移動する回数が少ないということです。
ここで、ハードディスクなどのブロック化されたモジュールを考えると、一般的に「比較」よりも「移動」の方がはるかにかかる時間が大きいです。
比較回数を減らすよりも、移動回数を減らした方が速くなるということです。
この点では平衡二分木よりもB木の方が優れています。
また、B木の場合は一つのノードに複数の値を持つことができるため、モジュールのブロック長と値の個数をうまく合わせれば、さらに効率の良い読み込みができるというわけです。
複数の観点で相性の良い場面だと言うことです。よく考えられていますよね。
おわりに
B木の動き、めちゃくちゃ美しいですよね。
みなさんぜひこのページでB木の美しさを堪能してください。
B木のアルゴリズムの美しさに対して、上記のコードはダサいなあと思ってます。自分の理解のために自力で書いているのですが、同じ処理を３回書いていたり、根の処理を別途にしていたり、色々と直したい点があります。
が、B木のアルゴリズムは理解できたので、この記事を書くには十分と判断しました。
気が向いたら美しいコードにします（気が向いたら）