バランス木とB木 — 100万件が3段で届く
二分探索木は「毎回半分に絞れるから速い」と習いました。ところが 1,2,3,... と並んだ 10,000件を入れたら、高さが 10,000 になりました。木ではなく連結リストです。この記事では VM の中に ~/cslab/btree を作り、その症状を実測してから AVL木を自分で書きます。回転を図で暗記せず、単回転と二重回転を実装して、同じ 10,000件で高さが 14 に収まることを確かめます。赤黒木は実装せずルールだけ読み、B木がなぜデータベースの索引なのかを段数の計算で出します。最後にトライでオートコンプリートを作り、スキップリストと比べて、全部消します。