ホーム » スタッフ » 斉藤徹 » B+木とハッシュ法

2011年1月
« 12月   2月 »
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

B+木とハッシュ法

先週のB木の説明を受け、実際のデータベースで利用されているB+木について説明を行う。 また、インデックスファイルでの高速検索を行うためのハッシュ法なども説明する。

単純なB木では、全データ対象のシーケンシャル処理などが面倒になるので、 B木に相当する部分と、シーケンシャルアクセスのための"シーケンシャルセット"で データを扱う。

このようにすることで、全データへの処理はシーケンスセットで横断し、 個別のキーで検索を行う場合は、B木のインデックスで目的データを見つける。

また、このようなB木やB+木では、データを消す場合、各ノード内のデータ数が半分を切らない間は、各ノード内でデータを消去する(あるいは使わない目印をつけるだけ)。 データ数が半分を切ると、次のノードとくっつけるなどの処理が行われる。

このように、B+木を用いることで、特定のデータの検索・全データ参照が容易になる。 実際のデータベースでは、データの記録順序とは別のキーでの検索も必要となる。 この場合は、別途インデックスファイルを作ることになる。 このインデックスファイルでは、ハッシュ法が用いられる場合もある。 ハッシュ法では、データよりハッシュ関数で計算したハッシュ値を、データの保存場所に利用する。ただし、別データでも同じハッシュ値となる「ハッシュ衝突」が発生するため、 オープンアドレス法や、チェイン法が使われる。