配列は先頭への挿入が遅くなります。データ構造を自作して、速度差を自分で測ります。
これは【番外編】です。 このサイトの本筋は 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で足りること。中身を知るのは、速く書くためではなく、選べるようになるためだということ
この記事でやること
- 配列の
pushとunshiftを10万件で測り、桁が違うことを確かめる - 連結リストを30行で書き、同じ10万件を先頭に入れて配列と並べる。 ついでに遅い操作も測って、裏返しであることを見る
- ハッシュ表を40行で書く。 バケツを4つに減らして衝突を起こし、
Mapと並べて測る - 二分探索木を書き、中間順巡回で並んで出ることを確認する。 そのあと昇順に入れて木を潰し、再帰を落とす
- スタックとキューを配列だけで作り、既に使っていたことを確認する
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| データ構造 | データの並べ方・持ち方のこと。同じデータでも、持ち方を変えると速い操作が変わります |
| ノード | データ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)で打ちます。
v20.19.0
バージョンは違って構いません。 Node.js の回で入れたものがそのまま使えます。出てこないなら、その回に戻ってください。
この記事で作るファイルは、すべて ~/ds の中だけです。 npm install は一度もしません。外部ライブラリを1つも使いません。
まず、全部の実験で使う「測る道具」を1つ作ります。
(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万回で比べます。
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;
});
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 × 要素の大きさ を足すだけ |
末尾に足す push | O(1) | 隣に置くだけ |
先頭に足す unshift | O(n) | 後ろを全部ずらす |
先頭を取る shift | O(n) | 同上 |
値を探す includes | O(n) | 先頭から順に見るしかない |
「先頭への出し入れが多い」という用途があるなら、配列は向いていません。 そこで出てくるのが、次のものです。
連結リストを書く
発想はこれだけです。
「連続して並べる」のをやめる。 かわりに、それぞれが「次はこれ」を持つ。
head → [ C |次 ] → [ B |次 ] → [ A |なし ]
バラバラの場所に置いてよくなります。 だからずらす必要がありません。 先頭に足すときは、
新 → [ D |次 ] → (今までの head)
head を D に付け替える
これで終わりです。 データが何個あっても、やることは矢印の付け替え2回だけです。
30行で書く
// 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個を消したら、後ろを全部ずらします。 差はここに出ます。
両方を実測して、配列と並べる
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;
});
配列 unshift × 10万 2683.90 ms
リスト unshift × 10万 12.44 ms
配列 番号で取得 × 1万 0.21 ms
リスト 番号で取得 × 1万 402.55 ms
きれいに裏返しになりました。
| 操作 | 配列 | 連結リスト |
|---|---|---|
| 先頭に足す | 2683.90 ms | 12.44 ms(約215倍速い) |
| 番号で取り出す | 0.21 ms | 402.55 ms(約1900倍遅い) |
どちらが速いか、という質問には答えがありません。 何をするかで逆転します。 これが、この記事で一番言いたいことです。
遅いほうの理由も、はっきりしています。 連結リストには番号がありません。 list.get(50000) は、先頭から5万回 next をたどっています。 「5万番目の場所」を計算で出す方法が無いからです。
教科書どおりにならないところ
ここで、素直に測ると教科書と違う結果が出るものを、隠さずに出します。
「全部たどって合計する」を比べます。 どちらも O(n) です。理屈の上では同じ速さのはずです。
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());
配列 全部たどって合計 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','鈴木'] ]
↑ ここだけ順に照合する
// 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 の中身は説明が付きます。 動かします。
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'));
田中
undefined
user-1 のバケツ番号: 337
user-2 のバケツ番号: 336
h.get('user-1') は、1024個あるバケツのうち337番だけを見ています。 他の1023個は触ってもいません。 これが「一発で引ける」の中身です。
* 31に意味はあるのか、と思ったはずです。 あります。 31は奇数の素数で、桁が散らばりやすいことが経験的に知られています。Java の文字列ハッシュがこれを使っていることで有名になりました。 ただし「これでなければならない」わけではありません。 大事なのはバケツに均等にばらけることだけです。次の実験で、ばらけないとどうなるかを見ます。
衝突を実際に起こす — バケツを4つに減らす
バケツを1024個から4個に減らします。 2万件のキーを入れれば、1つのバケツに平均5000件が詰まります。
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;
});
--- バケツ 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回程度で着きます。
挿入と探索を書く
// 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 がほとんど同じ形をしていることに注目してください。探して、見つからなかった場所に置く、それが挿入です。
中間順巡回で、並んだ順に出る
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());
入れた順: 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) です。木にした意味が消えます。
測ります。
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;
});
ばらばら順 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 の中のテキストファイルだけです。
入れたパッケージはありません。 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 — Computer Science
- roadmap.sh — Backend
- MDN — Array
- MDN — Array.prototype.unshift
- MDN — Map
- MDN — Set
- V8 — Elements kinds in V8
- Node.js — process.hrtime.bigint
- Wikipedia — 二分探索木
- Wikipedia — AVL木
- Wikipedia — 赤黒木
- Wikipedia — B木
- PostgreSQL — Index Types
- SQLite — Database File Format
- Redis — Data types
この段階の確認
【番外編】roadmap.sh の外 は、ここで終わりです。 次に進む前に、答えを見ずに試してください。
読み終えた直後は、たいてい「分かった気」になっています。 手が動くかどうかは別です。
説明できますか
- ここは飛ばしてよいと書いてあるのに、なぜ用意されているのか
- Windows Server は、Linuxと何が決定的に違うのか
- 自作してみることの価値は、どこにありますか
手が動きますか
- 触った範囲で、実務で出会ったときに困らない程度の地図を自分で描く
- 興味の無い項目は、堂々と飛ばす(ここは順路ではありません)
1つでも詰まったら、飛ばした回があります。 そこへ戻ってください。戻るのは後退ではありません。 戻り先の目安: 番外編の各回(順路ではないので、必要になったときだけ戻れば十分です)
全部答えられたなら、次の段階へ進んでください。
次に読む
この記事は 【番外編】roadmap.sh の外 の 35 / 35 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 1万件で100倍になる — 計算量とO記法を測る |
| → 次の記事 | ファイル操作 rm・cp・mv・ln — 消したものは戻らない |
ここは番外編です。 本筋から外れているので、飛ばして構いません。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
【番外編】データ構造。roadmap.sh の Computer Science 側の話で、本筋の範囲外。

コメント