sharin

Appearance

B-Tree ​

実装: data-structures/btree/ / 実行: go test ./data-structures/btree/

この章で作るもの ​

ほぼすべての RDB のインデックスの正体である B-Tree を、挿入と検索に絞って実装する。 ID Generation の章で予告した 「なぜ UUIDv7 はインデックスに優しいのか」をデモで実際に見るのがゴール。

前提章

この章は2つの前提章の上に立っている。 二分探索木(半分ずつ捨てる速さと、崩壊の問題)と、 ディスクとページ(ページ読み回数という速さの物差し)を先に読んでほしい。

この章の肝は3つ。

  • B-Tree の存在理由はディスク。速さの単位は比較の回数ではなくページ読みの回数
  • だから1ノード = 1ページにキーを大量に詰めて枝分かれを太くし、木を浅くする
  • 挿入は「降りながら、満杯のノードを先に割っておく」(proactive split)だけで書ける

なぜ二分探索木のままではダメなのか ​

二分探索木は、平衡さえ保てば比較 log2(n) 回で探せた。 メモリの中ならこれで話は終わり。しかしインデックスはディスクに置かれる。 ディスクとページで見たとおり、ディスクはページ単位でしか読めず、 1回のページ読みはメモリアクセスの数千〜10万倍重い。だから 速さはページ読みの回数で数える。

二分木のノードは小さい(キー1個とポインタ2本)ので、1億件も入れるとノードは バラバラのページに散らばる。高さ約27の木をたどる = 最悪27回のページ読み。

二分探索木約27回
B-Tree(分岐300)4回
1億件から1件探すときのページ読み回数。比較回数はほぼ同じでも、ディスクに触る回数が違う

ここで発想を変える。ページはどうせ8KBまるごと読まれるのだから、 1ページに収まるだけキーを詰めてしまえばいい。8KB にはキーとポインタが 数百組入る。枝分かれが300なら:

高さ0:                1 ノード ×  300 キー
高さ1:              300 ノード → 9万件
高さ2:            9万 ノード   → 2,700万件
高さ3:                          → 81億件

81億件でもページ読み4回。比較回数は二分木と大差ない(ノード内でも二分探索する)が、 ページ読み回数が27回から4回になる。これが B-Tree のすべてで、 「浅さを枝分かれの太さで買う」木と言える。

ノード構造 ​

go
// node は1ノード = 1ページに相当する。
// 最小次数 t のとき、キー数は最大 2t-1、root 以外は最小 t-1 に保たれる。
type node struct {
	keys     []int
	children []*node // 内部ノードでは常に len(keys)+1 個
	leaf     bool
}

// Tree は最小次数 t の B-Tree。
type Tree struct {
	root *node
	t    int
}

// New は最小次数 t (>= 2) の空の木を返す。t=2 なら1ノード最大3キーの 2-3-4 木。
func New(t int) (*Tree, error) {
	if t < 2 {
		return nil, errors.New("btree: minimum degree must be >= 2")
	}
	return &Tree{root: &node{leaf: true}, t: t}, nil
}

最小次数 t がノードの太さを決める(キー数は最大 2t-1、root 以外は最小 t-1)。 「最小」があるのが重要で、どのノードも半分以上詰まっていることが保証されるから、 木がスカスカに伸びることがない。テストではこの不変条件 (キー数の上下限、全部の葉が同じ深さ、ノード内昇順)を全ノードで検証している。

検索 ​

go
// Contains は key が存在するかを返す。
// 各ノードでキー列を二分探索し、見つからなければ「key が挟まる位置」の子へ降りる。
// 訪れるノード数 = 木の高さ+1 で、これがディスクなら「ページ読み回数」になる。
func (tr *Tree) Contains(key int) bool {
	n := tr.root
	for {
		pos := sort.SearchInts(n.keys, key)
		if pos < len(n.keys) && n.keys[pos] == key {
			return true
		}
		if n.leaf {
			return false
		}
		n = n.children[pos]
	}
}

各ノードでキー列を二分探索し、外れたら「挟まる位置」の子へ降りるだけ。 ループ回数 = 高さ+1 = ページ読み回数。

挿入と分割 ​

満杯のノード(2t-1 キー)に挿入はできないので、どこかで分割が要る。 素朴にやると「葉に入れる → 溢れたら割って親に昇格 → 親も溢れたら…」と 上に波及して戻る処理になるが、CLRS 流はこれを逆転させる: 降りる途中で、満杯の子を先に割っておく。こうすると親は必ず空きがある状態で 昇格を受け取れるので、処理が一方通行になる。

go
// Insert は key を挿入する(既存なら何もしない)。
// 降りる途中で「満杯のノードを先に割っておく」のが CLRS 流の proactive split。
// こうすると分割が親に波及して戻る処理が要らず、一方通行で書ける。
func (tr *Tree) Insert(key int) {
	if len(tr.root.keys) == 2*tr.t-1 {
		// root が満杯なら新しい root を作って割る。木が高くなるのはこの瞬間だけ。
		newRoot := &node{children: []*node{tr.root}}
		tr.root = newRoot
		tr.splitChild(newRoot, 0)
	}
	tr.insertNonFull(tr.root, key)
}

