100万件が3段で見つかるのは、木の形をしているからです。バランス木とB木を作って、索引が速い理由を確かめます。
これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で配列と連結リストを書き、データベースを自作する回で「索引を張ると速くなる」ところまでやった人が、その「速い」の中身を開けて見るための記事です。飛ばしても本線は進みます。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。 VM に Node.js が入っている必要があります。 入れ方は本線のnpmの回にあります。
node -vで v20 以上が出れば大丈夫です。 作業場所は~/cslab/btree/です。 この記事のためだけに新しく作り、最後に全部消します。 既存のプロジェクトには触りません。 記事に出てくる測定値は私のVMの数字です。 皆さんの数字とは違います。見てほしいのは絶対値ではなく、件数を増やしたときに高さが何段になるかです。
対象レベル: 中級〜上級 / 区分: 発展
木を書いたのに、木にならなかった
前の回で、私は自分でスタックとキューを書きました。そのあと調子に乗って、二分探索木を書きました。
説明は簡単でした。
二分探索木は、左の子が自分より小さく、右の子が自分より大きい木です。探すときは、根から比べて小さければ左、大きければ右に降りるだけ。1段降りるごとに候補が半分になるので、100万件でも20回で見つかります。
美しい話だと思いました。実際、書いたら動きました。ちゃんと入って、ちゃんと見つかりました。
そして、テスト用のデータを入れました。1 から 10000 まで、順番に。
高さを測りました。
高さ: 10000
14 のはずでした。 log2(10000) は約 13.3 です。
私は最初、高さを数えるコードのバグだと思いました。違いました。木のほうが壊れていました。
1 を根にしました。次に 2 が来ます。2 は 1 より大きいので右へ。次に 3 が来ます。1 より大きいので右へ、2 より大きいのでまた右へ。次に 4 が来ます。1 の右、2 の右、3 の右。
図にするとこうなっています。
1
\
2
\
3
\
4
\
...(10000段)
これは木ではありません。連結リストです。 しかも、右の子しか使っていないので、左の子のためのメモリを 10000個ぶん無駄に持っている連結リストです。
そして探索は、100万件で20回どころか、10000件で 10000回でした。
二分探索木の「速い」は、形が良いときだけの話です。 形は入れる順番で決まります。 そして現実のデータは、たいてい並んでいます。 IDの昇順、日付順、名前順。わざわざシャッフルしてから入れる人はいません。
ここで初めて、私は「バランス木」という言葉の意味が分かりました。
バランス木は「賢い木」ではありません。「一直線になるのを防ぐ木」です。 目的はただ1つ、高さを log n に保つこと。それだけです。AVL木も赤黒木もB木も、やろうとしていることは全部同じで、やり方が違うだけでした。
この記事では、その「やり方」を見ます。ただし、回転の図を暗記する記事にはしません。
私は昔、回転の図を4パターン暗記しようとして、3日で全部忘れました。 図は覚えられません。書いて、高さを測ったら、忘れなくなりました。 だからこの記事は書きます。
そして最後に、正直な結論を置きます。 これらを自分で書く機会は、実務ではほぼありません。 標準ライブラリとデータベースが全部やっています。それでも知っておく価値があるのは、「なぜ索引が速いのか」と「なぜ索引を張りすぎると挿入が遅くなるのか」を、自分の言葉で説明できるようになるからです。
この記事でわかること
- バランス木の目的はただ1つ、「高さを
log nに保つ」こと。 賢さの話ではなく、一直線になるのを防ぐ話。並んだ 10,000件で高さ 10000 が 14 になるのを実測します - 回転は覚える図ではなく、「親子の役を入れ替えるだけ」の操作。 入れ替えても「左 < 親 < 右」は壊れない。壊れないことを、並べ替えて確かめます
- バランスを取ると探索は速くなるが、挿入は遅くなる。 同じ 10,000件で挿入 4.1ms → 8.1ms、探索 3.0ms → 1.3ms。タダではないことを数字で見ます
- B木がデータベースの索引である理由は、ディスクが1バイトずつ読めないから。 二分木だと100万件で 20回のディスクアクセス。B木は同じ100万件が 2〜3段で届きます
- トライは、データ件数が100倍になっても引く時間が変わらない。 見る回数が「単語の長さ」だけで決まるから。代償はメモリで、Set の 8倍でした
- スキップリストは木ではない。 連結リストを重ねてコインを投げるだけで、回転が1行も要らない。それでほぼ同じ性能が出ます
- これらを自分で書くことは、実務ではほぼ無い。 価値があるのは「索引が速い理由」と「索引を張りすぎると挿入が遅くなる理由」を説明できること
この記事でやること
~/cslab/btree/を作り、素朴な二分探索木に並んだ 10,000件を入れて、高さが 10000 になることを実測する- AVL木を自分で書く。各節点に高さを持たせ、単回転(LL / RR)と二重回転(LR / RL)を実装して、同じ 10,000件で高さが 14 になることを確かめる
- 挿入時間と探索時間を両方測って表にする。バランスを取る代償を数字で出す
- 赤黒木はルールだけ読む(実装しない)。AVL木との使い分けを表にする
- B木が索引である理由を、段数の計算で出す。枝の数を 2 / 100 / 500 に変えて必要な段数を比べる
- トライを書いてオートコンプリートを作り、件数に依存しないことと、メモリの代償を実測する
- スキップリストを書いて AVL木と比べ、名前だけ押さえるものを整理して、
~/cslab/を消す
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| 節点(ノード / node) | 木の1個分。鍵と、左右の子への参照を持っている |
| 根(ルート / root) | 木の一番上の節点。探索はここから始まる |
| 葉(リーフ / leaf) | 子を持たない節点。木の一番下 |
| 高さ(height) | 根から一番遠い葉までの段数。この記事の主役はこれだけ。速さは高さで決まる |
| 二分探索木(BST) | 「左の子 < 自分 < 右の子」を守った木。降りるだけで探せる |
| バランス木 | 高さが log n から離れないように、自分で形を直す木。AVL木・赤黒木・B木など |
| 回転(rotation) | 親と子の役を入れ替えて、木の高さを1段下げる操作。並び順は壊れない |
| 次数 / 枝の数(order / fanout) | 1つの節点から出ている子の本数。二分木は最大2本。B木は何百本にもする |
| 接頭辞(prefix) | 文字列の先頭部分。program の接頭辞は p pr pro … |
O(log n) | 件数が10倍になっても、時間は数段しか増えない形。本線の計算量の回でやりました |
① 症状を確認する:並んだデータで木が一直線になる
まず作業場所を作ります。
v22.14.0
v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。
この記事では npm install を1回もしません。ライブラリは使いません。 使ったら、正体を確かめるという目的が消えます。
package.json だけ置きます。これは import を使うためです。
素朴な二分探索木を書く
まず、バランスを取らないほうを書きます。症状を自分の目で見るためです。
コードの中に2箇所、コメントで注意を書いています。 どちらも同じ話です。
insertとheightを再帰で書くと、この記事の実験では落ちます。 並んだ 10,000件を入れた木の高さは 10000 です。再帰で降りると 10000段積むので、前の回でやったMaximum call stack size exceededが出ます。 教科書の二分探索木は、たいてい再帰で書いてあります。それは「木が壊れていない」ことを暗黙に前提にしているからです。壊れた木を観察するコードは、再帰では書けません。
前の回で「自分でスタックを持つループに書き換えれば、コールスタックは溢れない」とやりました。その書き換えを、ここで実際に使っています。
並んだデータと、ばらしたデータを入れ比べる
件数: 10000
理想の高さ(log2): 14
--- 並んだ順に入れた木 ---
節点数: 10000
高さ : 10000
10000を探すのに降りた段数: 10000
--- 順番をばらして入れた木 ---
節点数: 10000
高さ : 27
10000を探すのに降りた段数: 15
これが症状です。 3つ、読み取ってください。
1. 同じ 10,000件です。 入れたデータは完全に同じ。入れた順番だけが違います。 それで高さが 10000 と 27 になりました。
2. 10000 を探すのに 10000段降りています。 二分探索木を使っているのに、先頭から1個ずつ見る配列の総なめと、まったく同じ回数です。木にした意味が完全に消えています。
3. ばらしたら 27 で、理想の 14 の約2倍でした。 これは「運が悪かった」のではありません。ランダムに入れた二分探索木の高さは、平均して log n の約2倍になります。14 にはなりません。 バランスを取らない限り。
ここが一番大事なところです。 「ランダムなら大丈夫」ではありません。ランダムでも2倍で、並んでいたら n 倍です。 そして現実のデータは、ほぼ必ず並んでいます。 自動採番のID、作成日時、名前のあいうえお順。「たまたま最悪のケースを踏む」のではなく、「普通にやると最悪のケースになる」のです。
だから、入れる側が気をつけるのではなく、木のほうが自分で直す必要があります。それがバランス木です。
② AVL木を書く:高さを節点に持たせて、傾いたら回す
AVL木のやることは、たった2つです。
- 各節点が、自分を根とする部分木の高さを覚えている
- 左右の高さの差が 2以上になったら、回して直す
これだけです。この2行が分かれば、AVL木は分かったことになります。 以下は、その実装の話です。
回転は「図」ではない。親子の役を入れ替えるだけ
回転を最初に説明します。ここを図の暗記にすると必ず忘れるので、「なぜ壊れないか」から入ります。
右に回す場合を見ます。y が親で、その左の子が x です。A B C は部分木(もっと木がぶら下がっているかもしれない場所)です。
y x
/ \ / \
x C 右に回す → A y
/ \ / \
A B B C
やっていることは3行です。
xの右の子(B)を、yの左に付け替えるyを、xの右の子にするxが新しい親になる
ここで、この木を小さい順に並べてみます。
回す前: A < x < B < y < C
回した後: A < x < B < y < C
完全に同じです。 回転は、並び順を1つも変えません。 変えるのは「誰が上か」だけです。 だから「左 < 親 < 右」の規則は、回しても絶対に壊れません。 これが回転が許される理由の全部です。
なぜ同じになるのか、確かめ方は簡単です。回す前の木を、左から順に読む(左の部分木 → 自分 → 右の部分木) と A, x, B, y, C です。回した後の木を同じように読むと、x の左が A、x 自身、x の右が y で、その y の左が B、y 自身、y の右が C。やはり A, x, B, y, C。
そして高さは下がります。 回す前は x の下に A と B があって y の下に x と C。左が深い形です。回した後は x の下に A と y、y の下に B と C。左右に振り分けられました。
二重回転が必要な場合がある
1回では直らない形があります。「左の子の、右が重い」場合です。
z z y
/ \ / \ / \
x D y D x z
/ \ → / \ → / \ / \
A y x C A B C D
/ \ / \
B C A B
①左が重い ②まず x を左に回す ③次に z を右に回す
なぜ1回で駄目なのか。 ①の形で z をそのまま右に回すと、y が z の左に付け替わるだけで、深いところ(B と C)がそのまま深いまま残ります。高さが下がりません。
だから、先に「く」の字を「ノ」の字に伸ばしてから回します。②で x を左に回すと、①の「左の子の右が重い」が「左の子の左が重い」に変わります。そこからは1回で直ります。
この4パターンには名前が付いています。
| 名前 | どういう傾き | 何回回すか |
|---|---|---|
| LL | 左の子の、左が重い | 右に1回(単回転) |
| RR | 右の子の、右が重い | 左に1回(単回転) |
| LR | 左の子の、右が重い | 左に1回 → 右に1回(二重回転) |
| RL | 右の子の、左が重い | 右に1回 → 左に1回(二重回転) |
この表を暗記する必要はありません。 覚えるのは1つだけです。
「重い側に、まず一直線にしてから、逆側に回す」
LL と RR は最初から一直線なので、そのまま逆側に回すだけ。LR と RL は「く」の字なので、一直線にする1回が余分に入る。それだけです。
実装する
気をつける点が3つあります。
1. #h(null) が 0 を返します。 空の場所の高さを 0 にしておくと、#fix の 1 + Math.max(...) が場合分け無しで書けます。これを null のときエラーにすると、if が4倍に増えます。
2. #fix は必ず「下から順」です。 #rotateRight の中で #fix(y) を先に、#fix(x) を後に呼んでいます。逆にすると、x が古い y の高さを見て計算するので、高さがずれます。 木の形は正しいのに高さだけ嘘になる、一番気づきにくい壊れ方です。
3. #insert は「新しい親を返す」形です。 node.left = this.#insert(node.left, key) のように、戻り値を必ず代入し直します。 回転で親が変わるので、代入を忘れると、回した結果がどこにも繋がらず、入れたはずのデータが消えます。
そして、#insert は再帰で書いています。 ①の BST ではループにしたのに、なぜここは再帰で良いのか。
AVL木は高さが
log nに保たれるので、再帰の深さもlog nにしかなりません。 100万件でも 20段です。溢れません。 「バランス木は再帰で書ける」は、バランス木の性質の結果です。 逆に、①の壊れた木では書けませんでした。この非対称が、そのまま高さの話です。
4つの傾きを、最小の3件で全部起こす
まず、小さい木で回転を目で見ます。
=== LL (左の左が重い→右に1回) : 3,2,1 の順に入れた ===
| /-- 3 (h1)
\-- 2 (h2)
\-- 1 (h1)
高さ 2 / 回転 {"LL":1,"RR":0,"LR":0,"RL":0}
=== RR (右の右が重い→左に1回) : 1,2,3 の順に入れた ===
| /-- 3 (h1)
\-- 2 (h2)
\-- 1 (h1)
高さ 2 / 回転 {"LL":0,"RR":1,"LR":0,"RL":0}
=== LR (左の右が重い→2回) : 3,1,2 の順に入れた ===
| /-- 3 (h1)
\-- 2 (h2)
\-- 1 (h1)
高さ 2 / 回転 {"LL":0,"RR":0,"LR":1,"RL":0}
=== RL (右の左が重い→2回) : 1,3,2 の順に入れた ===
| /-- 3 (h1)
\-- 2 (h2)
\-- 1 (h1)
高さ 2 / 回転 {"LL":0,"RR":0,"LR":0,"RL":1}
draw() の読み方だけ先に説明します。 上が右の子、下が左の子です。 首を左に90度傾けて見ると、普通の木の図になります。文字で木を描くとき、この向きが一番崩れないので、こうしました。(h2) はその節点の高さです。
そして、4つの結果を見てください。
4つとも、まったく同じ形になっています。 入れた順番は
3,2,1/1,2,3/3,1,2/1,3,2の4通りで全部違います。回転の種類も4通り全部違います。それでも最終形は2を根に1と3がぶら下がる、同じ木です。
これが、私が図の暗記をやめた瞬間でした。
4つのパターンは「4つの違う処理」ではありません。「同じ結論に到達するための、入口の違い」です。 目的は最初から1つ、「高さを下げる」だけ。傾き方が4通りあるので、そこに至る手順が4通りある。それだけでした。
10,000件で①と比べる
件数 1000 / 高さ 10 / log2 10 / 挿入 3ms / 最悪の探索段数 10
件数 10000 / 高さ 14 / log2 14 / 挿入 6ms / 最悪の探索段数 13
件数 100000 / 高さ 17 / log2 17 / 挿入 30ms / 最悪の探索段数 17
件数 1000000 / 高さ 20 / log2 20 / 挿入 320ms / 最悪の探索段数 20
全部「並んだ順」で入れています。 ①で高さ 10000 になったのと、同じ入れ方です。
| 件数 | 素朴な木の高さ | AVL木の高さ | log2 |
|---|---|---|---|
| 1,000 | 1000 | 10 | 10 |
| 10,000 | 10000 | 14 | 14 |
| 100,000 | (100000) | 17 | 17 |
| 1,000,000 | (1000000) | 20 | 20 |
高さが log2 とぴったり一致しています。 100万件が 20段。件数が1000倍になって、高さは 10段しか増えていません。
これが O(log n) の実物です。 本線の計算量の回でグラフとして見たものが、いま木の高さとして出ています。
[スクリーンショット: 01_高さが10000から14になる.png] — node shape.js と node grow.js の出力が両方写るように撮ります。「高さ 10000」と「高さ 14」が1枚に並ぶことが大事です。この記事の主張の全部がこの1枚に入ります。
③ 代償を測る:探索は速くなり、挿入は遅くなる
AVL木は速い。では、なぜ全部AVL木にしないのか。 タダではないからです。測ります。
件数 10000 / 理想の高さ 14
素朴な木(並んだ順) 高さ 10000 / 挿入 136.7ms / 全件探索 119.1ms / 平均段数 5000.5
AVL木(並んだ順) 高さ 14 / 挿入 7.4ms / 全件探索 4.5ms / 平均段数 12.4
素朴な木(ばらした順) 高さ 27 / 挿入 4.1ms / 全件探索 3.0ms / 平均段数 15.4
AVL木(ばらした順) 高さ 16 / 挿入 8.1ms / 全件探索 1.3ms / 平均段数 12.6
AVL木の回転回数(10000件): { LL: 0, RR: 9986, LR: 0, RL: 0 }
回転の合計: 9986 / 1件あたり 0.999 回
表にします。
| データの入れ方 | 木 | 高さ | 挿入 | 全件探索 | 平均段数 |
|---|---|---|---|---|---|
| 並んだ順 | 素朴な木 | 10000 | 136.7ms | 119.1ms | 5000.5 |
| 並んだ順 | AVL木 | 14 | 7.4ms | 4.5ms | 12.4 |
| ばらした順 | 素朴な木 | 27 | 4.1ms | 3.0ms | 15.4 |
| ばらした順 | AVL木 | 16 | 8.1ms | 1.3ms | 12.6 |
読み方を3つに分けます。
1. 並んだ順では、AVL木が挿入も探索も圧勝です。 挿入 136.7ms → 7.4ms で 18倍速い。 「バランスを取る仕事が増えたのに、挿入まで速くなった」のは、素朴な木のほうが降りる段数が平均 5000段もあったからです。回転のコストより、無駄に降りるコストのほうがずっと大きい。
2. ばらした順では、挿入がひっくり返ります。 4.1ms → 8.1ms で AVL木のほうが約2倍遅い。 これが代償です。回転する仕事、高さを書き直す仕事、バランスを確認する仕事が、1件ごとに乗ります。
3. それでも探索は 3.0ms → 1.3ms で AVL木が 2倍以上速い。 平均段数が 15.4 から 12.6 に減っています。
これが「索引を張りすぎると挿入が遅くなる」の正体です。 データベースの索引は、こういう木です。索引を1本増やすと、
INSERTのたびに木を1本、余分に組み直すことになります。 読むのが速くなる代わりに、書くのが遅くなる。 どちらも速くなる選択肢はありません。 本線のMySQLの回でCREATE INDEXを打ったとき、私はこれを1行も理解していませんでした。
そして、回転の回数を見てください。
10,000件を入れて、回転は 9,986回。1件あたり 0.999回です。「1件入れるたびに、およそ1回」。並んだデータを入れ続けているので、毎回同じ方向(RR)に傾き、毎回1回回して直しています。
LL / LR / RL が 0回なのも読みどころです。入力が単調増加なので、右にしか傾かない。 4パターンを実装しましたが、この入力では1種類しか出番がありません。 だから④の four.js のように、わざと4パターンを起こす入力を作らないと、残り3つが動いているか確認できません。
④ B木がデータベースの索引である理由
ここが、この記事で一番実務に効く節です。
AVL木で高さは log2 n になりました。100万件で20段。 これで十分な気がします。
データベースは、それでは全然足りません。 理由は木の話ではなく、ディスクの話です。
ディスクは1バイトずつ読めない
メモリの上のデータを読むとき、node.left は「その場所を見る」だけです。ほぼ一瞬です。
ディスクは違います。
ディスクは、決まった大きさの「かたまり」単位でしか読めません。 1バイトだけ欲しくても、そのバイトを含むかたまり全体を読みます。 このかたまりを ブロック や ページ と呼びます。MySQL の InnoDB では 16KB です。
つまり、16KB 読むのと 1バイト読むのは、ほぼ同じ時間がかかります。
ここで、二分木をディスクの上に置いたと想像してください。1つの節点には、鍵1個と、子への参照2個しか入っていません。数十バイトです。
1段降りるごとに、16KB のページを1枚読んで、その中の数十バイトだけ使って、次に行きます。
二分木をディスクに置いた場合(100万件)
20段降りる = 16KB のページを 20枚読む
= 使ったのは 20 × 数十バイト
= 残りの 99.9% は読み捨て
1回のディスクアクセスは、メモリアクセスの数万倍から数十万倍遅いです。20回やれば、それだけで終わりません。
B木の答え:1つの節点に、鍵を何十個も詰める
B木の発想は、節点を「1ページぶんに膨らませる」ことです。
二分木の節点 B木の節点(1ページ = 16KB)
[ 50 ] [ 10 | 25 | 40 | 55 | 70 | 85 | ... 何百個 ]
/ \ / | | | | | | \
<50 >50 子 子 子 子 子 子 子 子
(枝も同じ数だけある)
1ページ読んだら、その中で何百回も比較できます。 そして次のページに降りる回数が、劇的に減ります。
段数を計算する
「枝が何本あると、何段で届くか」を計算します。式は単純です。枝の数を f、件数を n とすると、必要な段数は log_f(n)。
枝の数 | 1千件 | 100万件 | 1億件 (必要な段数=ディスクアクセス回数)
2 | 10 | 20 | 27
4 | 5 | 10 | 14
100 | 2 | 3 | 4
500 | 2 | 3 | 3
1000 | 1 | 2 | 3
--- 16KB のページに鍵と枝を詰めたら何本になるか ---
鍵 8バイト → 1ページに 1170 本 → 100万件が 2 段
鍵 16バイト → 1ページに 744 本 → 100万件が 3 段
鍵 64バイト → 1ページに 234 本 → 100万件が 3 段
鍵 255バイト → 1ページに 62 本 → 100万件が 4 段
表にします。
| 枝の数 | 1千件 | 100万件 | 1億件 |
|---|---|---|---|
| 2(二分木) | 10段 | 20段 | 27段 |
| 4 | 5段 | 10段 | 14段 |
| 100 | 2段 | 3段 | 4段 |
| 500 | 2段 | 3段 | 3段 |
| 1000 | 1段 | 2段 | 3段 |
100万件が、20段から3段になりました。 ディスクアクセスが 20回から3回。7倍ではありません。「20回待つ」と「3回待つ」の差です。 そして1億件でも4段です。枝を100本にすると、件数が100倍になっても段数が1つ増えるだけになります。
下の表がもっと現実的です。 鍵の大きさによって、1ページに何本の枝が詰められるかが変わります。
| 鍵の大きさ | 1ページ(16KB)に入る枝 | 100万件が何段 |
|---|---|---|
8バイト(BIGINT) | 1170本 | 2段 |
| 16バイト | 744本 | 3段 |
| 64バイト | 234本 | 3段 |
| 255バイト(長い文字列) | 62本 | 4段 |
索引を張る列が長いと、段数が増えます。
これが、「索引は短い列に張れ」「VARCHAR(255) 全体に索引を張るな、先頭の数文字だけにしろ」と言われる理由です。気分の問題ではなく、1ページに何本詰まるかの問題でした。
B+木:葉を連結リストで繋ぐ
データベースが実際に使っているのは、B木の変種の「B+木」です。違いは2つです。
1. データは葉にしか置きません。 途中の節点は「どっちに行くか」の道しるべだけを持ちます。道しるべだけなら小さいので、1ページにもっと詰まります。
2. 葉が、横方向に連結リストで繋がっています。
[ 40 | 80 ] ← 道しるべだけ
/ | \
[10|25] [50|65] [90|99] ← ここにデータがある(葉)
│ │ │
└──────────┴──────────┘
葉が横に繋がっている
この2つ目が効きます。
WHERE id BETWEEN 100 AND 200 のような範囲検索を考えてください。
- 普通のB木なら、100 を探して、次に 101 を探して、また根から降りて…を101回。
- B+木なら、100 を1回探して葉に着いたら、あとは横に歩くだけです。
ORDER BYとBETWEENと>が索引で速くなるのは、これのおかげです。 葉がすでに小さい順に並んで、横に繋がっているから、並べ替えも範囲取りも「歩くだけ」で済みます。 逆に、ハッシュ索引(Redis のHASHのような形)では範囲検索ができません。 順番の情報を捨てているからです。
そして、あのとき書いた「索引が速い」の正体が、これでした。
本線のデータベースを自作する回で、私は索引を作って「速くなりました」と書きました。中で何が起きているかは書けませんでした。 深掘りの索引を張ったのに使われない回では EXPLAIN を読みましたが、「なぜ LIKE '%文字%' だと索引が効かないのか」は、木の形の話として説明できていませんでした。
いま説明できます。
B+木は「先頭から順に比べて降りる」木です。 だから先頭が決まっていないと、どの枝に行けばいいか決まりません。
LIKE 'abc%'は先頭が決まっているので降りられます。LIKE '%abc%'は降りる先が決まらないので、葉を全部歩くしかありません。 深掘りの部分一致の回で全文検索エンジンが必要になった理由も、これです。B+木では原理的に無理でした。
MySQL の InnoDB は、テーブルそのものも B+木で持っています。 主キーの B+木の葉に、行の中身が丸ごと入っています(クラスタ化索引)。だから主キー以外の索引で引くと、まず索引の木を降りて主キーを得て、それから主キーの木をもう1回降りることになります。2本降りるわけです。EXPLAIN で見る「カバリングインデックス」という言葉は、「1本目の木の中に必要な列が全部あったので、2本目を降りずに済んだ」という意味でした。
⑤ 赤黒木:実装しない。ルールと「なぜ緩いか」だけ
この節では、赤黒木を実装しません。 理由は正直に書きます。
私は2回書こうとして、2回とも削除する処理で詰まりました。 挿入は書けます。削除が、場合分けで6通りあります。 そして書き上げても、AVL木より速いことを実測で示すのは簡単ではありません。
ここで時間を使うのは、この記事の目的に合いません。 目的は「中で何が起きているかを読めるようになること」で、「赤黒木を書けるようになること」ではありません。
だから、ルールと使い分けだけ押さえます。
5つのルール
赤黒木は、各節点に「赤」か「黒」の色を持たせた二分探索木です。ルールは5つです。
| # | ルール | 何のためか |
|---|---|---|
| 1 | 各節点は赤か黒 | 色を使ってバランスを表す |
| 2 | 根は黒 | 起点を固定する |
| 3 | 葉(null の場所)は黒とみなす | 数え方を揃える |
| 4 | 赤の節点の子は、必ず黒(赤が2つ続かない) | 赤が連続しないので、道の半分以上は黒になる |
| 5 | どの節点から葉までの道も、通る黒の数が同じ | これが「バランスしている」の定義そのもの |
この5つから何が言えるか。
ルール5で「黒の数はどの道も同じ」。ルール4で「赤は連続しない」。つまり一番短い道(全部黒)と一番長い道(黒と赤が交互)の差は、最大でも2倍です。
高さの差が2倍以内に収まる。 それが赤黒木の保証です。 AVL木の保証は「左右の高さの差が1以内」。 赤黒木のほうが、ずっと緩いです。
緩いと何が起きるか
緩いということは、直す回数が少なくて済むということです。
| AVL木 | 赤黒木 | |
|---|---|---|
| バランスの条件 | 左右の高さの差が1以内(厳しい) | 黒の数が同じ・赤が連続しない(緩い) |
| 高さ | 1.44 × log2 n くらい | 2 × log2 n くらい(少し高い) |
| 挿入・削除 | 回転が多い → 少し遅い | 回転が少ない → 速い |
| 探索 | 高さが低い → 少し速い | 少し遅い |
| 節点が持つ余分な情報 | 高さ(整数) | 色(1ビット) |
| 実装の難しさ | 回転4パターン。書ける | 削除の場合分けが多い。かなり難しい |
| 向いている場面 | 読むほうがずっと多い | 書きも読みも多い(汎用) |
赤黒木のほうが「速い」のではありません。 どこを速くするかの選択が違うだけです。
そして、汎用の道具としては赤黒木が選ばれています。 実物を並べます。
| 使っているもの | どこで |
|---|---|
Java の TreeMap / TreeSet | 標準ライブラリの、順序付きマップの実装 |
C++ の std::map / std::set | 同じ。規格が「対数時間」を要求し、実装はほぼ赤黒木 |
| Linux カーネル | CFS(Linux 6.6 以降は後継の EEVDF)スケジューラが、次に動かすプロセスを選ぶのに使っている。ほかにメモリ領域の管理などでも使う |
std::mapに値を入れるたびに、赤黒木が回っています。 Linux が「次にどのプロセスを動かすか」を決めるたびに、赤黒木を降りています。 自分では一度も書いたことがないのに、毎秒何千回も使っているわけです。
Linux のカーネルが赤黒木を選んだ理由は、スケジューラが「入れる・消す」を極端に多く行うからです。プロセスが実行可能になれば入れ、実行を終えれば消す。挿入と削除の回数が探索の回数と同じくらいある場面では、回転が少ないほうが勝ちます。
ここまでで、③の表と同じ話が2回出てきました。
- ③:索引を張ると読みが速くなり、書きが遅くなる
- ⑤:バランスを厳しくすると読みが速くなり、書きが遅くなる
同じトレードオフです。 データ構造の選択は、ほとんどの場合「読みと書きのどちらが多いか」の1問に還元されました。本線のパフォーマンス改善の回で「まず測る」と書いたのは、この1問に答えるためだったわけです。
⑥ トライを書く:オートコンプリートは件数に依存しない
ここまでの木は、全部「鍵を比べて、左か右に降りる」木でした。
トライは違います。 比べません。1文字ずつ、その文字の枝に降ります。
(根)
└ p ─ r ─ o ─┬ g ─ r ─ a ─ m ● ← program
└ d ─ u ─ c ─ t ● ← product
● = 「ここで単語が終わる」という印
program を探すとき、比較は1回もしません。 p の枝、r の枝、o の枝…と7回降りるだけです。
見る回数は「単語の長さ」だけで決まります。 入っている単語が 100語でも 1000万語でも、
programを引くのに7回です。 データ件数に、まったく依存しません。 これはO(log n)よりさらに強い性質です。
実装する
まず単語リストを作ります。VM に辞書ファイルが無いことがあるので、自分で作ります。
/usr/share/dict/words を使う例をよく見ますが、素の Ubuntu Server には入っていません。 wamerican を apt install すれば入りますが、この記事のために apt でパッケージを増やしたくないので、自分で作りました。接頭辞が共通する単語が大量に必要なので、意図的に部品の組み合わせで作っています。
トライ本体です。
end というフラグが要る理由を押さえてください。pro まで降りられることは、pro が単語であることを意味しません。 program の途中を通っただけかもしれません。「ここで終わる」という印が別に必要です。
startsWith は、接頭辞まで降りて、そこから下を全部集めるだけです。前の回で書いたスタックを、また使っています。
動かす
単語数: 10000 / 例: program, program1, program2, program3, program4
トライに入った単語: 10000 / 節点の数: 10755
--- オートコンプリート ---
'pro' → product, product1, product10, product11, product12, product13
'progr' → program, program1, program10, program11, program12, program13
'interfer' → interfer, interfer1, interfer10, interfer11, interfer12, interfer13
'zzz' → (候補なし)
--- has() の確認 ---
has('program') : true
has('progra') : false (途中までは単語ではない)
has('programming') : false
検索欄の下に出てくる、あの候補リストです。 30行ほどで動きました。
has('progra') が false なのが、end フラグが効いている証拠です。progra まで降りられますが、そこには印がありません。
'zzz' が (候補なし) になるのも大事な挙動です。 z の枝が無いので、1文字目で終わります。 候補が無いことが分かるのも、1文字目を見た瞬間です。
件数に依存しないことを測る
--- 同じ1語を10万回引く(件数を100倍にする)---
単語 100件 / 節点 111 / 10万回で 24.2ms(1回 242ナノ秒)
単語 1000件 / 節点 1079 / 10万回で 23.7ms(1回 237ナノ秒)
単語 10000件 / 節点 10755 / 10万回で 14.9ms(1回 149ナノ秒)
--- 接頭辞で候補6件を出すのを1000回 ---
トライ : 22.9ms
配列を総なめ : 266.5ms
Setを総なめ : 1.1ms(⚠️ Setは接頭辞では引けない)
--- 測り直し:候補が末尾にある接頭辞 (subtain) で1000回 ---
該当件数: 200
トライ : 6.1ms
Setを総なめ : 192.9ms
1つめの結果を見てください。
| 単語の件数 | 節点の数 | 10万回引くのにかかった時間 |
|---|---|---|
| 100 | 111 | 24.2ms |
| 1,000 | 1,079 | 23.7ms |
| 10,000 | 10,755 | 14.9ms |
件数が100倍になって、時間が増えていません。 むしろ縮んでいます(10,000件のほうが速いのは、実行が長く続いてJITの最適化が効いたためです。速くなった理由は木ではなくランタイムの都合なので、ここで読むべきは「増えていない」ことだけです)。
素朴な木なら、件数が100倍なら高さが約7段増えます。トライは1段も増えません。 見ているのは program の7文字だけだからです。
2つめの結果は、私が測り方を間違えた記録です。
Set を総なめ が 1.1ms で、トライの 22.9ms より20倍速く出ました。これは嘘です。
原因は、progr で始まる単語が、リストの先頭に固まっていたことです。Set の総なめは6件見つけたところで break するので、最初の10件くらいを見ただけで終わっていました。
候補が末尾にある接頭辞(subtain)で測り直したら、192.9ms になりました。 トライは 6.1ms。約31倍の差です。総なめは「運が良ければ速い」だけで、最悪のときに 190ms かかります。
[スクリーンショット: 02_トライは件数が増えても遅くならない.png] — node bench-trie.js の出力全体を撮ります。上の3行の時間がほぼ同じであることと、測り直しで Set が 190ms 台になっていることが両方読めるように撮ります。
代償はメモリ
set : 322 KB / 要素 10000
trie : 2663 KB / 節点 10755
8倍以上です。
同じ 10,000語を持っているのに、Set は 322KB、トライは 2,663KB。理由は明らかです。
トライは、1文字ごとに1個の節点を作ります。 節点1個には
Mapが1つ入っています。 10,755個のMapがあるわけです。Mapは空でもそれなりの大きさを持ちます。Setのほうは文字列を 10,000本持っているだけです。
--expose-gc を付けているのが要点です。 これを付けないと global.gc() が使えず、測定の前後にゴミが残ったままの数字が出ます。私は最初これを付けずに測って、実行するたびに数百KBずれる数字を見て混乱しました。
判断はこうなります。
| やりたいこと | 使うもの |
|---|---|
| その単語が入っているかだけ知りたい | Set。トライは要らない。8倍のメモリを払う理由が無い |
| 接頭辞で候補を出したい(オートコンプリート) | トライ。Set では原理的にできない |
| 候補が数百件しかない | 配列の filter。266ms は「1000回やったら」の数字。1回なら 0.27ms |
「トライのほうが速いから使う」は間違いです。 Set でできることには Set を使い、Set にできないこと(接頭辞)だけにトライを使います。
⑦ スキップリスト:木ではないのに、ほぼ同じ性能が出る
ここまでずっと木でした。最後に、木でないものを1つ書きます。
スキップリストは連結リストです。 それを何段か重ねて、どの値をどの段に載せるかをコインで決めるだけです。
段4: H ──────────────────────────────→ 50 ────────────────→ null
段3: H ──────────→ 20 ───────────────→ 50 ───→ 70 ────────→ null
段2: H ───→ 10 ─→ 20 ───→ 35 ───────→ 50 ───→ 70 → 85 ───→ null
段1: H → 5 → 10 → 20 → 28 → 35 → 42 → 50 → 61 → 70 → 85 → 93 → null
(H = 先頭。一番下の段には全部の値が並んでいる)
61 を探すとき。 段4を見ると 50 があります。61 より小さいので 50 まで進みます。次に 50 の先を見ると null。段を1つ降ります。段3で 50 の次は 70。61 より大きいので進めません。また降ります。段2でも 70。降ります。段1で 61。着きました。
「大きく跳んで、行き過ぎたら降りる」を繰り返しています。やっていることは二分探索と同じです。
なぜコインで決めるのか。 段を上げるかどうかを、確率 1/2 で決めます。すると段1に全部、段2に約半分、段3に約4分の1…と、勝手に「良い形」になります。
回転が1行も要りません。 AVL木は「傾いたら直す」ために回転が必要でした。スキップリストは、最初から確率で形を決めるので、直す必要がありません。 「最悪の場合」の保証はありません。 コインが偏れば遅くなります。ただ、その確率が実用上無視できるほど小さい、という理屈です。
実装する
update 配列が要点です。 挿入するとき、各段の「どこの後ろに入れるか」を全部覚えておく必要があります。段ごとに繋ぎ替えるので、段ごとに直前の節点が要るわけです。
-Infinity を先頭に置いているのも実装の都合です。 これがないと「先頭に入れる場合」だけ特別扱いが必要になります。番兵を1個置くだけで if が消えます。
AVL木と比べる
スキップリスト: 100000件 / 段数 16 / 挿入 71ms
AVL木 : 100000件 / 高さ 17 / 挿入 63ms
スキップリストの全件探索: 19ms
AVL木の全件探索 : 8ms
範囲で取る (500〜510): 500,501,502,503,504,505,506,507,508,509,510
50000 を探すのに進んだ回数: 14
同じ 10万件を、同じ「並んだ順」で入れました。
| スキップリスト | AVL木 | |
|---|---|---|
| 段数 / 高さ | 16 | 17 |
| 挿入(10万件) | 71ms | 63ms |
| 全件探索 | 19ms | 8ms |
| 回転の実装 | 無し | LL / RR / LR / RL の4種 |
AVL木のほうが少し速い。でも「少し」です。 そして回転を1行も書いていません。
コードの行数を比べます。
avl.js: 77
skiplist.js: 49
trie.js: 51
bst.js: 48
AVL木 77行、スキップリスト 49行(空行とコメントを除く)。AVL木の 77行には、木を絵にする draw() の7行が入っているので、実質は 70行対 49行です。
3割少ないコードで、ほぼ同じ性能が出ました。 しかも難しさが違います。 AVL木の 70行のうち、回転と場合分けが 35行あります。ここは間違えても静かに壊れます(高さがずれるだけで、木は動く)。 スキップリストの 49行に、そういう場所がありません。 繋ぎ替えを間違えれば、すぐデータが消えて気づきます。
そして、これも実物で使われています。
Redis の Sorted Set(
ZADD/ZRANGE)の中身は、スキップリストです。 「スコア順に並べて、範囲で取る」のが Sorted Set の仕事で、スキップリストは一番下の段がただの連結リストなので、範囲取りが歩くだけで済みます。 本線のRedisの回でランキングを作ったとき、ZRANGEの裏でこれが動いていました。
B+木の葉が横に繋がっている話と、同じ発想です。 「範囲で取りたい」という要求が、必ず「横に繋がった一列」を要求します。 B+木もスキップリストも、そこは同じでした。
⑧ 名前だけ押さえるもの
書かないものを、どの問いに効くかの1行だけで並べます。名前を知っているだけで、調べ物のときに引っかかるようになります。 それが目的です。
| 名前 | どの問いに効くか |
|---|---|
| 2-3木 | 1つの節点に鍵を1個か2個持つ木。B木の一番小さい形。「節点に複数の鍵を置く」という発想の出発点 |
| 2-3-4木 | 鍵を1〜3個持つ木。赤黒木は、この2-3-4木を二分木で表現したもの。赤いつながりが「同じ節点の中」を表す |
| 接尾辞配列(suffix array) | 「この文書のどこかに、この文字列があるか」。B+木では原理的にできなかった部分一致。全文検索エンジンの中身 |
| 接尾辞木(suffix tree) | 同じ問い。トライの親戚。速いがメモリを食うので、実用では接尾辞配列が選ばれることが多い |
| k-d木 | 「この地点の近くにある店を5つ」。座標での近傍検索。地図アプリ・最近傍探索 |
| R木 | 「この四角形と重なる領域はどれか」。地理情報データベースの索引(GEOMETRY 型など) |
| ヒープ(heap) | 「一番小さいものだけ、すぐ取りたい」。並び順は保証しない。優先度付きキューの中身 |
| B+木 | ④でやった。「範囲で取りたい」「並べ替えたい」。関係データベースの索引 |
この表の並べ方に、狙いがあります。
データ構造は「性能で選ぶ」ものではなく、「答えたい問いで選ぶ」ものでした。
- 「あるか」だけ → ハッシュ(
Set/Map) - 「順番に並べたい」「範囲で取りたい」 → B+木・スキップリスト・赤黒木
- 「先頭が一致するものを集めたい」 → トライ
- 「どこかに含まれるものを探したい」 → 接尾辞配列(全文検索)
- 「座標が近いものを探したい」 → k-d木・R木
- 「最小のものだけ欲しい」 → ヒープ
性能はこの後に決まります。 問いが違えば、どんなに速いデータ構造でも答えられません。 Set がどれだけ速くても、接頭辞では引けませんでした。
⑨ 判断表と、正直な結論
判断表
実務で「何を使うか」を選ぶときの表です。
| やりたいこと | 使うもの | 自分で書くか |
|---|---|---|
| キーで1件引く | Map / Set(ハッシュ) | 書かない。言語標準 |
| 順番を保って持ちたい(JavaScript) | JavaScript に順序付きマップは無い。配列 + 二分探索、またはライブラリ | 場合によって書く |
| 同じことを Java / C++ で | TreeMap / std::map(赤黒木) | 書かない。標準ライブラリ |
| データベースで速く引きたい | 索引(B+木)。CREATE INDEX | 書かない。DBの中身 |
| 範囲・並べ替えで引きたい | B+木の索引。BETWEEN / ORDER BY が効く | 書かない |
| スコア順のランキング | Redis の Sorted Set(スキップリスト) | 書かない |
| オートコンプリート | トライ、または検索エンジン | 小さければ書く。⑥は30行だった |
部分一致(%文字%) | 全文検索エンジン(接尾辞配列) | 書かない |
| 「一番小さいものだけ」 | ヒープ | 小さければ書く |
| 座標の近傍 | PostGIS / 地理索引(R木) | 書かない |
「自分で書く」の列が、ほとんど「書かない」です。
正直な結論
この記事で AVL木・トライ・スキップリストを書きました。合計 180行くらいです。
そしてこの3つを、私は実務で1行も書かないと思います。
- 順序付きマップが要るなら、標準ライブラリにあります
- 索引が要るなら、データベースが持っています
- ランキングが要るなら、Redis がやります
- オートコンプリートが要るなら、検索エンジンか、そもそも件数が少なくて配列で足ります
では、この180行は無駄だったのか。 無駄ではありませんでした。ただし、価値があるのは書けるようになったことではありません。
この記事の後に説明できるようになったことは、3つだけです。
1. なぜ索引が速いのか。 100万件が20回ではなく3回のディスクアクセスで届くから。1つの節点に鍵を何百個も詰めて、段数を潰しているから
2. なぜ索引を張りすぎると挿入が遅くなるのか。 索引1本ごとに木が1本ある。
INSERTのたびに、その全部を組み直しているから。③で挿入が 4.1ms から 8.1ms になったのと同じ話3. なぜ
LIKE '%文字%'では索引が効かないのか。 B+木は先頭から比べて降りる木で、先頭が決まっていないと降りる枝が決まらないから
この3つは、「回転の図」を覚えても出てきません。 高さを測って、段数を数えて、挿入時間の増加を見て、初めて出てきました。
そして、この3つが分かれば、実務で困ることのほとんどが済みます。 EXPLAIN の出力が読めます。索引を張るか迷ったときに、何を測ればいいかが分かります。テーブル設計で「この列に索引を張るなら短くしよう」と思えます。
データ構造の勉強の目的は、データ構造を書けるようになることではありませんでした。 他人が書いたデータ構造の、性能の癖を予想できるようになることでした。
[スクリーンショット: 03_全部を並べて比べる.png] — node bench.js と node use-skip.js の出力を両方撮ります。AVL木の挿入が素朴な木より遅くなっている行と、スキップリストが回転無しでほぼ同じ性能を出している行が読めることが大事です。
つまずいたところ
遠回りした過程を、消さずに残します。
1. height() を再帰で書いて、木を測る前に落ちた
①で、高さを数えるメソッドを最初こう書きました。
height(node = this.root) {
if (node === null) return 0;
return 1 + Math.max(this.height(node.left), this.height(node.right));
}
教科書の書き方です。 そして、並んだ 10,000件を入れた木で呼んだら落ちました。
RangeError: Maximum call stack size exceeded
測ろうとしている症状(高さ 10000)が、測定コードそのものを壊しました。 前の回でやったエラーが、ここで出ました。
自分でスタックを持つループに書き換えて解決しました。「壊れた木を観察するコードは、木が壊れていないことを前提にできない」という、当たり前だけど気づきにくい話でした。
2. insert を再帰で書いて、同じところで落ちた
height を直したら、次は insert で落ちました。同じ理由です。 10,000段降りるので 10,000段積みます。
こちらもループにしました。そして AVL木の #insert は再帰のままにしました。 これは手抜きではなく、AVL木は高さが log n に保たれるので、深さが 20段までしか行かないからです。この非対称が、そのままバランス木の存在理由でした。
3. 回転の中で #fix の順番を逆にして、高さが静かにずれた
#rotateRight を最初こう書きました。
#rotateRight(y) {
const x = y.left;
y.left = x.right;
x.right = y;
this.#fix(x); // ⚠️ こっちを先に呼んだ
this.#fix(y);
return x;
}
動きました。 データも全部入りました。探索もできました。そして高さが 14 にならず、19 になりました。
原因は、x の高さを計算するときに、まだ古い y の高さを見ていたことです。高さは必ず「下から順」に直さなければいけません。 x の子になった y を先に直し、それから x を直す。
この壊れ方が一番厄介でした。 例外も出ず、データも消えず、バランスの判定だけが嘘の数字でされる。draw() を書いて小さい木を目で見るまで、原因が分かりませんでした。 小さい木を絵にするコードは、7行の投資として安すぎるくらいでした。
4. #insert の戻り値を代入し忘れて、データが消えた
これも書きました。
if (key < node.key) this.#insert(node.left, key); // ⚠️ 代入していない
回転が起きるまでは動きます。 回転が起きると、新しい親がどこにも繋がらないので、その部分木ごと消えます。
size は増えているのに、has() が false を返す。「入れたはずなのに無い」という、一番気持ちの悪い症状でした。
再帰で木を組む関数は、必ず「新しい親を返す」形にして、必ず代入し直す。 これは覚える価値がありました。
5. 4パターンの回転が、3つ動いていなかった
③の測定で、10,000件を入れて回転が RR が 9,986回、他が全部 0回でした。
私は最初、実装のバグを疑いました。 違いました。入力が単調増加なので、右にしか傾かないのが正しい挙動でした。
ここで気づいたのは、テストの話です。 「10,000件入れて動いた」は、4パターンのうち1つしか通っていないということでした。だから four.js を書いて、わざと4パターンを起こす最小の入力(3,2,1 / 1,2,3 / 3,1,2 / 1,3,2)を作りました。
大量のデータで動かすことは、網羅とは無関係でした。
6. トライの測定で、Set が20倍速いという嘘の数字を出した
⑥の2つめの測定で、Set の総なめが 1.1ms、トライが 22.9ms と出ました。
私はこれを見て「トライは無駄だった」と結論しかけました。測り方が間違っていました。
progr で始まる単語が、リストの先頭に固まっていたのです。6件見つけたら break するので、最初の10件くらいを見ただけでした。
subtain(末尾に固まっている接頭辞)で測り直したら、192.9ms になりました。31倍の逆転です。
break が入る測定は、データの並び順に完全に依存します。 「最悪のケース」と「運が良いケース」を、両方測らないと意味がありませんでした。
7. メモリ測定が実行ごとに数百KBずれた
process.memoryUsage().heapUsed を前後で引いたら、実行ごとに 300KB くらいばらつきました。
原因はゴミが残っていたことです。node --expose-gc を付けて global.gc() を測定の前後で呼ぶようにしたら、安定しました。
--expose-gc 無しで global.gc && の短絡だけ書いていたので、エラーも出ず、静かに「GCを呼ばずに測定」していました。 「動いているのに測れていない」形です。
8. B木を実装しようとして、途中でやめた
私は最初、B木も実装するつもりでした。 そして節点の分割の処理で詰まり、2時間使って動かず、やめました。
やめた判断を、ここに残します。B木の価値は「実装できること」ではなく「なぜ段数が減るかを説明できること」でした。 そして段数の計算は levels.js の20行で出ました。 実装しても、この記事の主張は1つも増えません。
赤黒木も同じ理由で実装していません。 「実装しないと分かった気になれない」は、私の思い込みでした。 分かるべきなのはトレードオフで、それは表で書けました。
後片づけ
この記事で作ったものを、全部消します。
まず、何があるか確認します。
avl.js bench-trie.js four.js levels.js mem-trie.js shape.js skiplist.js use-skip.js words.js
bench.js bst.js grow.js package.json small.js trie.js use-trie.js
node_modules はありません。 この記事では npm install を1回もしていないので、消すものは自分で書いたファイルだけです。apt で入れたものもありません。
消す前に、場所を確かめます。
/home/user/cslab/btree
pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。
cslab が消えていれば終わりです。これで完全に元通りです。
残しておきたい場合は、
avl.jsとtrie.jsの2つだけコピーしておくと使い回せます。 ただし、実務でこのavl.jsを使う場面は、まず来ません。 残す価値があるのはコードではなく、③の表と④の段数の表です。あれをメモに残しておくほうが、ずっと役に立ちます。
まとめ — 理解できたこと
- バランス木の目的はただ1つ、「高さを
log nに保つ」こと。 賢い木を作る話ではなく、一直線になるのを防ぐ話。AVL木・赤黒木・B木は、目的が同じで、やり方が違うだけだった - 素朴な二分探索木に並んだ 10,000件を入れたら、高さが 10000 になった。 理想は 14。木ではなく連結リストで、しかも使わない左の子のメモリを 10,000個ぶん持っている。探索段数も 10000 で、配列の総なめと同じ
- 「ランダムなら大丈夫」ではなかった。 ばらして入れても高さ 27 で、理想の 14 の約2倍。バランスを取らない限り 14 にはならない。そして現実のデータはほぼ必ず並んでいる(IDの昇順、日付順)ので、「普通にやると最悪のケースになる」
- 回転は覚える図ではなかった。 やっているのは親子の役を入れ替えるだけで、小さい順に並べると回す前と後で完全に同じ。だから「左 < 親 < 右」は絶対に壊れない。これが回転が許される理由の全部
- 4パターン(LL / RR / LR / RL)は「4つの違う処理」ではなかった。
3,2,1/1,2,3/3,1,2/1,3,2の4通りを入れたら、4つとも同じ形の木になった。覚えるのは「重い側に一直線にしてから、逆側に回す」の1行だけ - AVL木で、並んだ 10,000件の高さが 14 になった。 100万件でも 20段で、
log2とぴったり一致。件数1000倍で高さ10段しか増えないのがO(log n)の実物 - バランスはタダではなかった。 ばらした 10,000件で、挿入が 4.1ms → 8.1ms(約2倍遅い)、探索が 3.0ms → 1.3ms(2倍以上速い)。どちらも速くなる選択肢は無い
- これが「索引を張りすぎると挿入が遅くなる」の正体だった。 索引1本ごとに木が1本あり、
INSERTのたびにその全部を組み直している - B木がデータベースの索引である理由は、木の話ではなくディスクの話だった。 ディスクは 16KB のページ単位でしか読めない。二分木だと1段降りるごとに1ページ読んで数十バイトだけ使い、100万件で20回のディスクアクセス。B木は1ページに枝を何百本も詰めるので、同じ100万件が 2〜3段
- 「索引は短い列に張れ」は気分の問題ではなかった。 鍵8バイトなら1ページに 1170本入って 2段、255バイトなら 62本で 4段。1ページに何本詰まるかが、そのまま段数になる
ORDER BYとBETWEENが索引で速いのは、B+木の葉が横に連結リストで繋がっているから。 1回降りたらあとは歩くだけ。逆にハッシュ索引では範囲検索が原理的にできないLIKE '%文字%'で索引が効かない理由も、木の形で説明できた。 B+木は先頭から比べて降りる木なので、先頭が決まっていないと降りる枝が決まらない。全文検索エンジンが別に必要なのは、この制約のため- 赤黒木は「AVL木より速い」のではなく、「どこを速くするかの選択が違う」だけだった。 バランスの条件が緩い(高さの差が2倍以内)ので回転が少なく挿入削除が速い / 高さが少し高いので探索は少し遅い。
std::map・TreeMap・Linux の CFS スケジューラが使っているので、書いたことがないのに毎秒何千回も使っている - トライは、件数が100倍になっても引く時間が変わらなかった。 見る回数が単語の長さだけで決まるから。100件で 24.2ms、10,000件で 14.9ms(10万回あたり)。
O(log n)よりさらに強い性質 - トライの代償はメモリで、
Setの 8倍(322KB 対 2,663KB)。1文字ごとにMapを1つ持つから。Setでできることに使う理由は無く、Setにできないこと(接頭辞)だけに使う - スキップリストは木ではなかった。 連結リストを重ねてコインで段を決めるだけ。回転が1行も要らないので、AVL木の 70行に対して 49行。それで挿入 71ms 対 63ms、高さ 16 対 17 とほぼ同じ。Redis の Sorted Set の中身がこれ
- 「範囲で取りたい」という要求は、必ず「横に繋がった一列」を要求する。 B+木の葉の連結リストも、スキップリストの最下段も、同じ発想だった
- データ構造は性能で選ぶものではなく、「答えたい問い」で選ぶものだった。 「あるか」ならハッシュ、「範囲」ならB+木、「先頭一致」ならトライ、「部分一致」なら接尾辞配列、「近いもの」ならk-d木。問いが違えば、どんなに速い構造でも答えられない
- そして、これらを自分で書くことは実務ではほぼ無い。 判断表の「自分で書くか」の列は、ほとんど「書かない」だった。価値があるのは書けることではなく、「なぜ索引が速いか」「なぜ索引を張りすぎると挿入が遅くなるか」「なぜ
%文字%が効かないか」の3つを説明できること。この3つは、回転の図を覚えても出てこなかった。高さを測り、段数を数えて、初めて出てきた
参考リンク
- roadmap.sh — Computer Science — このコースがどの項目を扱っているかの地図
- MySQL 公式 — Comparison of B-Tree and Hash Indexes — ④の「範囲で取れるのはB木だけ」の一次情報
- MySQL 公式 — InnoDB Index Types — クラスタ化索引と、主キーの木の葉に行が入っている話
- MySQL 公式 — Column Indexes — 索引を張る列の長さと接頭辞索引の説明
- MySQL 公式 — InnoDB Disk I/O — ページ単位でしか読めないという前提そのもの
- Redis 公式 — Sorted sets — ⑦のスキップリストが使われている場所
- Redis 公式 — ZRANGE — 範囲取りのコマンド。最下段を歩く操作にあたる
- MDN — Map — ⑥でトライの子に使ったもの。メモリの話の原因
- MDN — Set — ⑥で比較対象にしたもの。接頭辞で引く方法が無いことが仕様から分かる
- Node.js 公式 — process.memoryUsage — ⑥のメモリ測定に使った関数
- Node.js 公式 — コマンドラインオプション — つまずき7で必要になった
--expose-gc - Linux カーネル公式ドキュメント — Red-black Trees — ⑤の「Linux が赤黒木を使っている」の一次情報
次に読む
この記事は 【深掘り】コンピュータ科学 の 9 / 25 本目です。
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 回転で高さを log n に保つ
- B木が索引である理由
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント