配列は先頭への挿入が遅い — データ構造を自作する

データ構造を自作する。並んだ箱と連結した球、枝分かれした木の模型。

配列は先頭への挿入が遅くなります。データ構造を自作して、速度差を自分で測ります。

前回: 1万件で100倍になる — 計算量とO記法を測る

これは【番外編】です。 このサイトの本筋は roadmap.sh に沿った段階で、データ構造を自分で書くことはそこに載っていません。 読まなくても順路は繋がります。飛ばして構いません。 それでも書いているのは、これまでの回で作ったものが、実は全部これでできていたからです。新しいことを覚える回ではなく、既に使っていたものの中身を開ける回です。 この記事のコマンドは、すべてVMの中(Ubuntu Server)で打ちます。 新しく入れるソフトは1つもありません。使うのは node だけです。

Array と Map があります。

const list = [];
list.push('買い物');

const table = new Map();
table.set('user-1', '田中');

これで大抵のプログラムは書けます。 実際、JavaScript の回から今日までずっと、この2つだけで足りてきました。

それなのに、データ構造の教科書には必ずこう並んでいます。

連結リスト、スタック、キュー、ハッシュ表、二分探索木、平衡木、ヒープ、グラフ……

「配列と Map で足りているのに、なぜ他があるのか」 — ここに答えが出ないまま暗記すると、写経で終わります。

答えは、そんなに難しくありません。

それぞれ「何が速くて、何が遅いか」が違うからです。

配列は番号で取り出すのが一瞬ですが、先頭に入れるのが遅い。 連結リストは逆です。Map はキーで一発ですが、並べて範囲で取り出すことができない。 木は並んだまま持てるかわりに、放っておくと潰れます。

この「速い・遅い」を、読むのではなく測ります。

そして、もう1つ。この記事で書く3つは、既にこのサイトの中に出てきています。

書くものどこで既に使っていたか
連結リストOS自作の malloc。 フリーリストは、空きブロックを繋いだリストそのものでした
ハッシュ表自作データベースの索引。 「キー → ファイルの何バイト目か」の Map がこれです
木本物のデータベースの索引(B+木)。 索引が速い理由の、最後の1段

Map も malloc も索引も、この記事のどれかでできています。 中身を開けます。

対象レベル: 中級 / 区分: 必要に応じて読む

目次

この記事でわかること

  • 配列の弱点は「先頭への挿入」だということ。遅いのは、後ろの要素を全部ずらしているからであって、JavaScript が遅いからではないこと
  • 連結リストは先頭挿入が速く、途中を見るのが遅いこと。配列とちょうど裏返しだということ
  • それでも、現代のCPUでは配列のほうが速いことが多いこと。教科書どおりの結果にならない理由がメモリの連続性にあること
  • Map の中身は、ハッシュ関数・バケツ・衝突処理の3つだけだということ。魔法ではないこと
  • 衝突が増えると、ハッシュ表は O(n) に近づいて配列と変わらなくなること。「一発で引ける」は条件付きだということ
  • 二分探索木は、入れた順に関係なく、取り出すと並んでいること。Map にできないのはここだということ
  • 昇順にデータを入れると、木は一直線に潰れること。だから平衡木(AVL木・赤黒木)があること
  • B+木がデータベースで使われるのは「ディスクが塊で読む」からだということ。メモリ上の木とは前提が違うこと
  • 結論として、ほとんどの場合 Array と Map で足りること。中身を知るのは、速く書くためではなく、選べるようになるためだということ

この記事でやること

  1. 配列の push と unshift を10万件で測り、桁が違うことを確かめる
  2. 連結リストを30行で書き、同じ10万件を先頭に入れて配列と並べる。 ついでに遅い操作も測って、裏返しであることを見る
  3. ハッシュ表を40行で書く。 バケツを4つに減らして衝突を起こし、Map と並べて測る
  4. 二分探索木を書き、中間順巡回で並んで出ることを確認する。 そのあと昇順に入れて木を潰し、再帰を落とす
  5. スタックとキューを配列だけで作り、既に使っていたことを確認する

先に知る言葉

この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。

言葉意味
データ構造データの並べ方・持ち方のこと。同じデータでも、持ち方を変えると速い操作が変わります
ノードデータ1個分の入れ物。 中身と、次(や左右)への行き先を持ちます
参照「この値はどこにあるか」を指す矢印。 JavaScript ではオブジェクトを変数に入れると、中身ではなく矢印が入ります
O(n)・O(1)データが n 個のとき、手間がどう増えるかの書き方。 O(1) は個数が増えても手間が変わらない、O(n) は比例して増える、という意味です
連結リストノードを「次はこれ」で数珠つなぎにした持ち方。 番号で飛べないかわりに、繋ぎ替えが速い
ハッシュ関数文字列などから、決まった範囲の数を作る計算。 同じ入力からは必ず同じ数が出ます
バケツハッシュ表の内部にある、値を入れる仕切り。 ハッシュ関数が出した数が、そのまま仕切りの番号になります
衝突違うキーから同じバケツ番号が出てしまうこと。 必ず起きます。 避けるのではなく、起きた前提で処理します
チェイン法衝突したものを、そのバケツの中でリストにして並べるやり方。一番素直な衝突処理
二分探索木「自分より小さいものは左、大きいものは右」だけを守って作る木
中間順巡回左 → 自分 → 右 の順に木をたどること。 これをやると小さい順に出てきます
平衡木偏らないように自動で組み替える木。 AVL木・赤黒木がこれ
B+木1つのノードに大量の子を持たせた木。 ディスクに置く索引用。MySQL(InnoDB) の索引がこれ
CPUキャッシュCPUのすぐ隣にある小さくて速いメモリ。 連続した番地をまとめて先読みします。ここに当たるかで速度が変わります

1つだけ、先に釘を刺しておきます。 この記事を読んでも、あなたのプログラムは速くなりません。 自作の連結リストやハッシュ表は、本物の Array や Map より遅いからです。 目的は、速く書くことではありません。 「Map で引くのが速い」「索引を張ると速い」と言うときに、何が起きているかを自分の言葉で言えるようになることです。

準備 — 測り方を先に決める

VMの中(Ubuntu Server)で打ちます。

bash
$ node --version
v20.19.0

バージョンは違って構いません。 Node.js の回で入れたものがそのまま使えます。出てこないなら、その回に戻ってください。

bash
$ mkdir -p ~/ds
$ cd ~/ds

この記事で作るファイルは、すべて ~/ds の中だけです。 npm install は一度もしません。外部ライブラリを1つも使いません。

まず、全部の実験で使う「測る道具」を1つ作ります。

bash
$ nano measure.js

(VS Code の Remote SSH を使っているなら、そちらで作って構いません)

// measure.js — 経過時間をミリ秒で表示するだけ
function measure(label, fn) {
  const start = process.hrtime.bigint();
  const result = fn();
  const end = process.hrtime.bigint();
  const ms = Number(end - start) / 1e6;
  console.log(label.padEnd(28) + ms.toFixed(2) + ' ms');
  return result;
}

module.exports = { measure };

process.hrtime.bigint() はナノ秒単位の時刻を返します。Date.now() はミリ秒までしか出ないので、1ミリ秒を切る処理を測ると全部 0 になります。 ここでは桁が小さい実験もするので、こちらを使います。

測る前に、注意を1つ。 これから出す数字は、この記事の実機(VM・4コア・8GB)のものです。 あなたの環境では違う数字が出ます。 見てほしいのは絶対値ではなく、隣に並べた数字との「桁の差」です。 3倍か1000倍かが分かれば十分です。

配列の弱点を、実際に測る

配列は速い、と言われます。 半分正しく、半分は違います。

「末尾に足す」と「先頭に足す」を、同じ10万回で比べます。

bash
$ nano bench-array.js
const { measure } = require('./measure');
const N = 100000;

measure('push(末尾に追加)', () => {
  const a = [];
  for (let i = 0; i < N; i++) a.push(i);
  return a.length;
});

measure('unshift(先頭に追加)', () => {
  const a = [];
  for (let i = 0; i < N; i++) a.unshift(i);
  return a.length;
});
bash
$ node bench-array.js
push(末尾に追加)            4.21 ms
unshift(先頭に追加)      2683.90 ms

同じ10万回で、約640倍の差が出ました。

ここで「unshift は遅い関数なんだな」と覚えると、何も分かっていません。 遅い理由を見ます。

配列は、メモリの上に連続して並んでいます。

番号:   0    1    2    3    4
      [ A ][ B ][ C ][ D ][ E ]

末尾に F を足すときは、E の隣に置くだけです。他の要素は動きません。

      [ A ][ B ][ C ][ D ][ E ][ F ]   ← 1個置いただけ

先頭に Z を足すときは、こうはいきません。

      [ Z ][ A ][ B ][ C ][ D ][ E ]
        ↑    ← ← ← ← ← ← ← ←
      置く   A〜E を全部1つ後ろへずらす

unshift が遅いのは、「後ろの要素を全部ずらしている」からです。

要素が n 個あるとき、1回の unshift で n 個ずらします。それを n 回やるので、手間は n × n に比例します。 10万件だと、約50億回の移動です。2.7秒かかって当然です。

そして、shift(先頭を取り出す)も同じ理由で遅い。 これは後でキューの節でもう一度出てきます。

この時点で、教科書の1行目が読めるようになります。

操作配列理由
番号で取り出す a[i]O(1)先頭の番地に i × 要素の大きさ を足すだけ
末尾に足す pushO(1)隣に置くだけ
先頭に足す unshiftO(n)後ろを全部ずらす
先頭を取る shiftO(n)同上
値を探す includesO(n)先頭から順に見るしかない

「先頭への出し入れが多い」という用途があるなら、配列は向いていません。 そこで出てくるのが、次のものです。

連結リストを書く

発想はこれだけです。

「連続して並べる」のをやめる。 かわりに、それぞれが「次はこれ」を持つ。

head → [ C |次 ] → [ B |次 ] → [ A |なし ]

バラバラの場所に置いてよくなります。 だからずらす必要がありません。 先頭に足すときは、

新 → [ D |次 ] → (今までの head)
head を D に付け替える

これで終わりです。 データが何個あっても、やることは矢印の付け替え2回だけです。

30行で書く

bash
$ nano list.js
// list.js — 連結リスト
class LinkedList {
  constructor() {
    this.head = null;   // 先頭のノード。空なら null
    this.size = 0;
  }

  // 先頭に足す:矢印の付け替えだけ
  unshift(value) {
    this.head = { value, next: this.head };
    this.size++;
  }

  // 番号で取り出す:先頭から数えて歩くしかない
  get(index) {
    let node = this.head;
    for (let i = 0; i < index; i++) {
      if (node === null) return undefined;
      node = node.next;
    }
    return node === null ? undefined : node.value;
  }

  // 全部たどって合計する
  sum() {
    let total = 0;
    for (let node = this.head; node !== null; node = node.next) {
      total += node.value;
    }
    return total;
  }

  // 「node の次」を1つ外す:ここも矢印の付け替えだけ
  removeAfter(node) {
    if (node.next === null) return;
    node.next = node.next.next;
    this.size--;
  }
}

module.exports = { LinkedList };

30行です。 これが連結リストの全部です。removeAfter に注目してください。

node.next = node.next.next;

途中の1個を消すのに、これだけです。 配列で途中の1個を消したら、後ろを全部ずらします。 差はここに出ます。

両方を実測して、配列と並べる

bash
$ nano bench-list.js
const { measure } = require('./measure');
const { LinkedList } = require('./list');
const N = 100000;

// ① 先頭への追加
const arr = measure('配列  unshift × 10万', () => {
  const a = [];
  for (let i = 0; i < N; i++) a.unshift(i);
  return a;
});

const list = measure('リスト unshift × 10万', () => {
  const l = new LinkedList();
  for (let i = 0; i < N; i++) l.unshift(i);
  return l;
});

// ② 途中を1万回のぞく(毎回ばらばらの位置)
const idx = [];
for (let i = 0; i < 10000; i++) idx.push(Math.floor(Math.random() * N));

measure('配列  番号で取得 × 1万', () => {
  let s = 0;
  for (const i of idx) s += arr[i];
  return s;
});

measure('リスト 番号で取得 × 1万', () => {
  let s = 0;
  for (const i of idx) s += list.get(i);
  return s;
});
bash
$ node bench-list.js
配列  unshift × 10万       2683.90 ms
リスト unshift × 10万        12.44 ms
配列  番号で取得 × 1万         0.21 ms
リスト 番号で取得 × 1万       402.55 ms

きれいに裏返しになりました。

操作配列連結リスト
先頭に足す2683.90 ms12.44 ms(約215倍速い)
番号で取り出す0.21 ms402.55 ms(約1900倍遅い)

どちらが速いか、という質問には答えがありません。 何をするかで逆転します。 これが、この記事で一番言いたいことです。

遅いほうの理由も、はっきりしています。 連結リストには番号がありません。 list.get(50000) は、先頭から5万回 next をたどっています。 「5万番目の場所」を計算で出す方法が無いからです。

教科書どおりにならないところ

ここで、素直に測ると教科書と違う結果が出るものを、隠さずに出します。

「全部たどって合計する」を比べます。 どちらも O(n) です。理屈の上では同じ速さのはずです。

bash
$ nano bench-scan.js
const { measure } = require('./measure');
const { LinkedList } = require('./list');
const N = 100000;

const arr = [];
const list = new LinkedList();
for (let i = 0; i < N; i++) { arr.unshift(i); list.unshift(i); }

measure('配列  全部たどって合計', () => {
  let s = 0;
  for (let i = 0; i < arr.length; i++) s += arr[i];
  return s;
});

measure('リスト 全部たどって合計', () => list.sum());
bash
$ node bench-scan.js
配列  全部たどって合計        0.32 ms
リスト 全部たどって合計        1.98 ms

同じ O(n) なのに、配列のほうが6倍速い。

理由は、CPUの都合です。

  • 配列は、メモリの上に連続して並んでいます。 CPUは「1つ読んだら、その隣もどうせ使うだろう」とまとめて先読みします(CPUキャッシュ)。当たり続けます
  • 連結リストのノードは、メモリ上のバラバラの場所にあります。 次の行き先は矢印をたどってみるまで分かりません。 先読みできません

計算量の記号は、メモリの都合を無視しています。 O(n) は「回数」の話で、1回あたりの値段が同じだとは言っていません。

現代のCPUでは、「配列のほうが速い」ことのほうが多いのが実情です。教科書に「連結リストは挿入が速い」と書いてあるのは正しいのですが、実際のプログラムでは、挿入より走査のほうが圧倒的に回数が多いからです。

それでも連結リストが要る場面があります。

  • 要素の場所(アドレス)が動いてはいけないとき。 配列は伸ばすときに丸ごと引っ越すことがあります
  • 「今持っているこの1個の、次を外す」ができれば十分なとき。 番号で引く必要が無いなら、リストの弱点は消えます
  • そもそも配列が使えないとき。 ここが次です

OS自作のフリーリストが、まさにこれだった

メモリ管理の回で、malloc を自作しました。ヒープの中は、こう並んでいました。

+--------+--------+------------------+--------+--------+------------+
| size   | used   | 実際に配る64バイト | size   | used   | 実際に配る… |
+--------+--------+------------------+--------+--------+------------+

あのとき「フリーリスト」と呼んだものが、連結リストです。 そして、あそこでは配列を使うことが原理的にできませんでした。

malloc は、メモリを配るプログラムです。 「空きブロックの一覧」を配列で持とうとすると、その配列を置くメモリを malloc で確保することになります。

自分を呼ばないと自分が動かない、という循環です。 だから、配るメモリそのものの中に管理情報を書き込んで、繋ぐしかありませんでした。あれは工夫ではなく、唯一の手だったわけです。

そして、free が O(1) だったことも、いま説明できます。

void kfree(void *p) {
    ((struct block *)p - 1)->used = 0;
}

「渡された場所の手前を書き換えるだけ」 — 連結リストの removeAfter と同じ、矢印の付け替えです。後ろを全部ずらすようなことは、一度もしていません。

ハッシュ表を書く — Map の中身

次は、ずっと使ってきた Map です。

const m = new Map();
m.set('user-1', '田中');
m.get('user-1');   // '田中'

キーが10万件あっても、get は一瞬で返ります。 なぜでしょうか。

「一瞬で返る」を素朴に考えると、あり得ないことが分かります。配列で 'user-1' を探すなら、先頭から順に照合するしかありません。 10万件なら10万回です。Map はそれをやっていません。

答えは、探していないからです。

キーの文字列から、置き場所の番号を「計算で」出している。

これがハッシュ表です。 部品は3つだけです。

部品役割
① ハッシュ関数文字列 → 数 に変換する。'user-1' → 731 のように
② バケツその番号の仕切りに値を入れる。 配列の1マス
③ 衝突処理違うキーから同じ番号が出たときにどうするか

③が要る理由は、単純です。 キーの種類は無限にありますが、バケツの数は有限です。必ずぶつかります。 「ぶつからないようにする」のではなく、「ぶつかった前提で処理する」のが正解です。

40行で書く

一番素直な衝突処理は、チェイン法です。 バケツの中を配列にして、ぶつかったものを並べて入れます。

バケツ[3] → [ ['user-1','田中'], ['user-77','鈴木'] ]
                ↑ ここだけ順に照合する
bash
$ nano hash.js
// hash.js — ハッシュ表(チェイン法)
class HashTable {
  constructor(bucketCount = 1024) {
    this.buckets = new Array(bucketCount);
    for (let i = 0; i < bucketCount; i++) this.buckets[i] = [];
    this.count = 0;
  }

  // ① ハッシュ関数:文字列 → バケツ番号
  hash(key) {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = (h * 31 + key.charCodeAt(i)) | 0;   // |0 で32bit整数に丸める
    }
    return Math.abs(h) % this.buckets.length;
  }

  set(key, value) {
    const bucket = this.buckets[this.hash(key)];
    for (const pair of bucket) {          // ③ 同じキーが既に居ないか
      if (pair[0] === key) { pair[1] = value; return; }
    }
    bucket.push([key, value]);            // ② 無ければ末尾に足す
    this.count++;
  }

  get(key) {
    const bucket = this.buckets[this.hash(key)];
    for (const pair of bucket) {          // ③ バケツの中だけ順に照合
      if (pair[0] === key) return pair[1];
    }
    return undefined;
  }

  // 一番混んでいるバケツの中身の数
  longestBucket() {
    let max = 0;
    for (const b of this.buckets) if (b.length > max) max = b.length;
    return max;
  }
}

module.exports = { HashTable };

これで Map の中身は説明が付きます。 動かします。

bash
$ nano try-hash.js
const { HashTable } = require('./hash');

const h = new HashTable(1024);
h.set('user-1', '田中');
h.set('user-2', '鈴木');

console.log(h.get('user-1'));           // 田中
console.log(h.get('user-999'));         // undefined
console.log('user-1 のバケツ番号:', h.hash('user-1'));
console.log('user-2 のバケツ番号:', h.hash('user-2'));
bash
$ node try-hash.js
田中
undefined
user-1 のバケツ番号: 337
user-2 のバケツ番号: 336

h.get('user-1') は、1024個あるバケツのうち337番だけを見ています。 他の1023個は触ってもいません。 これが「一発で引ける」の中身です。

* 31 に意味はあるのか、と思ったはずです。 あります。 31は奇数の素数で、桁が散らばりやすいことが経験的に知られています。Java の文字列ハッシュがこれを使っていることで有名になりました。 ただし「これでなければならない」わけではありません。 大事なのはバケツに均等にばらけることだけです。次の実験で、ばらけないとどうなるかを見ます。

衝突を実際に起こす — バケツを4つに減らす

バケツを1024個から4個に減らします。 2万件のキーを入れれば、1つのバケツに平均5000件が詰まります。

bash
$ nano bench-hash.js
const { measure } = require('./measure');
const { HashTable } = require('./hash');
const N = 20000;

const keys = [];
for (let i = 0; i < N; i++) keys.push('key-' + i);

function run(bucketCount) {
  console.log('--- バケツ ' + bucketCount + ' 個 ---');
  const h = measure('  set × 2万', () => {
    const t = new HashTable(bucketCount);
    for (const k of keys) t.set(k, k.length);
    return t;
  });
  measure('  get × 2万', () => {
    let s = 0;
    for (const k of keys) s += h.get(k);
    return s;
  });
  console.log('  一番混んだバケツ:       ' + h.longestBucket() + ' 件');
}

run(1024);
run(4);

console.log('--- 本物の Map ---');
const m = measure('  set × 2万', () => {
  const t = new Map();
  for (const k of keys) t.set(k, k.length);
  return t;
});
measure('  get × 2万', () => {
  let s = 0;
  for (const k of keys) s += m.get(k);
  return s;
});
bash
$ node bench-hash.js
--- バケツ 1024 個 ---
  set × 2万                    9.87 ms
  get × 2万                    6.12 ms
  一番混んだバケツ:       34 件
--- バケツ 4 個 ---
  set × 2万                  254.31 ms
  get × 2万                  231.77 ms
  一番混んだバケツ:       5002 件
--- 本物の Map ---
  set × 2万                    3.14 ms
  get × 2万                    1.42 ms

同じコード、同じデータ、違うのはバケツの数だけで、約38倍になりました。

なぜかは、もう分かるはずです。

  • バケツ1024個: 1つのバケツに平均20件。get は20件を順に照合して終わり
  • バケツ4個: 1つのバケツに平均5000件。get は5000件を順に照合する

