B-Treeページストア

実装: db/btreestore/ / 実行: go test ./db/btreestore/

B-Tree とページとバッファプールを1つに繋ぐ回になる。メモリの中だけにあった B-Tree を、各ノードを1ページに直列化してディスクに置き、読み書きをバッファプール経由にする。こうすると木は永続化され、しかも根に近いノードは何度も通るので勝手にキャッシュに残る。これが本物のデータベースのインデックスの姿で、1万件を入れても検索で読むページは木の高さぶんに収まる。

この章で作るもの

B-Tree はメモリ上の *node ポインタで枝を繋いだ木だった。それを バッファプールの上に載せて、閉じても消えない・大きくてもメモリに 乗り切る木にする。

先に押さえることが3つある。

• ノードは *node ポインタではなく1ページになる。枝は「ページID」で参照する
• 読み書きは全てバッファプールを通る。だから根に近いノードは 勝手にキャッシュに残り、実質メモリ木のように速い
• 挿入アルゴリズムはメモリ版とまったく同じ。変わるのは 「ポインタを辿る」が「ページを読む」に、「代入」が「書き戻す」に、それだけ

前提章

B-Tree(木の構造と proactive split)、バッファプール (ページの読み書きの窓口)、ディスクとページ(ページと局所性)の上に立つ。

ポインタをページIDに置き換える

メモリ版のノードは子を *node で指していた。ディスクにはポインタを保存できない (プロセスが変われば意味を失う)ので、代わりにページIDで指す。ノード1つを1ページに このレイアウトで直列化する:

leaf1B

numKeys2B

keys8B×N

vals8B×N

children8B×(N+1)

1ノード = 1ページのレイアウト。子への参照はポインタではなくページID(8バイトの整数)。これならディスクに保存でき、再起動しても意味が変わらない

// node はメモリ上での作業用のノード表現。ディスクにはページとして直列化される。
// leaf でなければ children が len(keys)+1 個ある(B-Tree の不変条件)。
type node struct {
	leaf     bool
	keys     []uint64
	vals     []uint64
	children []uint64 // 子ノードのページID
}

// ページレイアウト: [leaf 1B][numKeys 2B][keys...][vals...][children...(内部ノードのみ)]
func serialize(n *node) []byte {
	buf := make([]byte, bufferpool.PageSize)
	if n.leaf {
		buf[0] = 1
	}
	binary.BigEndian.PutUint16(buf[1:3], uint16(len(n.keys)))
	off := 3
	for _, k := range n.keys {
		binary.BigEndian.PutUint64(buf[off:], k)
		off += 8
	}
	for _, v := range n.vals {
		binary.BigEndian.PutUint64(buf[off:], v)
		off += 8
	}
	if !n.leaf {
		for _, c := range n.children {
			binary.BigEndian.PutUint64(buf[off:], c)
			off += 8
		}
	}
	return buf
}

func deserialize(buf []byte) *node {
	n := &node{leaf: buf[0] == 1}
	num := int(binary.BigEndian.Uint16(buf[1:3]))
	off := 3
	n.keys = make([]uint64, num)
	for i := range n.keys {
		n.keys[i] = binary.BigEndian.Uint64(buf[off:])
		off += 8
	}
	n.vals = make([]uint64, num)
	for i := range n.vals {
		n.vals[i] = binary.BigEndian.Uint64(buf[off:])
		off += 8
	}
	if !n.leaf {
		n.children = make([]uint64, num+1)
		for i := range n.children {
			n.children[i] = binary.BigEndian.Uint64(buf[off:])
			off += 8
		}
	}
	return n
}

木の操作は「読んで、いじって、書き戻す」

メモリ版で n.left とポインタを辿っていたところが、readNode(id) でページを読む操作に 変わる。ノードを変更したら writeNode(id, n) で書き戻す。この2つを挟むだけで、 アルゴリズム本体はメモリ版と同一になる。

検索がそれを一番はっきり示す:

// Get は key の値を返す。根から降りて、各ノードで二分探索するだけ。
// たどったノードの数がページ読みの回数で、根に近いページはキャッシュに載っている。
func (tr *Tree) Get(key uint64) (uint64, bool, error) {
	id := tr.rootID
	for {
		n, err := tr.readNode(id)
		if err != nil {
			return 0, false, err
		}
		pos := sort.Search(len(n.keys), func(i int) bool { return n.keys[i] >= key })
		if pos < len(n.keys) && n.keys[pos] == key {
			return n.vals[pos], true, nil
		}
		if n.leaf {
			return 0, false, nil
		}
		id = n.children[pos]
	}
}

