バランス木とB木 — 100万件が3段で届く

バランス木とB木。均整の取れた枝分かれのデータ模型と複数のカードを収める箱、虫眼鏡。

100万件が3段で見つかるのは、木の形をしているからです。バランス木とB木を作って、索引が速い理由を確かめます。

前回: 二分探索木と3つの巡回 — 木にしたのに一直線になる

これは【深掘り】の記事です。本線の順路ではありません。 本線のデータ構造を自作する回で配列と連結リストを書き、データベースを自作する回で「索引を張ると速くなる」ところまでやった人が、その「速い」の中身を開けて見るための記事です。飛ばしても本線は進みます。

この記事のコマンドは、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行も要らない。それでほぼ同じ性能が出ます
  • これらを自分で書くことは、実務ではほぼ無い。 価値があるのは「索引が速い理由」と「索引を張りすぎると挿入が遅くなる理由」を説明できること

この記事でやること

  1. ~/cslab/btree/ を作り、素朴な二分探索木に並んだ 10,000件を入れて、高さが 10000 になることを実測する
  2. AVL木を自分で書く。各節点に高さを持たせ、単回転(LL / RR)と二重回転(LR / RL)を実装して、同じ 10,000件で高さが 14 になることを確かめる
  3. 挿入時間と探索時間を両方測って表にする。バランスを取る代償を数字で出す
  4. 赤黒木はルールだけ読む(実装しない)。AVL木との使い分けを表にする
  5. B木が索引である理由を、段数の計算で出す。枝の数を 2 / 100 / 500 に変えて必要な段数を比べる
  6. トライを書いてオートコンプリートを作り、件数に依存しないことと、メモリの代償を実測する
  7. スキップリストを書いて 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倍になっても、時間は数段しか増えない形。本線の計算量の回でやりました

① 症状を確認する:並んだデータで木が一直線になる

まず作業場所を作ります。

bash
$ mkdir -p ~/cslab/btree
$ cd ~/cslab/btree
$ node -v
v22.14.0

v20 以上なら大丈夫です。 出ない場合は本線のnpmの回に戻ってください。

この記事では npm install を1回もしません。ライブラリは使いません。 使ったら、正体を確かめるという目的が消えます。

package.json だけ置きます。これは import を使うためです。

bash
$ cat > package.json << 'EOF'
  {
    "type": "module"
  }
  EOF

素朴な二分探索木を書く

まず、バランスを取らないほうを書きます。症状を自分の目で見るためです。

bash
$ cat > bst.js << 'EOF'
  // 素朴な二分探索木(バランスを取らない)
  export class BST {
    constructor() {
      this.root = null;
      this.size = 0;
    }
  
    insert(key) {
      const node = { key, left: null, right: null };
      if (this.root === null) {
        this.root = node;
        this.size++;
        return;
      }
      let cur = this.root;
      // ⚠️ 再帰で書くとここで落ちる。だからループで降りる
      for (;;) {
        if (key < cur.key) {
          if (cur.left === null) { cur.left = node; this.size++; return; }
          cur = cur.left;
        } else if (key > cur.key) {
          if (cur.right === null) { cur.right = node; this.size++; return; }
          cur = cur.right;
        } else {
          return; // 同じ鍵は入れない
        }
      }
    }
  
    has(key) {
      let cur = this.root;
      let steps = 0;
      while (cur !== null) {
        steps++;
        if (key === cur.key) return { found: true, steps };
        cur = key < cur.key ? cur.left : cur.right;
      }
      return { found: false, steps };
    }
  
    // 高さ = 根から葉までの節点数の最大。これも再帰で書くと落ちるので自分でスタックを持つ
    height() {
      if (this.root === null) return 0;
      let max = 0;
      const stack = [{ node: this.root, depth: 1 }];
      while (stack.length > 0) {
        const { node, depth } = stack.pop();
        if (depth > max) max = depth;
        if (node.left) stack.push({ node: node.left, depth: depth + 1 });
        if (node.right) stack.push({ node: node.right, depth: depth + 1 });
      }
      return max;
    }
  }
  EOF

コードの中に2箇所、コメントで注意を書いています。 どちらも同じ話です。

