sharin

Appearance

B-Tree ​

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

ほとんどのデータベースのインデックスの中身、B-Tree を作る。二分探索木を「ディスク向けに太らせた」木で、1つのノードに数百のキーを詰めて枝分かれを増やすと、数十億件あってもページを数回読むだけで目当てに届く。挿入のたびに触るノードを見ると、昇順に入れるときは常に右端の経路だけ、ランダムだと毎回別の場所になる。この散らばりの差が、実物の挿入速度に出る。

この章で作るもの ​

ほぼすべての 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 主キーの世界。全ページが中途半端に埋まり、 どのページもキャッシュから追い出されうる
デモB-Tree の挿入高さ 0

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

空

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

実物との距離: B+Tree ​

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

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

設計の観点 ​

  • 枝分かれの数を、比較の回数でなく読みの回数から決める: 二分木はメモリ上の比較回数を最小にするが、ディスクでは1回の読みの単位が大きい。1回で読める分だけ詰め込むと決めた時点で、次数も木の高さも決まる
  • 上に伸ばすことで、平衡を保証にする: 高さが変わるのは根が満杯のときだけ。葉から伸ばさないと決めたので、すべての葉が同じ深さであることが後付けの調整でなく構造から出てくる
  • 満杯を先に割る: 降りながら満杯のノードを割っておくと、挿入が1回の下降で終わる。戻りながら直す実装より状態が単純になる
  • 触る場所の散らばりが性能になる: 同じ計算量でも、毎回同じ経路を触るか散らばるかで速さが変わる。この章の実験がそれを見える形にしている
  • 削除を後回しにできる: 挿入だけなら分割で閉じるが、削除は借用と併合が要る。どこまで作れば主張が立つかを決めて、そこで切っている
  • 形はハードウェアに従う: 次数はアルゴリズムの美しさでなく、ページサイズから逆算される。データ構造の設計が、置き場所の性質に従属している

メリット・デメリットと実例 ​

索引の形得意苦手実例
B-Tree / B+Tree範囲検索、整列済みの取り出し、1件引き書き込みが集中する場面PostgreSQL の nbtree、InnoDB、SQLite
ハッシュ等値の1件引きが定数回範囲・整列がまったくできないハッシュマップ、PostgreSQL の hash 索引
スキップリスト実装が単純で、範囲もいけるポインタが多くメモリを食うRedis の sorted set、LevelDB の memtable
LSM ツリー書き込みが洪水のように来る場面読みが複数の階層をまたぐRocksDB、ログ構造KVの発展形

実例:

  • PostgreSQL の nbtree: 索引の既定。値は葉に置き、葉を横に繋いで範囲検索を歩けるようにしている
  • InnoDB: テーブル本体そのものが主キーの B+Tree になっている(クラスタ化)。だから主キーの選び方が、そのまま挿入の散らばりに直結する
  • ファイルシステム: NTFS も Btrfs も木を使う。ディスクの単位で読む以上、同じ制約に行き着く

裏どり:

  • B+Tree との差は2点: 値を葉だけに置くことと、葉を横に連結すること。前者は内部ノードの扇出しを上げて木を低くし、後者は BETWEEN を「降りてから右に歩く」に変える。この章の実装は内部ノードにも値を置くので、どちらの得も取っていない
  • 昇順挿入が効く理由: 触るのが常に右端の経路になるので、そのページがキャッシュに乗り続け、ページも順に満杯まで埋まる。UUIDv7 や Snowflake が主キーに選ばれる理由がここにある(ID生成で測っている)
  • ランダム挿入の代償: 触る場所が散ると、どのページも中途半端に埋まったままキャッシュから追い出されうる。同じ件数でも使うページ数が増え、書き込みも散らばる
  • 削除が実装を重くする: ノードが空きすぎたときの借用・併合は、分割より場合分けが多い。実物には、削除しても即座には詰めない設計もある
  • 並行制御は別の層: 実物は複数のトランザクションが同時に木を触るため、ノード単位の短いロック(ラッチ)を降りながら受け渡す。木の正しさと、同時に触られる正しさは別々に要る

簡略化したこと ​

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

参考資料 ​