readNode の回数 = たどったノードの数 = ページ読みの回数。 ディスクとページで見た「速さはページ読み回数で数える」が、 ここでコードの readNode 呼び出し回数として目に見える形になる。

挿入も同じ。メモリ版の proactive split をそのまま、ポインタ参照をページID参照に 置き換えただけ:

// Insert は key=value を挿入(既存キーなら値を更新)する。
// アルゴリズムはメモリ版 btree と同じ proactive split。違いはポインタでなく
// ページIDを辿り、変更したノードを writeNode で書き戻すこと。
func (tr *Tree) Insert(key, value uint64) error {
	root, err := tr.readNode(tr.rootID)
	if err != nil {
		return err
	}
	if len(root.keys) == 2*tr.t-1 {
		newRootID := tr.allocate()
		newRoot := &node{leaf: false, children: []uint64{tr.rootID}}
		if err := tr.writeNode(newRootID, newRoot); err != nil {
			return err
		}
		tr.rootID = newRootID
		if err := tr.splitChild(newRootID, 0); err != nil {
			return err
		}
	}
	return tr.insertNonFull(tr.rootID, key, value)
}

func (tr *Tree) insertNonFull(id, key, value uint64) error {
	n, err := tr.readNode(id)
	if err != nil {
		return err
	}
	pos := sort.Search(len(n.keys), func(i int) bool { return n.keys[i] >= key })
	if pos < len(n.keys) && n.keys[pos] == key {
		n.vals[pos] = value // 更新
		return tr.writeNode(id, n)
	}
	if n.leaf {
		n.keys = insertUint64(n.keys, pos, key)
		n.vals = insertUint64(n.vals, pos, value)
		return tr.writeNode(id, n)
	}

	child, err := tr.readNode(n.children[pos])
	if err != nil {
		return err
	}
	if len(child.keys) == 2*tr.t-1 {
		if err := tr.splitChild(id, pos); err != nil {
			return err
		}
		// 分割で親が変わったので読み直す。
		n, err = tr.readNode(id)
		if err != nil {
			return err
		}
		if key > n.keys[pos] {
			pos++
		} else if key == n.keys[pos] {
			n.vals[pos] = value
			return tr.writeNode(id, n)
		}
	}
	return tr.insertNonFull(n.children[pos], key, value)
}

// splitChild は parent.children[i] (満杯)を2つに割り、真ん中を parent へ昇格させる。
func (tr *Tree) splitChild(parentID uint64, i int) error {
	parent, err := tr.readNode(parentID)
	if err != nil {
		return err
	}
	childID := parent.children[i]
	child, err := tr.readNode(childID)
	if err != nil {
		return err
	}
	t := tr.t

	rightID := tr.allocate()
	right := &node{leaf: child.leaf}
	right.keys = append(right.keys, child.keys[t:]...)
	right.vals = append(right.vals, child.vals[t:]...)
	if !child.leaf {
		right.children = append(right.children, child.children[t:]...)
		child.children = child.children[:t]
	}
	midKey, midVal := child.keys[t-1], child.vals[t-1]
	child.keys = child.keys[:t-1]
	child.vals = child.vals[:t-1]

	parent.keys = insertUint64(parent.keys, i, midKey)
	parent.vals = insertUint64(parent.vals, i, midVal)
	parent.children = insertUint64(parent.children, i+1, rightID)

	if err := tr.writeNode(childID, child); err != nil {
		return err
	}
	if err := tr.writeNode(rightID, right); err != nil {
		return err
	}
	return tr.writeNode(parentID, parent)
}

// insertUint64 は s の位置 i に x を差し込んだ新しいスライスを返す。
func insertUint64(s []uint64, i int, x uint64) []uint64 {
	s = append(s, 0)
	copy(s[i+1:], s[i:])
	s[i] = x
	return s
}

コードの読みどころ: 分割後に親を読み直す