func (tr *Tree) insertNonFull(n *node, key int) {
	pos := sort.SearchInts(n.keys, key)
	if pos < len(n.keys) && n.keys[pos] == key {
		return // 重複は無視
	}
	if n.leaf {
		n.keys = append(n.keys, 0)
		copy(n.keys[pos+1:], n.keys[pos:])
		n.keys[pos] = key
		return
	}
	if len(n.children[pos].keys) == 2*tr.t-1 {
		tr.splitChild(n, pos)
		// 分割で昇格したキーと比較して、降りる先を選び直す。
		if key > n.keys[pos] {
			pos++
		} else if key == n.keys[pos] {
			return
		}
	}
	tr.insertNonFull(n.children[pos], key)
}

分割はこう動く。真ん中のキーが親に昇格し、残りが左右に分かれる。 t=2(1ノード最大3キー)の木に 10, 20, 30 まで入れて、4件目を入れようとした瞬間:

102030
分割
20
10
30
左: 満杯のノード(これ以上入らない)。右: 分割後 — 真ん中の20が昇格して新しい root になり、木が1段高くなる

コードではこうなる:

go
// splitChild は parent.children[i] (満杯: 2t-1 キー)を2つに割り、
// 真ん中のキーを parent に昇格させる。
//
//	割る前:  parent [.. keys ..]
//	         child  [a b c M d e f]   (t=4 の例。M が真ん中)
//	割った後: parent [.. M ..]
//	         left   [a b c]  right [d e f]
func (tr *Tree) splitChild(parent *node, i int) {
	t := tr.t
	child := parent.children[i]
	mid := child.keys[t-1]

	right := &node{leaf: child.leaf}
	right.keys = append(right.keys, child.keys[t:]...)
	if !child.leaf {
		right.children = append(right.children, child.children[t:]...)
		child.children = child.children[:t]
	}
	child.keys = child.keys[:t-1]

	// parent の位置 i に mid を、i+1 に right を差し込む。
	parent.keys = append(parent.keys, 0)
	copy(parent.keys[i+1:], parent.keys[i:])
	parent.keys[i] = mid
	parent.children = append(parent.children, nil)
	copy(parent.children[i+2:], parent.children[i+1:])
	parent.children[i+1] = right
}

コードの読みどころ: 木が高くなる瞬間は1箇所だけ ​

Insert の冒頭だけが木の高さを変える。root が満杯のとき、新しい root を作って 旧 root を割る——B-Tree は上に向かって伸びる。葉から伸びる二分木と逆で、 これがあるから「すべての葉が同じ深さ」が常に保たれる。

実験: 昇順挿入とランダム挿入で「触るノード」を見る ​

t=2(1ノード最大3キー)の小さな木で、挿入のたびに触ったノードが光る。

試してみる:

  • 「昇順で1件挿入」を連打すると、光るのは常に右端の経路だけ。 これが UUIDv7 / Snowflake 主キーの世界。触るページが固定されるから キャッシュに乗り続け、ページは順に満杯になっていく
  • リセットして「ランダムに1件挿入」を連打すると、光る場所が毎回バラバラになる。 これが UUIDv4 主キーの世界。全ページが中途半端に埋まり、 どのページもキャッシュから追い出されうる

キー 0 / 高さ 0 / 分割 0回 / 直前の挿入で触ったノード 0 個(枠が光る)

空

実物の DB では、この「触るページの散らばり」が挿入スループットの差になって現れる。 ID Generation の「なぜソート可能が効くのか」の実体がこれ。

実物との距離: B+Tree ​

実物の RDB が使うのは正確には B+Tree という変種で、この章の実装と2点違う。

  • 値(行データやそのポインタ)を葉だけに置く。内部ノードはキーだけになり、 さらに大量のキーを詰めて枝分かれを太くできる
  • 葉同士を横に連結する。WHERE id BETWEEN a AND b のような範囲検索が 「a まで降りて、あとは葉を右に歩くだけ」になる

実例

  • PostgreSQL のインデックス(nbtree)、MySQL InnoDB(テーブル本体が主キーの B+Tree)
  • SQLite(テーブルもインデックスも B-Tree ファミリ)
  • ファイルシステム(NTFS、Btrfs はその名の通り)

なお「等価検索しかしない」ならハッシュインデックスが O(1) で勝ち、 「書き込みが洪水のように来る」なら LSM-Tree(RocksDB 等)という別解がある。 このあたりの使い分けは db 編で扱う。

簡略化したこと ​

  • 削除は未実装: 隣接ノードからの借用・併合が入り、挿入より一段複雑になる
  • メモリ内のみ: 実物は1ノード = 1ページをディスクに置き、バッファプールで キャッシュする。「ページ読み回数」はこの章では概念で、db 編で実物になる
  • B+Tree ではない: 上記の通り
  • 並行制御なし: 実物は複数トランザクションが同時に触るためのラッチ制御がある

参考資料 ​