insert と height を再帰で書くと、この記事の実験では落ちます。 並んだ 10,000件を入れた木の高さは 10000 です。再帰で降りると 10000段積むので、前の回でやった Maximum call stack size exceeded が出ます。 教科書の二分探索木は、たいてい再帰で書いてあります。それは「木が壊れていない」ことを暗黙に前提にしているからです。壊れた木を観察するコードは、再帰では書けません。

前の回で「自分でスタックを持つループに書き換えれば、コールスタックは溢れない」とやりました。その書き換えを、ここで実際に使っています。

並んだデータと、ばらしたデータを入れ比べる

bash
$ cat > shape.js << 'EOF'
  import { BST } from './bst.js';
  
  const N = 10000;
  
  // 1. 並んでいるデータを入れる(1,2,3,...,10000)
  const sorted = new BST();
  for (let i = 1; i <= N; i++) sorted.insert(i);
  
  // 2. 同じ10000件を、順番をぐちゃぐちゃにして入れる
  const shuffled = [];
  for (let i = 1; i <= N; i++) shuffled.push(i);
  let seed = 42;
  const rand = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
  for (let i = shuffled.length - 1; i > 0; i--) {
    const j = Math.floor(rand() * (i + 1));
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
  }
  const random = new BST();
  for (const k of shuffled) random.insert(k);
  
  const ideal = Math.ceil(Math.log2(N + 1));
  
  console.log('件数:', N);
  console.log('理想の高さ(log2):', ideal);
  console.log('--- 並んだ順に入れた木 ---');
  console.log('  節点数:', sorted.size);
  console.log('  高さ  :', sorted.height());
  console.log('  10000を探すのに降りた段数:', sorted.has(10000).steps);
  console.log('--- 順番をばらして入れた木 ---');
  console.log('  節点数:', random.size);
  console.log('  高さ  :', random.height());
  console.log('  10000を探すのに降りた段数:', random.has(10000).steps);
  EOF
$ node shape.js
件数: 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つです。

  1. 各節点が、自分を根とする部分木の高さを覚えている
  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回が余分に入る。それだけです。

実装する

bash
$ cat > avl.js << 'EOF'
  // AVL木:各節点が自分の高さを持ち、左右差が2以上になったら回して直す
  export class AVL {
    constructor() {
      this.root = null;
      this.size = 0;
      this.rotations = { LL: 0, RR: 0, LR: 0, RL: 0 };
    }
  
    // --- 高さは節点に書いてある。毎回数えない ---
    #h(node) { return node === null ? 0 : node.height; }
    #fix(node) { node.height = 1 + Math.max(this.#h(node.left), this.#h(node.right)); }
    #balance(node) { return this.#h(node.left) - this.#h(node.right); }
  
    // --- 右に回す(左が重いときに使う)---
    #rotateRight(y) {
      const x = y.left;
      y.left = x.right;   // x の右の子を y の左に付け替える
      x.right = y;        // y を x の右の子にする
      this.#fix(y);       // 下から順に高さを直す
      this.#fix(x);
      return x;           // 新しい親を返す
    }
  
    // --- 左に回す(右が重いときに使う)---
    #rotateLeft(x) {
      const y = x.right;
      x.right = y.left;
      y.left = x;
      this.#fix(x);
      this.#fix(y);
      return y;
    }
  
    insert(key) {
      this.root = this.#insert(this.root, key);
    }
  
    #insert(node, key) {
      if (node === null) {
        this.size++;
        return { key, left: null, right: null, height: 1 };
      }
      if (key < node.key) node.left = this.#insert(node.left, key);
      else if (key > node.key) node.right = this.#insert(node.right, key);
      else return node;
  
      this.#fix(node);
      const b = this.#balance(node);
  
      // 左が2段以上重い
      if (b > 1) {
        if (this.#balance(node.left) >= 0) {
          this.rotations.LL++;
          return this.#rotateRight(node);            // 単回転
        }
        this.rotations.LR++;
        node.left = this.#rotateLeft(node.left);     // 二重回転
        return this.#rotateRight(node);
      }
      // 右が2段以上重い
      if (b < -1) {
        if (this.#balance(node.right) <= 0) {
          this.rotations.RR++;
          return this.#rotateLeft(node);             // 単回転
        }
        this.rotations.RL++;
        node.right = this.#rotateRight(node.right);  // 二重回転
        return this.#rotateLeft(node);
      }
      return node;
    }
  
    has(key) {
      let cur = this.root;
      let steps = 0;
      while (cur !== null) {
        steps++;
        if (key === cur.key) return { found: true, steps };
        cur = key < cur.key ? cur.left : cur.right;
      }
      return { found: false, steps };
    }
  
    height() { return this.#h(this.root); }
  
    // 木の形を文字で出す(小さい木の確認用)
    draw(node = this.root, prefix = '', isLeft = true, out = []) {
      if (node === null) return out;
      this.draw(node.right, prefix + (isLeft ? '|   ' : '    '), false, out);
      out.push(prefix + (isLeft ? '\\-- ' : '/-- ') + node.key + ' (h' + node.height + ')');
      this.draw(node.left, prefix + (isLeft ? '    ' : '|   '), true, out);
      return out;
    }
  }
  EOF