バケツの中は、ただの配列の全走査です。 つまり、

衝突が増えると、ハッシュ表は O(1) から O(n) に近づきます。 極端な話、バケツが1個ならただの配列です。

「ハッシュ表は O(1)」は、条件付きの主張でした。条件は「キーがバケツに均等にばらけていること」です。

だから本物の Map は、中身が詰まってくると自動でバケツを増やして全部入れ直します(リハッシュ)。この記事の自作版はそれをやっていないので、件数が増えると勝手に遅くなります。

これは机上の話ではありません。 ハッシュ関数の弱さを突いて、わざと全部同じバケツに落ちるキーを大量に送り付ける攻撃が実在します(ハッシュ衝突攻撃)。受け取ったJSONのキーをそのままハッシュ表に入れるサーバーが狙われました。 いまの言語やライブラリは、起動ごとにハッシュ関数へ乱数を混ぜてこれを防いでいます。

自作データベースの索引が、これだった

データベースを自作した回で、索引を足して読み出しが2000倍速くなりました。そのとき書いたのは、これだけです。

索引の正体は「キー → ファイルの何バイト目か」の Map。

その Map の中身が、いま書いたものです。 そして、あの回で残した2つの宿題が、ここで完全に説明が付きます。

① 「索引がメモリに載らなくなると、速度は出ない」

バケツの配列がメモリ上にあるから、番号で一発で飛べます。 バケツがディスクにあったら、番号を計算しても、そこを読むのにディスクアクセスが要ります。 ハッシュ表はメモリ上でしか本領を出しません。

② 「ハッシュ索引では範囲検索ができない」

理由が、いま目の前にあります。

'key-1'  → バケツ 67
'key-2'  → バケツ 68
'key-3'  → バケツ 69
'key-9'  → バケツ 75
'key-10' → バケツ 947
'key-11' → バケツ 946

ハッシュ関数は、わざと「散らす」ための計算です。 この単純な * 31 のハッシュでは、末尾1文字だけ違うキーがたまたま隣り合った番号に入りますが、'key-10' で一気に 947 へ飛び、'key-11' は逆に 946 へ戻ります。 キーの並び順とバケツの並び順は一致せず、隣り合ったキーが、隣り合ったバケツに入る保証はどこにもありません。

なので、WHERE id BETWEEN 100 AND 200 をハッシュ索引でやろうとすると、101件ぶんのハッシュを1つずつ計算して引くか、全部走査するしかありません。 ORDER BY に至っては、バケツを全部集めて並べ替えることになります。

「並んでいない」ことが、ハッシュ表の唯一にして最大の弱点です。

そして、これが次のものが存在する理由です。

二分探索木を書く — 並んだまま持てる

やりたいことは、これです。

キーで速く引きたい。かつ、取り出したら並んでいてほしい。

答えは、木です。 規則は1つだけです。

自分より小さいものは左、大きいものは右。

5, 3, 8, 1, 4, 7, 9 の順に入れると、こうなります。

            5
          /   \
        3       8
       / \     / \
      1   4   7   9

探すときは、根から降りるだけです。 4 を探すなら、5 より小さい → 左へ、3 より大きい → 右へ、着きました。 2回で見つかっています。7件を2回です。

1段降りるごとに、候補が半分になります。 だから100万件でも20回程度で着きます。

挿入と探索を書く

bash
$ nano bst.js
// bst.js — 二分探索木
class BST {
  constructor() { this.root = null; }

  insert(value) {
    const node = { value, left: null, right: null };
    if (this.root === null) { this.root = node; return; }
    let cur = this.root;
    for (;;) {
      if (value === cur.value) return;            // 同じ値は入れない
      if (value < cur.value) {
        if (cur.left === null) { cur.left = node; return; }
        cur = cur.left;
      } else {
        if (cur.right === null) { cur.right = node; return; }
        cur = cur.right;
      }
    }
  }

  has(value) {
    let cur = this.root;
    while (cur !== null) {
      if (value === cur.value) return true;
      cur = value < cur.value ? cur.left : cur.right;
    }
    return false;
  }

  // 中間順巡回:左 → 自分 → 右
  inorder(visit) {
    const walk = (node) => {
      if (node === null) return;
      walk(node.left);
      visit(node.value);
      walk(node.right);
    };
    walk(this.root);
  }

  // 木の高さ(再帰だと偏った木で落ちるので、あえて反復で書く)
  height() {
    let max = 0;
    const stack = [[this.root, 1]];
    while (stack.length > 0) {
      const [node, depth] = stack.pop();
      if (node === null) continue;
      if (depth > max) max = depth;
      stack.push([node.left, depth + 1], [node.right, depth + 1]);
    }
    return max;
  }
}

module.exports = { BST };

挿入と探索は、どちらも「降りるだけ」です。 insert と has がほとんど同じ形をしていることに注目してください。探して、見つからなかった場所に置く、それが挿入です。

中間順巡回で、並んだ順に出る

bash
$ nano try-bst.js
const { BST } = require('./bst');

const t = new BST();
for (const v of [5, 3, 8, 1, 4, 7, 9]) t.insert(v);

const out = [];
t.inorder((v) => out.push(v));
console.log('入れた順:', [5, 3, 8, 1, 4, 7, 9].join(' '));
console.log('出てくる順:', out.join(' '));
console.log('4 はある?', t.has(4), ' / 6 はある?', t.has(6));
console.log('木の高さ:', t.height());
bash
$ node try-bst.js
入れた順: 5 3 8 1 4 7 9
出てくる順: 1 3 4 5 7 8 9
4 はある? true  / 6 はある? false
木の高さ: 3

