「SQLアタマアカデミー 第7回」
『WEB+DB PRESS Vol.51』
今回はインデックスとパフォーマンスの話です。特に重要な B-tree (B+tree) とハッシュのアルゴリズムについて解説しています。インデックスというのは、みんな当たり前のように使っているでしょうが、その中身まで具体的なイメージを持っているかというと、B-tree が何となく木構造だという印象がある程度で、意外にブラックボックスになっているのではないでしょうか（B の意味もわからないしね）。
本文でもたびたび引用しましたが、このテーマについての最重要文献は、ルドルフ・バイエルの「B-tree and UB-tree」です。ぶっちゃけて言うと、これ読んでくれれば私の記事なんて読む必要ありません。本当は全文翻訳して「リレーショナル・データベースの世界」で公開したいぐらいなんですが、Scholarpedia は Wikipedia と違って GPL ライセンスではない通常の Copyright ライセンスが適用されるため、無断で翻訳を公表することはできません。残念。でも英語の勉強もかねて、ぜひ原文を読んでください。丁寧ですばらしい解説だし、難しい英語ではないですから。
なお、最後にハッシュについて一言補足しておくと、本文中ではずいぶんハッシュについての評価を低く書いてしまいましたが、これはあくまで一般向けの文章で、ハッシュが重要な分野というのもあります。たとえば私は、DWH の仕事ではハッシュに頼りきりです。これがないと DWH システムは成り立たない。
データベースに限らず、一般に TB 級の大量データの高速処理が求められる分野では、並列マシンによる分散処理（並列コンピューティング）がセオリーです。そして、分散処理とハッシュは実に相性がいい。Netezza では SPU と呼ばれる処理単位別にいかにうまくデータを分散させるかがパフォーマンスを決める最大の要因ですし、Teradata の場合もそれは変わりません（結合などのコストを考えると、ただ均等に割り振ればよい、というものではないのが悩ましくもあり、モデラーたちの腕の見せ所でもある）。
ただ、ハッシュというのは万能ではない。特に、記事にも書いたように、範囲検索に効果がないのが痛い。このハッシュの欠点を補うため、各ベンダーともいろいろな工夫を凝らしているのですが、これ以上は実装に踏み込む話になるので、この話はここで打ち切り。
