今朝、演習室に入ったら、「ぐぉ〜ん」という音が部屋中に響いている。 今までの経験で、HDDとかの異音はもう少し音が高音域だし、 サーバからの悲鳴のメールは飛んでいないので、改めて音の方向に行くと、 EthernetのGiga-SW-HUBが音を出している。

16ポートの排熱FAN付きなので、排熱FANのベアリングが壊れたとしか 思えない。修理も考えるけど、8ポートのGiga-HUBが5000円程のご時世だし、 8ポートの購入することにした。

ほぼ同型の現行後継機種のHUBもあるけど、大型だけあって、 排熱FANがついている様子なので、FANナシ8ポート2個で、 設置形態も適当にやりくりすれば、利便性もあがるだろう…

トラブルが起こる時は、続くもんだ…
自室の"Drobo S"(異なるサイズのHDDで特殊なRAID化できるHDD-NAS)の1個が故障。 HDDが故障のメールを吐いて、空き領域を使って残り4個で冗長化するための再構築処理が始まった。 発注したHDDが届いたら、故障HDDを取り除いて差し替えるだけなので、復旧は極めて簡単(の予定)。

先週が演習課題で、未完成な人も多いので、前半講義、後半演習とする。

ビューテーブル

データベースでプログラムを作る場合、3層スキーマ構成で考えることが多い。 概念スキーマ、内部スキーマ、外部スキーマ。 ビューテーブルは、外部スキーマに相当する。

使い方としては、元々複数のテーブルで扱われているデータを、 あたかも合成したテーブルがあるかのように扱えるもの。

((成績データベースを例に...))
[成2]　こういうシンプルな表だと分かりやすい
名前 |科目|担当|点数
Aさん|ＤＢ|斉藤| 65
Bさん|電磁|高久| 73
Cさん|ＤＢ|斉藤| 45
　
　　　でも修正不整合などを防ぐには...
[成]
名前 |科ID|点数
Aさん|1000| 65
Bさん|1020| 73
Cさん|1000| 45
　
[担]
科ID|科目|担当
1000|ＤＢ|斉藤
1020|電磁|高久
create view 成2 (名前,科目,担当,点数)
as select 成.名前, 担.科目, 担.担当, 成.点数
from 成, 担
where 成.科ID = 担.科ID ;

データベース組込み言語

データベースの処理のプログラムを実際に記述する場合、C言語などで扱う場合は、 特殊なSQL埋め込み用の機能を用いて記述する場合が多い。 select文などを埋め込むと、各要素を処理するためのループ命令が作られ、 カーソルという概念で1件づつの処理を繰り返してくれる。

SQLの埋め込みなどの機能でプログラム言語と整合性の高いものは、 COBOLが一番有名。しかし、COBOL自体は歴史の長い言語であり、 最近の金融系では、COBOLプログラマが定年でプログラムを改良できる技術者不足などが原因の トラブルが多いことも雑談として説明しておく。

情報構造論は、先日のB木の説明をした所なので、 データベースの一般的な話をする予定だったが…

Webサービスとデータベースと負荷分散

でも、一般的なWebシステムでの負荷分散の話を知ってて 欲しかったので、 (1)大量のユーザの相手を負荷分散で処理するWebサーバ、 (2)そのWebサーバの裏でデータベースの処理をする スレーブ・データベース・サーバ、 (3)そのスレーブサーバの中核となるマスターデータベースサーバ の3段構成となっていることなどを説明する。

また、こういったWebシステムでは、早急なサービス提供開始が 必要となるから、安価なLAMP(Linux+Apache+MySQL+PHP)の コンピュータシステムで実現することが多いことを説明する。

LAMPシステムでサービスを開始すると、サービス提供の最初であったり、 システムが話題になったりと、インターネットでの情報によって、 サービス利用者は増減する。しかし、利用者が増えてサービス性能が 低下するのを防ぐ場合には、コンピュータの増設が必要となる。

仮想コンピュータ

しかし、物理的なコンピュータの増設は、管理の手間や導入費用、 さらに利用者が減った際に、遊休のコンピュータができるなど、 問題も多い。そこで、最近のコンピュータは1台の中に、 複数のCPUを持っていることから、仮想サーバ機能で、 必要な時に必要な量のコンピュータを一時的に借りるなどの 方法が取られる。

この際に、出来上がったソフトウェアを借りる(SaaS)、 プログラムを動かす基盤を借りる(PaaS)、 仮想コンピュータのCPU,MEM,HDD,NETを借りる(IaaS)などの 方式がある。

様々なプログラム言語

このWebサービスを動かすにあたり、 サーバ側であれば、PHPやPerlといったプログラム言語が使われたり、 Java等が使われる。そのデータ処理で、SQLなどの言語も使われる。

