ホーム » 2010 » 1月 » 14

日別アーカイブ: 2010年1月14日

2010年1月
« 12月   2月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

B木とB+木

データベースの内部構造の話として、B木B+木について説明を行う。

B木

B木は、位数Nの場合、2N個のデータ部(di)と、 2N+1個の次のノードへのポインタ(pj)で、 1ノードが構成される。 i番目のポインタpiの先には、di-1より大きく、 diより小さいデータを格納する。 また、1つのノード内のデータ件数は、N以上、2N以下を満たすように構成する。

データの挿入などを行うことで、1ノード内のデータ件数が2N個を越える場合、 追加データを含めた2N+1個の中央の値を上位に昇格させ、ノードを2つに分割する。 昇格先の上ノードもあふれる場合は、再帰的に同じ処理を繰り返す。


データあふれで昇格&分割の説明(wikipediaより引用)

同様に、データ削除の場合も、1ノード内データ件数がNを下回る場合も、 2つのノードを併合などの処理を行う。

B+木

B木では、追加削除が容易ではあるが、全データの順次処理をする場合、 再帰処理などが必要になったりするため、データのシーケンシャルアクセス・ランダムアクセスが 苦手である。データベースでは、複数テーブルの全データで直積といった処理も多いことから、 次々と処理を行うためのヒントが必要となる。

このため、末端のノードにおいて、シーケンスセットと呼ばれるリスト構造を作っておく。 末端のデータをリストでつないだ情報を持つことで、データ順の順次アクセスが容易となる。

参考教科書では、シーケンスセットをノードとは別に保存する説明で記載されているが、 WikipediaのB+木の説明では、末端ノード同士を横方向に接続するだけの図で説明されている。 この辺は、実装方法の異差かな???

crontabの月日付と曜日日付はorなんだ

バックアップ対策用に導入したNASのためのバックアップ処理を記述したけど、 確認すると予想外のバックアップが発生している。 月初めの日曜だけバックアップを取りたかったので、crontab にて、

#時 分 日 月 曜
0   3 1-7 * 0   root ...backup-script...

を記載した。『1~7日でかつ曜日が日曜日』のつもりだったんだけど、1~7の毎日バックアップが実行されている。よくよく man 5 crontab を見ると、他の項目と違い、月日付と週日付の両指定は"or" だった。

注意: コマンド実行の日は 2 つのフィールドで指定できる — 月内日および曜日である。 もし両方のフィールドが制限指定 (* 以外) であると、 いずれかのフィールドが現在時刻と合った時にコマンドが実行される。 (man 5 crontab より)

しかたがないので、曜日指定を抜いて、"0 3 1 * * root …"の設定とした…. 平日夜中の3時、負荷かけないでね…

追記:2010/01/14 予定外で実行された、バックアップで中身をみると、差分バックアップなのに、大量の記録が 記載されている。でも、ほとんどディレクトリ。更新日付だけの記録なんだろうか….

全国高専到達度試験がありました

この数年、高専の3年生はこの時期、『全国高専到達度試験』というものが実施されます。 全国の高専の学習内容の理解度の違いを見るためなんだろうけど、 数学と物理の試験が、1/13日の午前に実施されました。 実施方法は、入試とほぼ同じで90分の内容。学校によって教える内容の違いもあり、 いくつかの領域に分けられ、最初から教えていないものは問題から除外される。

どちらにしろ、直接的に自分の成績には影響しないため、中には適当にマークシートに 書いている人も若干いる様子。だけど、数学・物理の先生も、学校の評価にかかわることもあり、 到達度試験と同様の範囲のレポートを課題にしたりと、ちょっと苦労されているみたい。