簡単なアルゴリズムの話かと思い、さらっと流そうかと思ったら、配列、連結リスト、ハッシュテーブルをRubyで実装し、B木/B+木にも言及した良記事でしたので、手を動かしなら、B+木の絵も手元で沢山書いて理解しながら熟読してしまいました。
計算量の違いの説明もあり図も充実しており、とてもよかったです。若い頃の自分に読ませてあげたい良特集です。
- 作者: 丸山晋平,清水雅人,舘野祐一,小野将之,佐藤歩,泉水翔吾,伊藤直也,佐藤太一,海野弘成,福本貴之,うさみけんた,西尾泰和,中島聡,はまちや2,竹原,WEB+DB PRESS編集部
- 出版社/メーカー: 技術評論社
- 発売日: 2016/02/24
- メディア: 大型本
- この商品を含むブログを見る
配列
配列と連結リストのアーキテクチャ、計算量の違いを unshift, push, each を実装することで理解できます。
ハッシュテーブル
ハッシュテーブルの仕組み(binやメモリ空間の説明)、rehash(要素数がbinを超えた時の再計算の仕組み)の説明があり、ハッシュテーブル、順序付きハッシュテーブルの実装することで計算量やメモリ使用量について理解できます。
余談
関連してRubyの実装上必要な Object#hash, Object#eql? がどのように定義されているかをコードリーディングで調べた記事です(本書で紹介されていました)。
こちらも面白かったです。
CRuby の hash.c を一部読んだ - 猫型の蓄音機は 1 分間に 45 回にゃあと鳴く
2分木、B木、B+木
2分探索木の説明、実装。そのあと、B木、B+木の説明があります。 「B+木」についてはちゃんと理解していなかったので勉強になりました。
B+木の特徴
- リーフノードを全て読むと、ツリー内の全てのデータを読むことができる
- リーフノードどうしが連結リストのように連結されている
これ何が嬉しいのかというと、Range指定の抽出が楽になります。
例えば、5から20のデータを抽出する場合、リーフノードの5を探せば、あとは連結されたデータを20まで読めば良いと。(言葉にするとわかりにくいので是非図付きの本書を読んでください。)
他には
MySQLのInnoDBがB+木を採用していることや、プライマリキー(クラスタ化インデックス)と通常のインデックスの違い、通常のインデックスの問題点、その回避策となるカバリングインデックスの仕組みについて説明があり、とてもためになりました。
ご参考
若干visualizationの仕方が異なりますが、B+Tree がどのようにバランスするのかを分かりやすく見れます。
B+ Tree Visualization