気をつける点が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件で全部起こす

まず、小さい木で回転を目で見ます。

bash
$ cat > four.js << 'EOF'
  import { AVL } from './avl.js';
  
  // 4つの傾き方を、それぞれ最小の3件で起こす
  const cases = [
    ['LL (左の左が重い→右に1回)', [3, 2, 1]],
    ['RR (右の右が重い→左に1回)', [1, 2, 3]],
    ['LR (左の右が重い→2回)', [3, 1, 2]],
    ['RL (右の左が重い→2回)', [1, 3, 2]],
  ];
  
  for (const [name, keys] of cases) {
    const t = new AVL();
    for (const k of keys) t.insert(k);
    console.log('=== ' + name + ' : ' + keys.join(',') + ' の順に入れた ===');
    console.log(t.draw().join('\n'));
    console.log('高さ ' + t.height() + ' / 回転 ' + JSON.stringify(t.rotations) + '\n');
  }
  EOF
$ node four.js
=== 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件で①と比べる

bash
$ cat > grow.js << 'EOF'
  import { AVL } from './avl.js';
  
  // 件数を10倍ずつ増やして、高さがどう伸びるかだけ見る(全部「並んだ順」)
  for (const n of [1000, 10000, 100000, 1000000]) {
    const t = new AVL();
    const t0 = performance.now();
    for (let i = 1; i <= n; i++) t.insert(i);
    const t1 = performance.now();
    console.log(
      '件数 ' + String(n).padStart(8) +
      ' / 高さ ' + String(t.height()).padStart(3) +
      ' / log2 ' + String(Math.ceil(Math.log2(n + 1))).padStart(3) +
      ' / 挿入 ' + (t1 - t0).toFixed(0).padStart(6) + 'ms' +
      ' / 最悪の探索段数 ' + t.has(-1).steps
    );
  }
  EOF
$ node grow.js
件数     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,00010001010
10,000100001414
100,000(100000)1717
1,000,000(1000000)2020

高さが log2 とぴったり一致しています。 100万件が 20段。件数が1000倍になって、高さは 10段しか増えていません。

これが O(log n) の実物です。 本線の計算量の回でグラフとして見たものが、いま木の高さとして出ています。

[スクリーンショット: 01_高さが10000から14になる.png] — node shape.js と node grow.js の出力が両方写るように撮ります。「高さ 10000」と「高さ 14」が1枚に並ぶことが大事です。この記事の主張の全部がこの1枚に入ります。


③ 代償を測る:探索は速くなり、挿入は遅くなる

AVL木は速い。では、なぜ全部AVL木にしないのか。 タダではないからです。測ります。

