読者です 読者をやめる 読者になる 読者になる

WEB+DB Press Vol.91 データ構造の基礎知識 が良い

簡単なアルゴリズムの話かと思い、さらっと流そうかと思ったら、配列、連結リスト、ハッシュテーブルをRubyで実装し、B木/B+木にも言及した良記事でしたので、手を動かしなら、B+木の絵も手元で沢山書いて理解しながら熟読してしまいました。
計算量の違いの説明もあり図も充実しており、とてもよかったです。若い頃の自分に読ませてあげたい良特集です。

WEB+DB PRESS Vol.91

WEB+DB PRESS Vol.91

配列

配列と連結リストのアーキテクチャ、計算量の違いを 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まで読めば良いと。(言葉にするとわかりにくいので是非図付きの本書を読んでください。)

他には
MySQLInnoDBがB+木を採用していることや、プライマリキー(クラスタ化インデックス)と通常のインデックスの違い、通常のインデックスの問題点、その回避策となるカバリングインデックスの仕組みについて説明があり、とてもためになりました。

ご参考

若干visualizationの仕方が異なりますが、B+Tree がどのようにバランスするのかを分かりやすく見れます。
B+ Tree Visualization