insertNonFull の中で、満杯の子を splitChild した後に n, err = tr.readNode(id) と親をもう一度読んでいる。メモリ版なら分割は同じ *node を直接書き換えるので読み直しは不要だった。ページ版では splitChild が 親ページを writeNode で書き戻しているので、手元の n は古い。 「ページに書き戻したら、手元のメモリコピーは古くなる」。これがポインタの世界から ページの世界に移ると必ず出てくる注意点。

根の情報はどこに置くのか

木のどこが根か(rootID)、次に使えるページはどこか(nextID)を、 どこかに永続化しないと再起動したとき木を見つけられない。定石は ページ0を「メタページ」として予約し、そこに置くこと。

// Tree は uint64 キー → uint64 値の永続 B-Tree。
type Tree struct {
	pool   *bufferpool.Pool
	t      int // 最小次数。ノードのキー数は最大 2t-1
	rootID uint64
	nextID uint64 // 次に割り当てるページID
}

// Open はファイルを開き、既存の木を復元するか、空の木を初期化して返す。
func Open(path string, degree int) (*Tree, error) {
	if degree < 2 {
		return nil, errors.New("btreestore: degree must be >= 2")
	}
	// 2t-1 キー + 値 + 子が1ページに収まることを確かめる。
	maxKeys := 2*degree - 1
	if 3+maxKeys*8*2+(maxKeys+1)*8 > bufferpool.PageSize {
		return nil, fmt.Errorf("btreestore: degree %d too large for page size %d", degree, bufferpool.PageSize)
	}
	pool, err := bufferpool.New(path, 128)
	if err != nil {
		return nil, fmt.Errorf("btreestore: %w", err)
	}
	tr := &Tree{pool: pool, t: degree}

	meta, err := pool.Read(metaPage)
	if err != nil {
		pool.Close()
		return nil, err
	}
	tr.rootID = binary.BigEndian.Uint64(meta[0:8])
	tr.nextID = binary.BigEndian.Uint64(meta[8:16])

	if tr.nextID == 0 {
		// 新規ファイル。空の葉を root にする。
		tr.rootID = 1
		tr.nextID = 2
		if err := tr.writeNode(tr.rootID, &node{leaf: true}); err != nil {
			pool.Close()
			return nil, err
		}
		if err := tr.writeMeta(); err != nil {
			pool.Close()
			return nil, err
		}
	}
	return tr, nil
}

// Close は木を閉じる(dirty ページの書き戻しを含む)。
func (tr *Tree) Close() error {
	if err := tr.writeMeta(); err != nil {
		tr.pool.Close()
		return err
	}
	return tr.pool.Close()
}

func (tr *Tree) writeMeta() error {
	buf := make([]byte, bufferpool.PageSize)
	binary.BigEndian.PutUint64(buf[0:8], tr.rootID)
	binary.BigEndian.PutUint64(buf[8:16], tr.nextID)
	return tr.pool.Write(metaPage, buf)
}

func (tr *Tree) allocate() uint64 {
	id := tr.nextID
	tr.nextID++
	return id
}

func (tr *Tree) readNode(id uint64) (*node, error) {
	buf, err := tr.pool.Read(int(id))
	if err != nil {
		return nil, err
	}
	return deserialize(buf), nil
}

func (tr *Tree) writeNode(id uint64, n *node) error {
	return tr.pool.Write(int(id), serialize(n))
}

Open は起動時にページ0を読み、nextID == 0 なら「まだ何もない新規ファイル」と判断して 空の葉を根に初期化する。既存ファイルならメタページの rootID から木を再構築できる。 といっても、木のノードはもうディスク上のページとして全部そこにあるので、 「再構築」は rootID を思い出すだけで済む。これが永続データ構造の気持ちよさ。

試す: 検索は何ページ読むか

1〜20 を入れた木で、キーを検索するとたどったページ(=読んだページ)が光る。 検索キーを変えて、根から葉までのページ読み回数を見てほしい。

デモB-Tree の検索とページ読み

検索キー: 10

8

4

2

1

3

6

5

7

12

10

9

11

141618

13

15

17

1920

木が浅い(B-Treeの枝分かれの太さのおかげ)ので、20件でもページ読みは 2〜3回で収まる。そして同じ検索を繰り返せば、これらのページは バッファプールに残っているので、2回目からはディスクに触らない。 根のページに至っては、どんな検索でも必ず通るので、事実上ずっとキャッシュに居座る。