バラバラに入れたのに、並んで出てきました。 並べ替えは1回もしていません。

これが Map にできないことです。 Map は「入れた順」を覚えているだけで、キーの大小を一度も見ていません。 木は入れる場所を決めるときに毎回大小を見ているので、出すときには既に並んでいます。

そして、これが「範囲で取り出す」を可能にします。 3以上8以下 が欲しければ、中間順巡回を3で始めて8で止めるだけです。ハッシュ表にはこれができません。

昇順に入れると一直線になる

ここまでは、木の良い話です。 壊します。

さっきの例は 5, 3, 8, 1, ... とバラバラに入れました。 昇順に入れたらどうなるでしょうか。

1, 2, 3, 4, 5 の順に入れます。規則は「大きいものは右」なので、

1
 \
  2
   \
    3
     \
      4
       \
        5

木ではなく、ただの一本道になりました。これは連結リストと同じ形です。 つまり has が O(n) です。木にした意味が消えます。

測ります。

bash
$ nano bench-bst.js
const { measure } = require('./measure');
const { BST } = require('./bst');
const N = 20000;

// ① ばらばらな順で入れる
const shuffled = [];
for (let i = 0; i < N; i++) shuffled.push(i);
for (let i = N - 1; i > 0; i--) {
  const j = Math.floor(Math.random() * (i + 1));
  [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]];
}

const t1 = measure('ばらばら順 insert × 2万', () => {
  const t = new BST();
  for (const v of shuffled) t.insert(v);
  return t;
});
console.log('  木の高さ:                 ' + t1.height());
measure('ばらばら順 has × 2万', () => {
  let c = 0;
  for (let i = 0; i < N; i++) if (t1.has(i)) c++;
  return c;
});

// ② 昇順で入れる
const t2 = measure('昇順     insert × 2万', () => {
  const t = new BST();
  for (let i = 0; i < N; i++) t.insert(i);
  return t;
});
console.log('  木の高さ:                 ' + t2.height());
measure('昇順     has × 2万', () => {
  let c = 0;
  for (let i = 0; i < N; i++) if (t2.has(i)) c++;
  return c;
});
bash
$ node bench-bst.js
ばらばら順 insert × 2万        9.63 ms
  木の高さ:                 33
ばらばら順 has × 2万           6.71 ms
昇順     insert × 2万       412.88 ms
  木の高さ:                 20000
昇順     has × 2万          448.15 ms

木の高さが 33 と 20000 です。

同じデータ、同じコード、違うのは入れた順番だけで、探索が約67倍遅くなりました。 高さ20000は、2万件を一直線に繋いだということです。

そして、これは特殊な意地悪ではありません。

昇順に入れるのは、現実で最もよくある入れ方です。

  • id を1から順に振ったデータを、順に読み込む
  • 日付順に並んだログを、上から入れる
  • ソート済みのCSVをそのまま流し込む

「たまたま最悪」ではなく、「普通にやると最悪」です。ここが厄介なところです。

さらに、この木で inorder を呼ぶと落ちます。

t2.inorder((v) => {});
RangeError: Maximum call stack size exceeded

再帰の深さが、木の高さそのものだからです。 高さ20000の木をたどると、関数が2万段積まれます。 これについては「つまずいたところ」でもう一度触れます。

だから平衡木(AVL木・赤黒木)がある

「偏ったら、組み替えればいい」 — それをやるのが平衡木です。

発想はこうです。

挿入のたびに左右の高さを見て、偏っていたら回転して直す。

   1                     2
    \                   / \
     2      ⟶      1     3
      \
       3

この「回転」を、挿入・削除のたびに自動でやります。 そうすると、どんな順で入れても高さは log n あたりに収まります。

名前特徴
AVL木厳しく平衡を保つ。 高さが低く抑えられるので探索が速い。 そのぶん回転の回数が多く、挿入が重い
赤黒木ゆるく平衡を保つ。 回転が少ないので挿入・削除が速い。 実際のライブラリで採用されることが多い

この記事では、平衡木は実装しません。 回転の場合分けだけで記事1本ぶんあり、「なぜ要るか」が分かった時点で、この回の目的は達成されているからです。

大事なのは、これです。

平衡木は、賢い木ではありません。 潰れる木への対処です。

B+木がデータベースで使われる理由

ここで、パフォーマンスの回の宿題を回収します。

MySQL の索引は、二分探索木でも赤黒木でもなく、B+木です。 なぜでしょうか。

理由は、木の性能ではありません。 置き場所が違うからです。

二分探索木B+木
置き場所メモリディスク
1ノードの子の数2個数百個
高さ(100万件)約20約3

ディスクは、1バイトだけ読むということができません。 必ず塊(ページ、たいてい4KB〜16KB)で読みます。

1バイト読むのも、16KB読むのも、かかる時間はほとんど同じ。

この前提だと、「1ノードに値を2個しか入れない」のは、とんでもない無駄です。 16KB読んで、使うのは数バイトだからです。

なので、B+木はこうします。

1ノードに、ディスクの1ページぶん(数百個)のキーを詰め込む。

すると、1回のディスク読み込みで数百方向に枝分かれできます。 100万件でも高さ3、つまりディスクを3回読めば着きます。