bash
$ cat > bench.js << 'EOF'
  import { BST } from './bst.js';
  import { AVL } from './avl.js';
  
  const N = 10000;
  const keys = [];
  for (let i = 1; i <= N; i++) keys.push(i);
  
  // 順番をばらした同じ10000件
  const shuffled = keys.slice();
  let seed = 42;
  const rand = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
  for (let i = shuffled.length - 1; i > 0; i--) {
    const j = Math.floor(rand() * (i + 1));
    [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
  }
  
  function run(name, tree, input = keys) {
    const t0 = performance.now();
    for (const k of input) tree.insert(k);
    const t1 = performance.now();
    let sum = 0;
    for (const k of keys) sum += tree.has(k).steps;
    const t2 = performance.now();
    console.log(
      name.padEnd(22) +
      ' 高さ ' + String(tree.height()).padStart(5) +
      ' / 挿入 ' + (t1 - t0).toFixed(1).padStart(8) + 'ms' +
      ' / 全件探索 ' + (t2 - t1).toFixed(1).padStart(8) + 'ms' +
      ' / 平均段数 ' + (sum / N).toFixed(1)
    );
  }
  
  console.log('件数 ' + N + ' / 理想の高さ ' + Math.ceil(Math.log2(N + 1)) + '\n');
  run('素朴な木(並んだ順)', new BST());
  run('AVL木(並んだ順)', new AVL());
  run('素朴な木(ばらした順)', new BST(), shuffled);
  run('AVL木(ばらした順)', new AVL(), shuffled);
  
  const avl = new AVL();
  for (const k of keys) avl.insert(k);
  console.log('\nAVL木の回転回数(10000件):', avl.rotations);
  const total = Object.values(avl.rotations).reduce((a, b) => a + b, 0);
  console.log('回転の合計:', total, '/ 1件あたり', (total / N).toFixed(3), '回');
  EOF
$ node bench.js
件数 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 回

表にします。

データの入れ方木高さ挿入全件探索平均段数
並んだ順素朴な木10000136.7ms119.1ms5000.5
並んだ順AVL木147.4ms4.5ms12.4
ばらした順素朴な木274.1ms3.0ms15.4
ばらした順AVL木168.1ms1.3ms12.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)。

bash
$ cat > levels.js << 'EOF'
  // 「1つの節点から何本枝が出るか」を変えると、何段で届くかがどう変わるか
  const rows = [];
  for (const fanout of [2, 4, 100, 500, 1000]) {
    const cells = [];
    for (const n of [1000, 1000000, 100000000]) {
      cells.push(Math.ceil(Math.log(n) / Math.log(fanout)));
    }
    rows.push([fanout, ...cells]);
  }
  
  console.log('枝の数 | 1千件 | 100万件 | 1億件   (必要な段数=ディスクアクセス回数)');
  for (const [f, a, b, c] of rows) {
    console.log(
      String(f).padStart(6) + ' | ' +
      String(a).padStart(5) + ' | ' +
      String(b).padStart(7) + ' | ' +
      String(c).padStart(5)
    );
  }
  
  console.log('\n--- 16KB のページに鍵と枝を詰めたら何本になるか ---');
  const page = 16 * 1024;
  for (const keySize of [8, 16, 64, 255]) {
    const perEntry = keySize + 6; // 鍵 + ページ番号(6バイト)
    const fanout = Math.floor(page / perEntry);
    const levels = Math.ceil(Math.log(1000000) / Math.log(fanout));
    console.log(
      '鍵 ' + String(keySize).padStart(3) + 'バイト → 1ページに ' +
      String(fanout).padStart(4) + ' 本 → 100万件が ' + levels + ' 段'
    );
  }
  EOF
$ node levels.js
枝の数 | 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段
45段10段14段
1002段3段4段
5002段3段3段
10001段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 に辞書ファイルが無いことがあるので、自分で作ります。

bash
$ cat > words.js << 'EOF'
  // 単語リストを自分で作る(VMに辞書ファイルが無くても再現できるように)
  const head = ['pro', 'con', 'inter', 'trans', 'sub', 'pre', 'post', 'over', 'under', 'multi'];
  const mid = ['gram', 'duct', 'form', 'port', 'ject', 'struct', 'fer', 'mit', 'pose', 'tain'];
  const tail = ['', 'ing', 'ed', 'er', 'ion', 'able', 'ive', 'ment', 'al', 'ly'];
  
  export function makeWords(n) {
    const out = [];
    let i = 0;
    outer:
    for (const h of head) {
      for (const m of mid) {
        for (const t of tail) {
          for (let k = 0; k < 20; k++) {
            out.push(h + m + t + (k === 0 ? '' : String(k)));
            if (++i >= n) break outer;
          }
        }
      }
    }
    return out;
  }
  EOF

/usr/share/dict/words を使う例をよく見ますが、素の Ubuntu Server には入っていません。 wamerican を apt install すれば入りますが、この記事のために apt でパッケージを増やしたくないので、自分で作りました。接頭辞が共通する単語が大量に必要なので、意図的に部品の組み合わせで作っています。

トライ本体です。

