B-treeを作成する。1}ここでItemは比較対象のアイテムより小さいかどうかを比較するLessメソッドを実装しています。Itemが持っているObjectはわかりやすさのために、stringにしていますが、interface{}にしておくことで、好きなデータを紐づけることができます。ItemをLessを持ったinterface化する方が汎用的だと思いますが、今回はこのままでいきます。btree.NewBtree(2)のようにして作成します。次にB-treeから特定のアイテムを探索するメソッドを実装していきます。子ノードのアイテムリストを探索し、なければその子ノードを(以下略)の用に探索していきます。アイテムリストの探索まずはアイテムリストから対象のアイテムを探索するメソッドを作成します。Itemsの中から検索対象のItemを検索する。false}ここでは、アイテムリストの中身をLessとsortパッケージのSearchメソッドを使って順に探索しています。アイテムリストの中に探しているアイテムが会った時のみ、二番目の戻り値にtrueを返しています(真ん中部分)アイテムリストの中に探索対象のアイテムがなかった場合、indexとfalseを返しています。対象アイテムが見つからなかった場合でも、falseのみでなくindexも返しているのは、次の子ノードを探索する時に利用するからです。下の画像の例でルートのノードから30を探索するケースを考えてみます。40]があり、30はありません。indexは1になります。B-treeの特性としてあるアイテムの右にはそのアイテムより大きく、左にはそのより小さいアイテムしかないという特性があるので、30は0の子ノード以下には存在しなく、同時に2の子ノードにも存在しないことになります。探索する子ノードは1の子ノードだけで良いのです。このindexはノードの探索用関数で使うことになります。false}ノードの探索関数は上のようになります。ノードにあるアイテムリストから探索し、もし見つかればそこで終了。見つからなければ、先ほどのindexにあたる子ノードを再帰的に探索していきます。ここでイメージがわきやすいようにテストを書いておきます。必要がない方は飛ばしてください。}}ノードの探索関数ができたので、ルートからそれを呼び出す関数を追加します。手書きでB-treeにアイテム・ノードを入れて試してみます。山田これで探索部分が完成しました。挿入は探索より少し複雑になります。基本的な流れは、以下のようになっています。詳しくは参考サイトなどをみていただけると理解しやすいかと思います。子ノードが閾値を超える場合は、子ノードを分割し、アイテムリストに真ん中になるアイテムを追加し、子ノードに分割したノードを追加する。その結果2の条件に当てはまれば、さらに自分自身を分割する。アイテムリストへの挿入アイテムリストへの挿入は、特に変わったことはありません。子ノードがない場合には、アイテムリストに追加する。アイテムリストが閾値を超えた場合は真ん中で分割する。いった振る舞いが必要になります。わかりやすさのために、3を実行する関数を実装します。下記の図のような状態のB-treeに8のアイテムを挿入するとします。5]のノードになりますが、8を挿入するとアイテムリストが3になるので、事前にこのノードを分割してアイテムを入れるスペースを空ける必要があります。実装としては以下のようになります。}}処理が終わったあとのB-treeは以下のようになり、8が入るスペースが空けられます。これを使ってノードへの挿入処理の関数を書きます。nodeにItemを挿入する。limit)}基本的に自身のアイテムリストに追加し、追加した後に先ほどのノードの分割処理を必要に応じて行なっています。子ノードができた後は、自身のアイテムリストの直接追加することはせず、適切な子ノードを探索した後に、その子ノードにたいしてinsert関数を呼び出しています。ルートノードへの挿入あとはルートノードへの挿入処理です。ルートノードで必要な処理は、ノードの初期化処理と、ノードと同じようにルートのアイテムリストが閾値を超えた時の分割処理処理のみです。みてもらえばわかりますが、初期化処理以外は、ノードの挿入処理と同じ動きをしています。nil}これでB-treeの探索処理と、挿入処理が一通り実装できました。B木のすごく簡単な実例b-treeを図でわかりやすく説明している。Treeの違いに関して説明させている。Treeの理解もすんなりできるRDBMSで使われるB木を学ぼうこちらは連載。upLoginユーザーは見つかりませんでした。