二分探索木で同じことをすると、高さ20 = ディスク20回です。メモリなら20回はタダ同然ですが、ディスクでは7倍の差になります。

そして、B+木の「+」の部分。

一番下の段(葉)だけが実データを持ち、葉どうしが横一列に繋がっている。

この横の繋がりが、連結リストです。 だから WHERE id BETWEEN 100 AND 200 は、木を降りて100に着いたあと、葉を横にたどるだけで済みます。木を登り直しません。

この記事の3つが、全部入っています。

B+木の部品正体
枝分かれ木
葉の横の繋がり連結リスト
1ノードの中でのキー探索並んだ配列の二分探索

「索引が速い」の全体像が、これでようやく閉じました。

スタックとキュー — もう使っている

残る2つは、実装するようなものではありません。 配列で足ります。

出し入れの規則配列でのやり方
スタック後入れ先出し。 最後に入れたものが最初に出るpush と pop
キュー先入れ先出し。 最初に入れたものが最初に出るpush と shift
// スタック:積んだ皿を上から取る
const stack = [];
stack.push('A'); stack.push('B'); stack.push('C');
console.log(stack.pop());   // C

// キュー:レジの行列
const queue = [];
queue.push('A'); queue.push('B'); queue.push('C');
console.log(queue.shift()); // A

そして、この2つは既に何度も出てきています。

スタックは、さっき自分で溢れさせました。

RangeError: Maximum call stack size exceeded

「コールスタック」の「スタック」です。 関数を呼ぶと積まれ、return すると上から降ろされる。後入れ先出しそのものです。溢れたのは、この記事のデータ構造の話でした。

キューは、メッセージキューの回です。「待たせるAPIをやめる」ために、仕事を並べて先入れ先出しで処理しました。 Redis の回で触ったリスト型も、両端から出し入れできるので同じ用途に使えます。

ただし、キューを配列でやるときは1つ注意があります。

shift は O(n) です。 この記事の最初に測ったとおり、後ろを全部ずらします。

数百件なら気にしなくて構いません。 数十万件のキューを配列の shift で回すと、そこが詰まります。 そのときは、先頭を消さずに「読んだ位置」を数字で覚えるか、両端キュー(デック)を使います。「先頭の出し入れが多いなら配列は向いていない」という、この記事の最初の話に戻ってきます。

選び方 — やりたいことから引く表

構造の名前から入ると覚えられません。 やりたいことから引きます。

やりたいこと使うデータ構造JavaScript での実物
番号で取り出す・順番に全部見る配列Array
キーから値を一発で引くハッシュ表Map(キーが文字列なら普通のオブジェクトでも)
重複を消したい・あるか無いかだけ知りたいハッシュ集合Set
後入れ先出しスタックArray の push / pop
先入れ先出しキューArray の push / shift(大量ならメッセージキュー)
先頭・途中の出し入れが極端に多い連結リスト標準には無い。自分で書く(が、まず配列で測ってから)
並んだまま持って範囲で取り出す平衡木・B+木標準には無い。データベースの索引に任せる
常に最小(最大)を取り出すヒープ(優先度付きキュー)標準には無い
繋がり方そのものを扱うグラフ標準には無い

下の3つに「標準には無い」が並んでいることに、意味があります。

JavaScript が用意しているのは、配列とハッシュ系だけです。 他は自分で書くか、それを内蔵した道具(データベース・メッセージキュー)に任せることになります。

そして実務では、後者がほぼ正解です。 「並んだまま範囲で引きたい」なら、自作の平衡木ではなく、索引を張ったデータベースに任せます。

つまずいたところ

素直に書いた順に残します。

① inorder が RangeError で落ちた

昇順で入れた木を巡回した瞬間、これが出ました。

RangeError: Maximum call stack size exceeded

最初はバグを疑いました。 違いました。木の高さが20000だったので、再帰が2万段積まれただけです。ばらばら順の木(高さ33)では、まったく同じコードが普通に動きます。

ここで学んだのは、「再帰で木をたどるコードは、木が平衡である前提で書かれている」ということです。だから height() だけは最初から反復で書いてあります。 再帰で書くと、高さを測ろうとした瞬間に落ちて、高さが分からないという間抜けなことになります。

② unshift を1000件で測って、差が出なかった

最初は N = 1000 で測りました。

push(末尾に追加)            0.09 ms
unshift(先頭に追加)          0.71 ms

8倍しか違わず、「教科書は大げさなのか」と思いました。 違いました。n × n に比例するものは、n が小さいうちは差が出ません。 1000件では50万回のずらしで、これは一瞬です。10万件にして初めて50億回になり、桁が変わりました。

「小さいデータで測って差が無いから大丈夫」は、この種の問題で一番危険な結論です。 本番のデータ量で初めて牙をむきます。

③ ハッシュ関数で、バケツ番号が負の数になった

最初、hash の最後をこう書いていました。

return h % this.buckets.length;

一部のキーで get が必ず undefined を返しました。 調べると、バケツ番号が -133 のような負の数になっていました。

原因は | 0 です。 32bit整数に丸めるとき、上の桁が立っていると負の数になります。 JavaScript の % は割られる数の符号を引き継ぐので、負のまま出ます。そして this.buckets[-133] はエラーにならず undefined を返すので、気付くのが遅れました。

Math.abs() を挟んで直しました。「配列の範囲外がエラーにならない」というJavaScriptの性質が、ここで牙をむきました。

④ 連結リストが配列より遅くて、実装を疑った