bash
$ cat > trie.js << 'EOF'
  // トライ(接頭辞木):1文字ずつ枝を辿る木
  export class Trie {
    constructor() {
      this.root = { children: new Map(), end: false };
      this.size = 0;
    }
  
    insert(word) {
      let node = this.root;
      for (const ch of word) {
        if (!node.children.has(ch)) {
          node.children.set(ch, { children: new Map(), end: false });
        }
        node = node.children.get(ch);
      }
      if (!node.end) { node.end = true; this.size++; }
    }
  
    // 単語がちょうど入っているか。⚠️ 見る回数は「単語の長さ」だけ
    has(word) {
      const node = this.#walk(word);
      return node !== null && node.end;
    }
  
    // 接頭辞まで降りる
    #walk(prefix) {
      let node = this.root;
      for (const ch of prefix) {
        node = node.children.get(ch);
        if (node === undefined) return null;
      }
      return node;
    }
  
    // その接頭辞で始まる単語を集める(オートコンプリート)
    startsWith(prefix, limit = 10) {
      const start = this.#walk(prefix);
      if (start === null) return [];
      const out = [];
      const stack = [[start, prefix]];
      while (stack.length > 0 && out.length < limit) {
        const [node, word] = stack.pop();
        if (node.end) out.push(word);
        // 逆順に積むと、辞書順に近い順で出てくる
        const keys = [...node.children.keys()].sort().reverse();
        for (const ch of keys) stack.push([node.children.get(ch), word + ch]);
      }
      return out;
    }
  
    // 節点の数(メモリの話で使う)
    countNodes() {
      let n = 0;
      const stack = [this.root];
      while (stack.length > 0) {
        const node = stack.pop();
        n++;
        for (const child of node.children.values()) stack.push(child);
      }
      return n;
    }
  }
  EOF

end というフラグが要る理由を押さえてください。pro まで降りられることは、pro が単語であることを意味しません。 program の途中を通っただけかもしれません。「ここで終わる」という印が別に必要です。

startsWith は、接頭辞まで降りて、そこから下を全部集めるだけです。前の回で書いたスタックを、また使っています。

動かす

bash
$ cat > use-trie.js << 'EOF'
  import { Trie } from './trie.js';
  import { makeWords } from './words.js';
  
  const words = makeWords(10000);
  console.log('単語数:', words.length, '/ 例:', words.slice(0, 5).join(', '));
  
  const t = new Trie();
  for (const w of words) t.insert(w);
  console.log('トライに入った単語:', t.size, '/ 節点の数:', t.countNodes());
  
  console.log('\n--- オートコンプリート ---');
  for (const p of ['pro', 'progr', 'interfer', 'zzz']) {
    console.log("'" + p + "' →", t.startsWith(p, 6).join(', ') || '(候補なし)');
  }
  
  console.log('\n--- has() の確認 ---');
  console.log("has('program')      :", t.has('program'));
  console.log("has('progra')       :", t.has('progra'), '(途中までは単語ではない)');
  console.log("has('programming')  :", t.has('programming'));
  EOF
$ node use-trie.js
単語数: 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文字目を見た瞬間です。

件数に依存しないことを測る