一方でクライアント側では、昔であれば静的なHTMLページを 記述したけど、ページ遷移は全画面同時に起こるため、 操作性が悪い。このため、以前であれば Java が使われた。 しかし、Java はブラウザの中の特定枠の中で動かされ、 ブラウザと連携するのは困難であった。そのため、JavaScriptなどが 開発され、画面の必要な部分だけ通信しながら処理を行う AJAX技術が発達してきた。それに合わせ、HTML5や画面レイアウト の記述であるCSSなどの考え方も重要となってきた。 そうすると、CSS,JavaScript,HTMLなどを自分で組合せて記述するのは 大変なので、jQueryなどのライブラリが普及してきた….

今日は、2分木を用いた式の表現とB木について説明を行う。 前回、２項演算子の話で、逆ポーランド記法などの説明をしたので、 そのプログラム例から話を行う。

逆ポーランド記法のスタック処理

逆ポーランド記法による式は、スタックを用いると簡単にその値を求める処理が記述できる。

// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '
// スタックの記述
int stack[ 10 ] ;
int *sp = stack ;
void push( int x ) {
*sp++ = x ;
}
int pop() {
return *--sp ;
}
// 逆ポーランド記法の式を処理する関数
int eval( char* s ) {
for( ; *s != '\0' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}
' ; s++ ) {
if ( *s >= '0' && *s <= '9' ) {
push( *s - '0' ) ;
} else {
switch( *s ) {
case '+' : push( pop() + pop() ) ; break ;
case '*' : push( pop() * pop() ) ; break ;
}
}
}
return pop() ;
}
void main() {
printf( "%d\n" , eval( "12+3*" ) ) ;
}

2分木による式の表現

これが本来説明したい2分木による式の表現。 データ構造を簡単にしたいので、 左右の枝がNULLなら、opr部に整数値、非NULLなら、opr部に演算子の文字コードとする。 この方式であれば、要素名は異なるものの、２分木のデータ宣言とまるっきり同じ。

// まずはデータ構造の宣言と、そのデータを生成する補助関数。
struct Expr {
int opr ;
struct Expr* left ;
struct Expr* right ;
} ;
// 数値の場合
struct Expr* Integer( int x ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = x ;
ans->left = NULL ;
ans->right = NULL ;
}
return ans ;
}
// 演算子の場合
struct Expr* Operator( int op ,
struct Expr* l ,
struct Expr* r ) {
struct Expr* ans ;
ans = (struct Expr*)malloc( sizeof( struct Expr ) ) ;
if ( ans != NULL ) {
ans->opr = op ;
ans->left = l ;
ans->right = r ;
}
return ans ;
}

データ構造を作る処理が記述できたところで、その式の表示と、その式の計算。

// 2分木による式を表示する関数。
// 演算子の優先順位を無視して、全てにカッコをつける
void print_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
printf( "%d" , e->opr ) ;
} else {
printf( "(" ) ;
print_expr( e->left ) ;
printf( "%c" , e->opr ) ;
print_expr( e->right ) ;
printf( ")" ) ;
}
}
// 式の値を計算する関数
int eval_expr( struct Expr* e ) {
if ( e->left == NULL && e->right == NULL ) {
return e->opr ;
} else {
switch( e->opr ) {
case '+' :
return eval_expr( e->left )
+ eval_expr( e->right ) ;
case '*' :
return eval_expr( e->left )
* eval_expr( e->right ) ;
}
}
}
// 実際に計算させてみる。
void main() {
struct Expr* e
= Operator( '*' ,
Integer( 1 ) ,
Operator( '+' ,
Integer( 2 ) ,
Integer( 3 ) ) ) ;
printf( "%d\n" , eval_expr( e ) ) ;
}

B木

2分木で式の表現を説明したが、枝の数は左右２本と限定する必要はあるのだろうか？ 2本をN本に拡張したものが、B木と呼ばれる。

// 位数2のBTree
struct BTree {
int size ; // B木のノード内のデータ数
int d[ 4 ] ; // 実際のデータ
struct BTree* p[ 5 ] ; // d[i] < ● < d[i+1] のデータは、
// p[i+1]の枝に保存
} ;

B木では、枝に関する条件に加え、位数Nの場合では、ノード内のデータ件数を必ず、 N <= (データ件数) <=2N を満たすようにする。

データの追加で、ノード内のデータ件数が2Nを越える場合には、 加えるデータを含め、データ順に並べた時の中央値を上位ノードに移動させ、 ノードを、左右に分割を行う。

|
　　[ 12 | 21 | 23 | 29 ]  ← 18を加えるなら、12,18,21,23,29 で、
　　　　　　　　　　　　　　　　　21を上位に上げる。
[ 8 |(21)| 39 | × ]
|    |
|    +---------------+
|                    |
[ 12 | 18 | × | × ]  [ 23 | 29 | × | × ]