B木メモ(not BI木)


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

ゆっくりアルゴリズム

使い物にならない人材速度でアルゴリズムを低速に考えます。

B木メモ

  • B木は平衡二分木のようにバランスがとれ、ノード中のブロックに複数のキーを格納する。
  • バランスのBだかブロックのBだかわからん。
  • 似たようなややこしいネーミングにバイナリインデックスツリーというのがあるが、おそらく別モノ
  • キーの挿入とは探索中の親ノードには追加されず、必ず子のノードに追加される。
  • 親ノードのキーが増えるときは、子ノードからの分割吸い上げによるもの。
  • アンダーフローに関して何か引っかかる自分。
  • 副作用として見れば、splitは2つの木と親への1つのキーの返還ではなく、溢れ出た1つの木と親へ渡すキー、そして自身を2つのキーへ変化させる処理
  • 上記の処理だと親ではinsertの戻り値として返ってきたこの2つのアイテムを一通りに挿入するだけ。
  • 挿入時にもしアイテムの数が多くなった場合は親へ同様の処理を行う。
  • 親の分割の際、引き連れている子の分割も行われるが、
  • 子が連続して格納されていない例はアルゴリズム上存在しないので、単純に0-2と3-5の子を持つようにすればいい。

  • 子を持つノードを親ノードと呼ぶ。
  • 親ノードが分割される場合はいつかという問いに対して、キーがBTreeに挿入される仮定では親ノードの分割は行われない。
  • 親ノードの分割がおこなわれるのは子ノードが分割され、吸い上げられたkeyによってノードのバッファがあふれるときに起こる。

  • 子のノードであること親のノードであることの振舞が違いすぎる気も。
  • ハードディスクに配置したり低レベルの組み込み用ではなく、
  • ただ単に高速検索を利用したいのであればポリモフィズムを利用したほうがいいかもしれない。