bash
$ cat > bench-trie.js << 'EOF'
  import { Trie } from './trie.js';
  import { makeWords } from './words.js';
  
  // 1. 件数を増やしても、引く時間が変わらないか
  console.log('--- 同じ1語を10万回引く(件数を100倍にする)---');
  for (const n of [100, 1000, 10000]) {
    const words = makeWords(n);
    const t = new Trie();
    for (const w of words) t.insert(w);
    const target = words[0];
    const t0 = performance.now();
    let hit = 0;
    for (let i = 0; i < 100000; i++) if (t.has(target)) hit++;
    const t1 = performance.now();
    console.log(
      '単語 ' + String(n).padStart(5) + '件 / 節点 ' + String(t.countNodes()).padStart(6) +
      ' / 10万回で ' + (t1 - t0).toFixed(1).padStart(7) + 'ms(1回 ' +
      ((t1 - t0) * 1000000 / 100000).toFixed(0) + 'ナノ秒)'
    );
  }
  
  // 2. 接頭辞で候補を出す:トライ と 配列の総なめ
  console.log('\n--- 接頭辞で候補6件を出すのを1000回 ---');
  const words = makeWords(10000);
  const t = new Trie();
  for (const w of words) t.insert(w);
  
  let a = performance.now();
  for (let i = 0; i < 1000; i++) t.startsWith('progr', 6);
  let b = performance.now();
  console.log('トライ         :', (b - a).toFixed(1) + 'ms');
  
  a = performance.now();
  for (let i = 0; i < 1000; i++) words.filter((w) => w.startsWith('progr')).slice(0, 6);
  b = performance.now();
  console.log('配列を総なめ    :', (b - a).toFixed(1) + 'ms');
  
  const set = new Set(words);
  a = performance.now();
  for (let i = 0; i < 1000; i++) {
    const out = [];
    for (const w of set) { if (w.startsWith('progr')) out.push(w); if (out.length >= 6) break; }
  }
  b = performance.now();
  console.log('Setを総なめ     :', (b - a).toFixed(1) + 'ms(⚠️ Setは接頭辞では引けない)');
  
  // 3. ⚠️ 上の Set の測定は不公平だった。候補が最初のほうに固まっているから
  //    「最後のほうにある接頭辞」で測り直す
  console.log('\n--- 測り直し:候補が末尾にある接頭辞 (subtain) で1000回 ---');
  const late = 'subtain';
  console.log('  該当件数:', words.filter((w) => w.startsWith(late)).length);
  
  a = performance.now();
  for (let i = 0; i < 1000; i++) t.startsWith(late, 6);
  b = performance.now();
  console.log('トライ         :', (b - a).toFixed(1) + 'ms');
  
  a = performance.now();
  for (let i = 0; i < 1000; i++) {
    const out = [];
    for (const w of set) { if (w.startsWith(late)) out.push(w); if (out.length >= 6) break; }
  }
  b = performance.now();
  console.log('Setを総なめ     :', (b - a).toFixed(1) + 'ms');
  EOF
$ node bench-trie.js
--- 同じ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万回引くのにかかった時間
10011124.2ms
1,0001,07923.7ms
10,00010,75514.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 台になっていることが両方読めるように撮ります。

代償はメモリ

bash
$ cat > mem-trie.js << 'EOF'
  import { Trie } from './trie.js';
  import { makeWords } from './words.js';
  
  const which = process.argv[2]; // 'set' か 'trie'
  const words = makeWords(10000);
  
  global.gc && global.gc();
  const before = process.memoryUsage().heapUsed;
  
  let holder;
  if (which === 'set') {
    const s = new Set();
    for (const w of words) s.add(w);
    holder = s;
  } else {
    const t = new Trie();
    for (const w of words) t.insert(w);
    holder = t;
  }
  
  global.gc && global.gc();
  const after = process.memoryUsage().heapUsed;
  
  console.log(
    which.padEnd(5) + ' : ' + ((after - before) / 1024).toFixed(0) + ' KB' +
    (which === 'trie' ? ' / 節点 ' + holder.countNodes() : ' / 要素 ' + holder.size)
  );
  EOF
$ node --expose-gc mem-trie.js set
$ node --expose-gc mem-trie.js trie
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木は「傾いたら直す」ために回転が必要でした。スキップリストは、最初から確率で形を決めるので、直す必要がありません。 「最悪の場合」の保証はありません。 コインが偏れば遅くなります。ただ、その確率が実用上無視できるほど小さい、という理屈です。

実装する

bash
$ cat > skiplist.js << 'EOF'
  // スキップリスト:木ではない。連結リストを何段か重ねただけ
  const MAX = 16;
  
  export class SkipList {
    constructor() {
      this.head = { key: -Infinity, next: new Array(MAX).fill(null) };
      this.level = 1;
      this.size = 0;
    }
  
    // コインを投げて、この値を何段目まで載せるか決める
    #randomLevel() {
      let lv = 1;
      while (Math.random() < 0.5 && lv < MAX) lv++;
      return lv;
    }
  
    insert(key) {
      const update = new Array(MAX).fill(this.head);
      let cur = this.head;
      for (let i = this.level - 1; i >= 0; i--) {
        while (cur.next[i] !== null && cur.next[i].key < key) cur = cur.next[i];
        update[i] = cur;
      }
      if (cur.next[0] !== null && cur.next[0].key === key) return;
  
      const lv = this.#randomLevel();
      if (lv > this.level) this.level = lv;
      const node = { key, next: new Array(lv).fill(null) };
      for (let i = 0; i < lv; i++) {
        node.next[i] = update[i].next[i];
        update[i].next[i] = node;
      }
      this.size++;
    }
  
    has(key) {
      let cur = this.head;
      let steps = 0;
      for (let i = this.level - 1; i >= 0; i--) {
        while (cur.next[i] !== null && cur.next[i].key < key) { cur = cur.next[i]; steps++; }
      }
      cur = cur.next[0];
      return { found: cur !== null && cur.key === key, steps };
    }
  
    // 範囲で取る(一番下の段はただの連結リストなので、そのまま進むだけ)
    range(from, to) {
      let cur = this.head;
      for (let i = this.level - 1; i >= 0; i--) {
        while (cur.next[i] !== null && cur.next[i].key < from) cur = cur.next[i];
      }
      const out = [];
      cur = cur.next[0];
      while (cur !== null && cur.key <= to) { out.push(cur.key); cur = cur.next[0]; }
      return out;
    }
  }
  EOF