「全部たどって合計」で配列に負けたとき、自分の連結リストの書き方が悪いのだと思って30分探しました。 バグはありませんでした。メモリの連続性の差で、こうなるのが正常です。

教科書の O(n) は、これを教えてくれません。 測らないと分からないことがある、という良い例でした。

後片づけ

この記事で作ったものは、すべて ~/ds の中のテキストファイルだけです。

bash
$ cd ~
$ rm -rf ~/ds

入れたパッケージはありません。 apt も npm install も一度も使っていないので、戻すものは何もありません。 VMの状態は、この記事を読む前とまったく同じです。

もし手元に残しておきたいなら、消さなくて構いません。 全部合わせて20KB程度です。

まとめ

  • 「配列と Map があるのに、なぜ他があるのか」の答えは、「何が速くて何が遅いかが違うから」。 どちらが優秀か、という質問には答えが無い
  • 配列の弱点は先頭への出し入れ。 10万件の unshift で 2683ms、push は 4.21ms。約640倍
  • 遅い理由は「後ろを全部ずらしているから」。 n回の unshift は n × n に比例する。JavaScript が遅いのではない
  • 連結リストは裏返し。 同じ10万件の先頭挿入が 12.44ms(215倍速い)、番号での取得は 402ms(1900倍遅い)
  • 連結リストは、矢印の付け替えだけで挿入・削除ができる。 かわりに番号で飛べない(計算で場所が出せない)
  • 全部たどる処理は、同じ O(n) でも配列が6倍速かった。 理由はメモリが連続していてCPUが先読みできるから
  • 計算量の記号は「回数」しか語らない。 1回あたりの値段は同じではない。 教科書どおりにならないのは、ここ
  • OS自作のフリーリストは連結リストそのものだった。 しかも配列を使うことが原理的にできなかった(malloc を作るのに malloc が要る)
  • free にサイズを渡さなくていいのと、removeAfter が一瞬なのは、同じ理由。矢印の付け替えだけだから
  • ハッシュ表の部品は3つだけ。 ハッシュ関数・バケツ・衝突処理。40行で書ける
  • get が速いのは、探していないから。 キーから置き場所を計算で出して、そのバケツだけ見る
  • バケツを1024個から4個に減らしたら、約38倍遅くなった。 一番混んだバケツが 34件 → 5002件
  • つまり衝突が増えると O(1) は O(n) に近づく。 「ハッシュ表は O(1)」は、均等にばらける前提での話
  • 本物の Map は詰まってくると自動でバケツを増やす(リハッシュ)。 自作版はやっていないので、増えると勝手に遅くなる
  • 自作データベースの索引は、このハッシュ表だった。 範囲検索ができない理由は「ハッシュはわざと散らす計算だから」
  • 二分探索木の規則は「小さいものは左、大きいものは右」の1つだけ。 挿入と探索はほとんど同じコードになる
  • 中間順巡回(左 → 自分 → 右)で、並べ替えなしに小さい順で出てくる。 Map にできないのはここ
  • 昇順に入れると木は一直線になる。 2万件で高さ20000、探索が約67倍遅くなった
  • しかも昇順は現実で一番よくある入れ方(id 順、日付順、ソート済みCSV)。「普通にやると最悪」
  • だから平衡木(AVL木・赤黒木)がある。 賢い木ではなく、潰れる木への対処
  • B+木がデータベースで使われるのは、木の性能ではなく置き場所の都合。 ディスクは塊で読むから、1ノードに数百個詰める
  • 100万件でも高さ3。 ディスク3回で着く。二分探索木なら高さ20 = ディスク20回
  • B+木の葉は横に繋がっている=連結リスト。 だから範囲検索で木を登り直さずに済む
  • スタックとキューは配列で足りる。 そして既に使っていた: コールスタック(Maximum call stack size exceeded の正体)とメッセージキュー
  • ただし配列の shift は O(n)。 大量のキューを配列で回すと詰まる
  • 結論: ほとんどの場合 Array と Map で足りる。 自作の構造は、標準のものより遅い
  • 中身を知る意味は、速く書くためではなく、選べるようになるため。 「この処理が遅いのは、先頭に挿入しているからだ」と言えることが成果

参考リンク


この段階の確認

【番外編】roadmap.sh の外 は、ここで終わりです。 次に進む前に、答えを見ずに試してください。

読み終えた直後は、たいてい「分かった気」になっています。 手が動くかどうかは別です。

説明できますか

  1. ここは飛ばしてよいと書いてあるのに、なぜ用意されているのか
  2. Windows Server は、Linuxと何が決定的に違うのか
  3. 自作してみることの価値は、どこにありますか

手が動きますか

  • 触った範囲で、実務で出会ったときに困らない程度の地図を自分で描く
  • 興味の無い項目は、堂々と飛ばす(ここは順路ではありません)

1つでも詰まったら、飛ばした回があります。 そこへ戻ってください。戻るのは後退ではありません。 戻り先の目安: 番外編の各回(順路ではないので、必要になったときだけ戻れば十分です)

全部答えられたなら、次の段階へ進んでください。


次に読む

この記事は 【番外編】roadmap.sh の外 の 35 / 35 本目です。

記事
← 前の記事1万件で100倍になる — 計算量とO記法を測る
→ 次の記事ファイル操作 rm・cp・mv・ln — 消したものは戻らない

ここは番外編です。 本筋から外れているので、飛ばして構いません。

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

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

【番外編】データ構造。roadmap.sh の Computer Science 側の話で、本筋の範囲外。

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

コメント

コメントする

目次