ホーム » 2011 » 1月 » 25

日別アーカイブ: 2011年1月25日

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

最近の投稿(電子情報)

アーカイブ

カテゴリー

B+木とハッシュ法

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

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

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

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

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

緊急連絡システムの送信データ量

卒研にて「Google App Engine を使って緊急連絡システムを作ると…」 というネタをやっていて、その運用面での有用性の論証ということで、 現在の緊急連絡システムと比較しようという話になった。 そこで、メールの送信量を知りたいとの話。 ということで、簡単にプログラムを書いて、カウントしてみた。

発信されたメールの件数:9286件
そのメールを受け取った延べ人数:993302件
取り扱い組織数: 88組織
管理しているメールユーザ数: 12632件
(2006/01月より2011/01/25現在)
# ただし送信確認のテストメールや、受信フィルタで
# 実際には保護者に届かなかった人数(メール数)も含む。

運用が広がった段階で、約1万のメールアドレスを超えていて、我ながらすげーと思っていた。 んで、個人に送ったメールが、のべ約100万通か…すげー多いな…