update 配列が要点です。 挿入するとき、各段の「どこの後ろに入れるか」を全部覚えておく必要があります。段ごとに繋ぎ替えるので、段ごとに直前の節点が要るわけです。

-Infinity を先頭に置いているのも実装の都合です。 これがないと「先頭に入れる場合」だけ特別扱いが必要になります。番兵を1個置くだけで if が消えます。

AVL木と比べる

bash
$ cat > use-skip.js << 'EOF'
  import { SkipList } from './skiplist.js';
  import { AVL } from './avl.js';
  
  const N = 100000;
  
  const s = new SkipList();
  let a = performance.now();
  for (let i = 1; i <= N; i++) s.insert(i); // 並んだ順に入れる
  let b = performance.now();
  console.log('スキップリスト: ' + s.size + '件 / 段数 ' + s.level + ' / 挿入 ' + (b - a).toFixed(0) + 'ms');
  
  const t = new AVL();
  a = performance.now();
  for (let i = 1; i <= N; i++) t.insert(i);
  b = performance.now();
  console.log('AVL木        : ' + t.size + '件 / 高さ ' + t.height() + ' / 挿入 ' + (b - a).toFixed(0) + 'ms');
  
  // 探索
  a = performance.now();
  for (let i = 1; i <= N; i++) s.has(i);
  b = performance.now();
  console.log('\nスキップリストの全件探索: ' + (b - a).toFixed(0) + 'ms');
  a = performance.now();
  for (let i = 1; i <= N; i++) t.has(i);
  b = performance.now();
  console.log('AVL木の全件探索        : ' + (b - a).toFixed(0) + 'ms');
  
  console.log('\n範囲で取る (500〜510):', s.range(500, 510).join(','));
  console.log('50000 を探すのに進んだ回数:', s.has(50000).steps);
  EOF
$ node use-skip.js
スキップリスト: 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木
段数 / 高さ1617
挿入(10万件)71ms63ms
全件探索19ms8ms
回転の実装無しLL / RR / LR / RL の4種

AVL木のほうが少し速い。でも「少し」です。 そして回転を1行も書いていません。

コードの行数を比べます。

bash
$ for f in avl.js skiplist.js trie.js bst.js; do
$   echo -n "$f: "
$   grep -v '^\s*$' $f | grep -v '^\s*//' | wc -l
$ done
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つも増えません。

赤黒木も同じ理由で実装していません。 「実装しないと分かった気になれない」は、私の思い込みでした。 分かるべきなのはトレードオフで、それは表で書けました。


後片づけ

この記事で作ったものを、全部消します。

まず、何があるか確認します。

bash
$ cd ~/cslab/btree
$ ls
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 で入れたものもありません。

消す前に、場所を確かめます。

bash
$ pwd
/home/user/cslab/btree

pwd で必ず確認してください。 これから rm -rf を打ちます。別の場所で打つと、消してはいけないものが消えます。 rm で消したものは戻りません(本線の基本コマンドの回で扱いました)。

bash
$ cd ~
$ rm -rf ~/cslab
$ ls ~

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つは、回転の図を覚えても出てこなかった。高さを測り、段数を数えて、初めて出てきた

参考リンク


次に読む

この記事は 【深掘り】コンピュータ科学 の 9 / 25 本目です。

記事
← 前の記事二分探索木と3つの巡回 — 木にしたのに一直線になる
→ 次の記事ヒープとLRUキャッシュ — 10件欲しいだけで100万件ソート

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

roadmap.sh のどこをやっているか

›CS — Balanced Trees
  • 回転で高さを log n に保つ
  • B木が索引である理由

この記事は、上の項目を実際に手を動かして確かめる回です。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次