データベースの内部構造の説明として、排他処理やB木について解説を行う。

トランザクションとは、首尾一貫したデータに対する一連のデータベースの操作の集合で、 データの一貫性が保証されなければならない。 (A)原子性、(C)一貫性、(I)隔離性、(D)耐久性が重要であり、 一貫性を完全に反映させたCOMMIT状態から、トランザクションを受けつけ、 一貫性が保証されない時はROLLBACK文により処理が無かったものとして、 改めてトランザクションを行ったりする。

排他処理

トランザクションは並行して行われたりするが、一貫性を保つために順序が重要。 同時実行制御では、(a)ロッキング方式、(b)時刻印方式(更新の不都合の検知にタイムスタンプを使う)などがある。 ロッキング方式では、ロックの粒度（カラム/レコード/テーブル/DB全体)も重要。 粒度が大きいと、排他処理で待ちが増える。 ロックの種類には、共有ロック(Readロック:一般的に読み出しで他のアクセスを許す)や、 専有ロック(Writeロック:書き込み時で他のアクセスを許さない)がある。 ロックで排他状態になれば、待たされる…

ロックでは、資源解放を待つ状態になるが、資源が複雑に絡み合い、お互いがUnlock待ちになると、デッドロック状態が発生する。これを防ぐために、(a)ロックの一括獲得、(b)使用データの順序付け、(c)トランザクションの優先順位などを設けたりするけど、完璧なデッドロック解消は不可能。

DB内部構造：B木

2分木などの方式では、データの登録順序によっては木の左右のバランスが悪くなって、 検索効率の低下が発生する。2分木であれば、AVL木の手法でバランスを取るけど、 面倒な処理となる。

B木では、１つの節は位数Nのデータと、N+1件の節へのポインタを持つ。 １つの節の中のデータ件数は、N/2以上、N以下になるようにする。 データをB木に追加する時、データ個数がN+1個になった時、 中央値のデータを、上位ノードに繰り上げて２つの節に分ける。 このようにすることで、木のバランスを保つようにする。 (参考：昨年度資料)

Wikipediaより引用

Wikipediaより引用