研修第4回(RDBMS概論最終回)
最終回ってことで、検索/インデックス関係のアルゴリズムの解説。
- アルゴリズム
- 線形探索
- 二分探索
- Hash探索
- Chain
- Open Address
- 二分木探索
- 平衡木探索
- MySQLのインデックスアルゴリズム
- B++ Tree(図解したのはB Tree)
- Hash
- R Tree
基本的に、図解中心。Cを知らないPGにHashとかのポインタなアルゴリズムを教えるのが大変。多分判ってくれてない。
ま、検索やインデックスの大体の動きや、各操作の計算量の目安が想像出来るようになってくれればいいんだけどね。
問題を出さなかったので、最終回ということで質問メインで時間を潰した。
SQL文と採用されるアルゴリズムについての質問なんかは非常にいい質問だったなあ。クエリオプティマイザの話も絡めて解答した。これに関しては、あとで資料作って配布しよう。
基本的には、インデックスの有無とその構造を理解できれば予想は可能だよって話だ。
- "foo like bar%"
- B++ Treeインデックス有
- 前方一致でインデックス辿ってデータの頭を探して、一致しないところまで線形探索。
- インデックス無
- sort & binary search
- linear search
- B++ Treeインデックス有
って感じで。
あとは、配布したソースが殆どのPGは判ってないObject指向ベースだったので、Object指向のザックリとした説明とか、DataObject系にはcompareとかequalsとか予め準備しておくと幸せになれるよとか言う話を callback functionだとか、絡めて説明したりした。
次回からは、正直順番は逆転してるんだけど、コンピュータ概論。まずはハード系とかOSの概略ぐらいだろうから、数週間は講師を休めそうだ。Linux系の話になると、俺がやるんだけど。
でもさ、そっち系の概論とかいう話になったら無意味に歴史話をしたくなりそうで、自制しなきゃと思う。Unix系、BSD系、Linux系とか、SysVとかPosixだとかFSFだとかどんどん広がっていきそうだもんねえ。ある程度、互換性類推出来る話ぐらいに留めないと。
あと、カーネル話とかも、Linuxがマイクロカーネル採用しなかったのは失敗だったって議論とかに話が飛びそうで気をつけなきゃ。
そんな話の後は何やるかは決まってないけど、候補としてはこんな感じ。
- ネットワーク概論
- プロトコル辺りの話は俺。
- それ以外は上司。
- プログラミング概論
- 現場に任せる。
- セキュリティ概論
- これは俺。
- 実践Webアプリ構築
- html/xhtml,css,JavaScriptは俺。
- phpは現場。
- DBは現場と俺の折半かな。
- 実践Webアプリ設計
- リーダクラス+DBAのディスカッションかな?
- 実践PM
- リーダクラス以上のディスカッションかな?
- 運用/負荷分散
- リーダクラス+各レイヤのメイン+鯖管のディスカッションかな?
- その他
- 業界動向、トレンドなど。リーダ会議でカバー?
やる事が多くて大変だけど、正直楽しいです。