ここまでの db 編が1つになった

この章で、バラバラだった部品が組み上がった。

• B-Tree の構造と分割アルゴリズム
• ディスクとページ の「ページ単位・ページ読み回数」
• バッファプール の「読み書きの唯一の窓口・キャッシュ・遅延書き込み」
• LRU の追い出し(バッファプールの中身)

これで「永続化された、インデックス付きの、キャッシュの効くストレージ」になった。 足りないのは1つだけ、クラッシュ耐性だ。今はページの書き戻しが Close 頼みで、 途中で電源が落ちれば木が壊れうる。それを WAL と繋ぐのが db 編の最終回。

設計の観点

• ポインタを番号に置き換える: メモリのアドレスはプロセスが終われば無効になる。ページ番号にしておけば、そのままファイルへ書ける。永続化とは、突き詰めればアドレスを番号にすることになる
• 読んで、いじって、書き戻す: ページを触る操作をこの1つの型にはめておくと、どこでディスクを触ったかを数えられる。数えられれば、効いているかどうかを主張でなく測定にできる
• 根の位置だけは木の外に要る: どこから木が始まるかは、木の中には書けない。固定の場所が1つだけ要る
• 形をハードウェアが決める: 次数はアルゴリズムの都合ではなく、1ページに何個入るかで決まる。データ構造の形が、ディスクの単位から逆算されている
• キャッシュは上の段ほど効く: 根はどの検索でも必ず通るので、ほぼ常駐する。読むページ数を見積もるとき、上の段は数に入れなくてよくなる
• 保証していない線を言う: この章は Close するまで確実に届いた保証がない。何が保証されていないかを言えることが、次に何を作るかを決める

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

論点	この章	実物
ノードの参照	ページID(ファイルにそのまま書ける)	同じ。ページ番号でたどる
次数	256バイトページで4	4KB ページで数百。木が低くなる
値の置き場	内部ノードにも置く(B-Tree)	リーフだけに置く(B+Tree)。内部をさらに太くできる
根の位置	メタページ	SQLite はファイル先頭のヘッダ、bbolt はメタページ2枚
永続化の線	Close するまで保証なし	WAL で commit ごとに引く

実例:

• SQLite: ファイル全体がページの列で、その中に B-Tree ノードが載る。この章とほぼ同じ構造で、既定のページサイズは 4096 バイト
• InnoDB / PostgreSQL: 索引は B+Tree。値をリーフに集め、内部ノードの扇出しを上げている
• bbolt: Go 製の組み込み KV で、ファイルを mmap したページ上の B+Tree。読みのキャッシュを OS に任せている

裏どり:

• メタページは2枚持つ: bbolt はメタページを交互に書き、新しいほうが壊れていれば古いほうを使う。1枚しかないと、そこを書き換えている最中のクラッシュで木ごと迷子になる。根の位置は木で一番失えない情報になる
• 扇出しが直接効く: 読むページ数は木の高さで決まり、高さは1ページに入るキー数の対数で決まる。B+Tree が内部ノードから値を追い出すのは、この数を増やして高さを下げるためになる
• ページサイズは OS とディスクに合わせる: 4KB が多いのは、OS のページと多くのディスクの単位がそこだから。半端な大きさにすると1回の読みが2ブロックにまたがり、得が消える
• mmap という選択: bbolt はバッファプールを自前で持たず、ページの読みを OS のページフォールトに任せている。実装は小さくなるが、いつ書き戻されるかの制御を手放すことになる
• 削除が入ると難しくなる: この章は削除を持たないが、実物はページが空きすぎたときの併合や借用が要る。分割より削除のほうが実装が重いのは、この後始末があるため

簡略化したこと

• 削除は未実装: メモリ版に揃えた。ページの併合・借用が入る
• キーも値も uint64 固定: 実物は可変長・複合キー。ページ内はスロット配列になる
• B+Tree ではない: 実物は値をリーフだけに置き、内部ノードをさらに太くする。 リーフを横に繋いで範囲検索も速くする
• WAL 未統合・フリーリストなし: 次章とその先で

参考資料

• SQLite Database File Format — ページ上の B-Tree の実物
• bbolt — Go で読めるページ上 B+Tree の実装
• Alex Petrov『Database Internals』2〜4章 — ノードのページレイアウトを最も詳しく扱う