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

B木

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

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

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

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

B+木

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

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

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

バックアップ対策用に導入した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 …"の設定とした…. 平日夜中の３時、負荷かけないでね…

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

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

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