RDBMSを自作して学ぶ：第6章 B+木インデックス
前回は、テーブルのレコードをスロット付きページに格納するヒープファイルを実装しました。ヒープファイルはレコードを空いている場所に積み上げていくだけなので、特定のレコードを探すには全ページを読むしかありません。今回は、キーから目的のレコードの位置（RID）を素早く引くためのB+木（B+ Tree）インデックスを実装します。
なぜインデックスが必要か ── フルスキャンの限界
フルスキャンのコスト
インデックスのないテーブルで WHERE id = 100 を実行すると、データベースはヒープファイルの全ページを先頭から読み、すべてのレコードの id を確かめるしかありません。これをフルスキャンと呼びます。
ページ 0 → ページ 1 → ページ 2 → ... → ページ N
（すべてのスロットを確認）レコード数を N とすると、1件を探すだけでも O(N) の時間がかかります。100万件のテーブルなら、目的の1件を探すために100万件を調べることになります。
インデックスによる改善
B+木は、キーの大小関係に従ってエントリを並べた、背の低い木構造です。1つのノードを1ページ（4KB）にして、1ノードに数百個のキーを詰め込みます。本章の実装では、葉ノードに最大290件、内部ノードに最大338個のキーが入ります。
1ノードから数百本の枝が出るので、木の高さは件数が増えてもほとんど伸びません。テストで確かめますが、10万件を挿入しても高さは3です。つまり、ルートから葉まで3ページたどるだけで、目的のキーのRIDが手に入ります。一般に B+木 の検索は O(log N) で、その対数の底が数百と非常に大きい、というのがポイントです。
B木とB+木の違い
B木（B-Tree）
B木は、内部ノードにも葉ノードにも、キーとデータ（本シリーズならRID）を格納します。
[30:RID]
/ \
[10:RID, 20:RID] [40:RID, 50:RID]B+木（B+ Tree）
B+木は、データを葉ノードだけに格納します。内部ノードが持つのは、どの子へ進むかを決めるためのキー（区切りキー）だけです。さらに、葉ノード同士をリンクでつなぎます。
[30] ← 内部ノード（区切りキーだけ）
/ \
[10,20,25] → [30,40,50] ← 葉ノード（キー + RID）。右隣へのリンクを持つ区切りキーの30は、葉ノードにも残っている点に注意してください。B+木では、すべてのキーが必ず葉に存在します。
データベースがB+木を選ぶ理由
| 観点 | B木 | B+木 |
|---|---|---|
| 1件の検索 | O(log N)。内部ノードで見つかれば途中で終わる | O(log N)。必ず葉までたどる |
| 範囲検索 | 木を行ったり来たりしながら順にたどる | 開始位置の葉を見つけたら、葉のリンクを順にたどるだけ |
| 内部ノードの分岐数 | データも持つぶん少ない | キーだけなので多い（木が低くなる） |
WHERE id BETWEEN 100 AND 200 のような範囲検索は、データベースでは非常によく使われます。B+木なら、100の位置の葉を見つけた後は、右隣の葉へリンクをたどるだけで順番に読めます。また内部ノードにデータを置かないぶん、1ページに多くのキーが入り、木が低くなります。こうした理由から、MySQL（InnoDB）もPostgreSQLも、標準のインデックスにB+木（またはその変種）を使っています。
なお、PostgreSQLのB+木は葉を左右両方向にリンクしていますが、本シリーズでは実装を簡単にするため、右方向のリンクだけを持たせます。
ノードの設計
ページレイアウト
1ノード = 1ページです。第5章のヒープページと同じく、共通ヘッダの直後の8バイトは第12章のページLSNのために空けておきます。
B+木ノード (4096バイト)
┌──────────────────────────────────────────────────────┐
│ [0:16] 共通ページヘッダ（ページ種別 = PageTypeBTree）│
│ [16:24] ページLSN（予約） │
│ [24] ノード種別（1 = 葉、0 = 内部） │
│ [26:28] キーの数 │
│ [28:32] 葉: 右隣の葉のPageID / 内部: 最も左の子 │
├──────────────────────────────────────────────────────┤
│ [32:] エントリの配列 │
│ 葉 : キー(8B) + RID.PageID(4B) + RID.SlotID(2B) │
│ 内部: キー(8B) + 右側の子のPageID(4B) │
└──────────────────────────────────────────────────────┘キーは int64 にします。本シリーズでは、主キー（PRIMARY KEY）に指定したINT型カラムのインデックスとしてB+木を使うので、整数キーだけ扱えれば十分です。また主キーなので、キーの重複は許しません。
内部ノードのキーと子の関係
キーが k 個ある内部ノードは、子を k+1 個持ちます。最も左の子はヘッダの [28:32] に、残りの子は各エントリの「右側の子」に入れます。
内部ノード: child0 | key0 | child1 | key1 | child2
│ │ │
▼ ▼ ▼
key0未満 key0以上key1未満 key1以上child(i) の部分木には「key(i-1) 以上 key(i) 未満」のキーが入ります。区切りキーと等しいキーは右側の子に入る、というのがこの実装の約束です。後で見るとおり、葉を分割したときに「右側の葉の最小キー」を区切りキーとして親に上げるので、この約束と一致します。
実装：node
ノードの読み書きは node 型にまとめます。エントリの位置は nodeHeaderSize + i × エントリサイズ で計算でき、挿入・削除は後ろのエントリをまとめて copy でずらします。
// storage/btree/node.go
package btree
import (
"encoding/binary"
"github.com/yourname/go-rdbms/storage/heap"
"github.com/yourname/go-rdbms/storage/page"
)
// ノードのレイアウト
//
// [0:16] 共通ページヘッダ（ページ種別 = PageTypeBTree）
// [16:24] ページLSN（第12章のために予約。第5章のヒープページと同じ位置）
// [24] ノード種別（1 = 葉、0 = 内部）
// [26:28] キーの数
// [28:32] 葉: 右隣の葉のPageID / 内部: 最も左の子のPageID
// [32:] エントリの配列
//
// 葉のエントリ : キー(8B) + RID.PageID(4B) + RID.SlotID(2B) = 14B
// 内部のエントリ : キー(8B) + 右側の子のPageID(4B) = 12B
const (
offsetIsLeaf = 24
offsetNumKeys = 26
offsetLink = 28
nodeHeaderSize = 32
leafEntrySize = 14
internalEntrySize = 12
maxLeafKeys = (page.PageSize - nodeHeaderSize) / leafEntrySize // 290
maxInternalKeys = (page.PageSize - nodeHeaderSize) / internalEntrySize // 338
)
// leafEntry は葉ノードの1エントリ
type leafEntry struct {
key int64
rid heap.RID
}
// node はページをB+木のノードとして読み書きするためのラッパー
type node struct {
p *page.Page
}
func (n node) initLeaf() {
n.p.SetPageType(page.PageTypeBTree)
n.p[offsetIsLeaf] = 1
n.setNumKeys(0)
n.setLink(page.InvalidPageID)
}
func (n node) initInternal(leftmostChild page.PageID) {
n.p.SetPageType(page.PageTypeBTree)
n.p[offsetIsLeaf] = 0
n.setNumKeys(0)
n.setLink(leftmostChild)
}
func (n node) isLeaf() bool { return n.p[offsetIsLeaf] == 1 }
func (n node) numKeys() int {
return int(binary.BigEndian.Uint16(n.p[offsetNumKeys:]))
}
func (n node) setNumKeys(k int) {
binary.BigEndian.PutUint16(n.p[offsetNumKeys:], uint16(k))
}
func (n node) link() page.PageID {
return page.PageID(binary.BigEndian.Uint32(n.p[offsetLink:]))
}
func (n node) setLink(id page.PageID) {
binary.BigEndian.PutUint32(n.p[offsetLink:], uint32(id))
}
func (n node) entrySize() int {
if n.isLeaf() {
return leafEntrySize
}
return internalEntrySize
}
func (n node) entryPos(i int) int {
return nodeHeaderSize + i*n.entrySize()
}
// key はi番目のキーを返す（葉・内部共通）
func (n node) key(i int) int64 {
return int64(binary.BigEndian.Uint64(n.p[n.entryPos(i):]))
}
// ---- 葉ノード ----
// next は右隣の葉のPageIDを返す
func (n node) next() page.PageID { return n.link() }
func (n node) setNext(id page.PageID) { n.setLink(id) }
func (n node) rid(i int) heap.RID {
pos := n.entryPos(i) + 8
return heap.RID{
PageID: page.PageID(binary.BigEndian.Uint32(n.p[pos:])),
SlotID: binary.BigEndian.Uint16(n.p[pos+4:]),
}
}
func (n node) setLeafEntry(i int, e leafEntry) {
pos := n.entryPos(i)
binary.BigEndian.PutUint64(n.p[pos:], uint64(e.key))
binary.BigEndian.PutUint32(n.p[pos+8:], uint32(e.rid.PageID))
binary.BigEndian.PutUint16(n.p[pos+12:], e.rid.SlotID)
}
func (n node) leafEntries() []leafEntry {
entries := make([]leafEntry, n.numKeys())
for i := range entries {
entries[i] = leafEntry{key: n.key(i), rid: n.rid(i)}
}
return entries
}
func (n node) setLeafEntries(entries []leafEntry) {
for i, e := range entries {
n.setLeafEntry(i, e)
}
n.setNumKeys(len(entries))
}
// insertLeafEntry はi番目にエントリを挿入する（i以降は1つ後ろへずらす）
func (n node) insertLeafEntry(i int, e leafEntry) {
k := n.numKeys()
copy(n.p[n.entryPos(i+1):n.entryPos(k+1)], n.p[n.entryPos(i):n.entryPos(k)])
n.setLeafEntry(i, e)
n.setNumKeys(k + 1)
}
// removeLeafEntry はi番目のエントリを取り除く（i+1以降を1つ前へ詰める）
func (n node) removeLeafEntry(i int) {
k := n.numKeys()
copy(n.p[n.entryPos(i):n.entryPos(k-1)], n.p[n.entryPos(i+1):n.entryPos(k)])
n.setNumKeys(k - 1)
}
// lowerBound はkey以上となる最初のエントリ位置を返す（二分探索）
func (n node) lowerBound(key int64) int {
lo, hi := 0, n.numKeys()
for lo < hi {
mid := (lo + hi) / 2
if n.key(mid) < key {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}
// ---- 内部ノード ----
// キーがk個ある内部ノードは、子をk+1個持つ。
// child(0) はヘッダのlink、child(i+1) はi番目のエントリに入っている。
func (n node) child(i int) page.PageID {
if i == 0 {
return n.link()
}
pos := n.entryPos(i-1) + 8
return page.PageID(binary.BigEndian.Uint32(n.p[pos:]))
}
// setInternalEntry はi番目のキーと、その右側の子（child(i+1)）を書き込む
func (n node) setInternalEntry(i int, key int64, rightChild page.PageID) {
pos := n.entryPos(i)
binary.BigEndian.PutUint64(n.p[pos:], uint64(key))
binary.BigEndian.PutUint32(n.p[pos+8:], uint32(rightChild))
}
// insertInternalEntry はi番目にキーと右側の子を挿入する
func (n node) insertInternalEntry(i int, key int64, rightChild page.PageID) {
k := n.numKeys()
copy(n.p[n.entryPos(i+1):n.entryPos(k+1)], n.p[n.entryPos(i):n.entryPos(k)])
n.setInternalEntry(i, key, rightChild)
n.setNumKeys(k + 1)
}
// internalContents はキーの一覧と子の一覧（キー数+1個）を返す
func (n node) internalContents() ([]int64, []page.PageID) {
k := n.numKeys()
keys := make([]int64, k)
children := make([]page.PageID, k+1)
children[0] = n.child(0)
for i := 0; i < k; i++ {
keys[i] = n.key(i)
children[i+1] = n.child(i + 1)
}
return keys, children
}
func (n node) setInternalContents(keys []int64, children []page.PageID) {
n.setLink(children[0])
for i, key := range keys {
n.setInternalEntry(i, key, children[i+1])
}
n.setNumKeys(len(keys))
}
// childIndex はkeyをたどるべき子の位置を返す
// 「key以下のキーの個数」が、そのまま子の位置になる
func (n node) childIndex(key int64) int {
lo, hi := 0, n.numKeys()
for lo < hi {
mid := (lo + hi) / 2
if n.key(mid) <= key {
lo = mid + 1
} else {
hi = mid
}
}
return lo
}子の位置を求める childIndex は「key 以下のキーの個数」を二分探索で数えます。たとえばキーが [10, 20] の内部ノードで、検索キーが
- 5 なら、10以下のキーは0個 →
child(0) - 10 なら、10以下のキーは1個 →
child(1)（区切りキーと等しいキーは右へ） - 25 なら、20以下のキーは2個 →
child(2)
となります。「key より小さいキーの個数」で数えてしまうと、区切りキーと等しいキーが左の子に進み、見つからなくなるので注意が必要です。
検索
ルートから始めて、内部ノードでは childIndex で子を選び、葉に着いたら二分探索でキーを探します。
// BPlusTree はキー（int64）からRIDを引くB+木インデックス
// キーの重複は許さない（主キー用のユニークインデックス）
type BPlusTree struct {
mu sync.RWMutex
bpm *buffer.BufferPoolManager
rootPageID page.PageID // ルートのPageIDは作成後に変わらない
}
// NewBPlusTree は空の葉ノード1つをルートとする新しいB+木を作る
func NewBPlusTree(bpm *buffer.BufferPoolManager) (*BPlusTree, error) {
rootID, p, err := bpm.NewPage()
if err != nil {
return nil, fmt.Errorf("btree: ルートページの割り当てに失敗しました: %w", err)
}
node{p}.initLeaf()
if err := bpm.UnpinPage(rootID, true); err != nil {
return nil, err
}
return &BPlusTree{bpm: bpm, rootPageID: rootID}, nil
}
// OpenBPlusTree はルートのPageIDから既存のB+木を開く
func OpenBPlusTree(bpm *buffer.BufferPoolManager, rootPageID page.PageID) *BPlusTree {
return &BPlusTree{bpm: bpm, rootPageID: rootPageID}
}
// RootPageID はルートノードのPageIDを返す
func (t *BPlusTree) RootPageID() page.PageID {
return t.rootPageID
}
// Search はkeyに対応するRIDを返す。見つからなければ found=false
func (t *BPlusTree) Search(key int64) (rid heap.RID, found bool, err error) {
t.mu.RLock()
defer t.mu.RUnlock()
leafID, err := t.findLeaf(key)
if err != nil {
return heap.RID{}, false, err
}
p, err := t.bpm.FetchPage(leafID)
if err != nil {
return heap.RID{}, false, err
}
defer t.bpm.UnpinPage(leafID, false)
n := node{p}
i := n.lowerBound(key)
if i < n.numKeys() && n.key(i) == key {
return n.rid(i), true, nil
}
return heap.RID{}, false, nil
}
// findLeaf はルートから内部ノードをたどり、keyが属する葉のPageIDを返す
func (t *BPlusTree) findLeaf(key int64) (page.PageID, error) {
id := t.rootPageID
for {
p, err := t.bpm.FetchPage(id)
if err != nil {
return page.InvalidPageID, err
}
n := node{p}
if n.isLeaf() {
return id, t.bpm.UnpinPage(id, false)
}
next := n.child(n.childIndex(key))
if err := t.bpm.UnpinPage(id, false); err != nil {
return page.InvalidPageID, err
}
id = next
}
}findLeaf は、次の子のPageIDを読んだらすぐに今のノードをアンピンしてから下へ進みます。木の高さぶんのページを同時にピンし続けないようにするためです。
mu は木全体を守る読み書きロックです。検索どうしは同時に実行でき、挿入・削除は他の操作と重ならないようにします。実際のデータベースでは、ノードごとに細かくロック（ラッチ）を取って並行性を上げますが、本シリーズでは単純さを優先しています。
範囲検索
範囲検索は、最小キーが属する葉を探し、そこから右隣の葉へリンクをたどりながら、最大キーを超えるまでRIDを集めます。
// RangeScan は minKey 以上 maxKey 以下のキーに対応するRIDをキー順に返す
func (t *BPlusTree) RangeScan(minKey, maxKey int64) ([]heap.RID, error) {
t.mu.RLock()
defer t.mu.RUnlock()
if minKey > maxKey {
return nil, nil
}
leafID, err := t.findLeaf(minKey)
if err != nil {
return nil, err
}
var result []heap.RID
for leafID != page.InvalidPageID {
p, err := t.bpm.FetchPage(leafID)
if err != nil {
return nil, err
}
n := node{p}
done := false
for i := n.lowerBound(minKey); i < n.numKeys(); i++ {
if n.key(i) > maxKey {
done = true
break
}
result = append(result, n.rid(i))
}
next := n.next()
if err := t.bpm.UnpinPage(leafID, false); err != nil {
return nil, err
}
if done {
break
}
leafID = next // 右隣の葉へ
}
return result, nil
}最初の葉の中では lowerBound(minKey) の位置から読み始めます。2つ目以降の葉のキーはすべて minKey 以上なので、lowerBound は0を返し、先頭から読むことになります。
挿入とノードの分割
葉の分割
葉に空きがあれば、ソート順を保つ位置にエントリを差し込むだけです。満杯の葉に挿入するときは、新しいエントリを加えた全エントリを半分に分け、後半を新しい葉に移します。図は、1ノードに最大4件入る場合の例です。
満杯の葉 [10, 20, 30, 40] に 25 を挿入する
① 新しいエントリを加えて並べる: [10, 20, 25, 30, 40]
② 半分に分ける: [10, 20] [25, 30, 40]
③ 右の葉の最小キー 25 を親に「コピー」する
[25]
/ \
[10, 20] → [25, 30, 40]葉のエントリは本物のデータ（RID）なので、区切りキー25は右の葉にも残ります。また、新しい右の葉が元の右隣を引き継ぎ（right.next = left.next）、元の葉は新しい右の葉を指す（left.next = right）ようにリンクをつなぎ直します。
内部ノードの分割
子の分割によって親に区切りキーが追加され、親の内部ノードも満杯になった場合は、内部ノードも分割します。
満杯の内部ノード [10, 20, 30, 40] に区切りキー 25 を追加する
① キーを加えて並べる: [10, 20, 25, 30, 40]
② 真ん中の 25 を親へ「移動」し、残りを左右に分ける
[25]
/ \
[10, 20] [30, 40]内部ノードのキーはあくまで道案内なので、真ん中のキーは左右どちらにも残さず、親へ移動します。葉の分割（コピー）との違いに注意してください。
ルートの分割
分割が親へ親へと伝わってルートまで達すると、ルートも分割しなければなりません。このときは、2つに分かれたノードの上に新しいルートを作り、木を1段高くします。B+木は葉の側ではなく、根の側に向かって成長するので、すべての葉の深さが常に等しく保たれます。
素直に実装すると、新しいルートは新しいページになり、ルートのPageIDが変わってしまいます。第9章では、テーブルごとにインデックスのルートのPageIDをカタログに保存するので、ルートが変わるたびにカタログも書き換えることになります。
そこで本シリーズでは、ルートのPageIDを変えない方法を取ります。ルートの中身を新しいページにコピーしてそれを左の子とし、ルート自身は2つの子を持つ内部ノードに作り直します。SQLiteも同じ方法で、ルートのページ番号を変えずに木を高くしています。
分割前: root(ページ1) = [10, 20] → [25, 30, 40](ページ7)
① ルートの中身を新しいページ8にコピーする
② ルート（ページ1）を内部ノードに作り直す
root(ページ1) = [25]
/ \
ページ8 = [10, 20] → ページ7 = [25, 30, 40]実装：挿入
挿入は再帰で書きます。insert は、あるノードを根とする部分木にエントリを挿入し、そのノードが分割された場合は「親に追加すべき区切りキーと、新しい右ノード」を splitResult として返します。呼び出し元（親）はそれを受け取って自分に追加し、自分も満杯なら分割して、さらに上へ伝えます。
// splitResult は子ノードが分割されたときに親へ伝える情報
type splitResult struct {
key int64 // 親に追加する区切りキー
right page.PageID // 分割で新しくできた右側のノード
}
// Insert はキーとRIDの組を挿入する
func (t *BPlusTree) Insert(key int64, rid heap.RID) error {
t.mu.Lock()
defer t.mu.Unlock()
split, err := t.insert(t.rootPageID, key, rid)
if err != nil || split == nil {
return err
}
// ルートが分割された場合は木を1段高くする
return t.growRoot(split)
}
// insert はpageIDをルートとする部分木にエントリを挿入する
// このノードが分割された場合は、親に追加すべき区切りキーを返す
func (t *BPlusTree) insert(pageID page.PageID, key int64, rid heap.RID) (*splitResult, error) {
p, err := t.bpm.FetchPage(pageID)
if err != nil {
return nil, err
}
n := node{p}
if n.isLeaf() {
i := n.lowerBound(key)
if i < n.numKeys() && n.key(i) == key {
t.bpm.UnpinPage(pageID, false)
return nil, ErrDuplicateKey
}
if n.numKeys() < maxLeafKeys {
n.insertLeafEntry(i, leafEntry{key, rid})
return nil, t.bpm.UnpinPage(pageID, true)
}
split, err := t.splitLeaf(n, i, leafEntry{key, rid})
t.bpm.UnpinPage(pageID, true)
return split, err
}
// 内部ノード: 子をたどって再帰的に挿入する
idx := n.childIndex(key)
childID := n.child(idx)
if err := t.bpm.UnpinPage(pageID, false); err != nil {
return nil, err
}
childSplit, err := t.insert(childID, key, rid)
if err != nil || childSplit == nil {
return nil, err
}
// 子が分割されたので、区切りキーと新しい子をこのノードに追加する
p, err = t.bpm.FetchPage(pageID)
if err != nil {
return nil, err
}
n = node{p}
if n.numKeys() < maxInternalKeys {
n.insertInternalEntry(idx, childSplit.key, childSplit.right)
return nil, t.bpm.UnpinPage(pageID, true)
}
split, err := t.splitInternal(n, idx, childSplit.key, childSplit.right)
t.bpm.UnpinPage(pageID, true)
return split, err
}内部ノードでは、子へ再帰する前に一度アンピンし、子が分割されたときだけ改めてフェッチしています。木全体をロックしているので、その間に他の操作がノードを書き換えることはありません。
分割の処理は次のとおりです。
// splitLeaf は満杯の葉に新しいエントリを加えたうえで、左右2つの葉に分ける
func (t *BPlusTree) splitLeaf(left node, pos int, e leafEntry) (*splitResult, error) {
entries := left.leafEntries()
entries = append(entries[:pos], append([]leafEntry{e}, entries[pos:]...)...)
mid := len(entries) / 2
rightID, rp, err := t.bpm.NewPage()
if err != nil {
return nil, err
}
right := node{rp}
right.initLeaf()
right.setLeafEntries(entries[mid:])
right.setNext(left.next()) // 右の葉は、元の右隣を引き継ぐ
left.setLeafEntries(entries[:mid])
left.setNext(rightID)
if err := t.bpm.UnpinPage(rightID, true); err != nil {
return nil, err
}
// 右の葉の最小キーを区切りキーとして親にコピーする
return &splitResult{key: entries[mid].key, right: rightID}, nil
}
// splitInternal は満杯の内部ノードに区切りキーを加えたうえで、左右2つに分ける
func (t *BPlusTree) splitInternal(left node, pos int, key int64, rightChild page.PageID) (*splitResult, error) {
keys, children := left.internalContents()
keys = append(keys[:pos], append([]int64{key}, keys[pos:]...)...)
children = append(children[:pos+1], append([]page.PageID{rightChild}, children[pos+1:]...)...)
mid := len(keys) / 2
rightID, rp, err := t.bpm.NewPage()
if err != nil {
return nil, err
}
right := node{rp}
right.initInternal(children[mid+1])
right.setInternalContents(keys[mid+1:], children[mid+1:])
left.setInternalContents(keys[:mid], children[:mid+1])
if err := t.bpm.UnpinPage(rightID, true); err != nil {
return nil, err
}
// 真ん中のキーは左右どちらにも残さず、親へ移動する
return &splitResult{key: keys[mid], right: rightID}, nil
}
// growRoot はルートが分割されたときに木を1段高くする
// ルートの中身を新しいページへ移し、ルート自身は2つの子を持つ内部ノードに作り直す。
// こうするとルートのPageIDが変わらないので、カタログを書き換えずに済む
func (t *BPlusTree) growRoot(split *splitResult) error {
rootPage, err := t.bpm.FetchPage(t.rootPageID)
if err != nil {
return err
}
leftID, leftPage, err := t.bpm.NewPage()
if err != nil {
t.bpm.UnpinPage(t.rootPageID, false)
return err
}
*leftPage = *rootPage // ページ全体をコピーしてから、PageIDだけ付け替える
leftPage.SetPageID(leftID)
root := node{rootPage}
root.initInternal(leftID)
root.insertInternalEntry(0, split.key, split.right)
if err := t.bpm.UnpinPage(leftID, true); err != nil {
return err
}
return t.bpm.UnpinPage(t.rootPageID, true)
}splitLeaf では、元の葉を書き換える前に left.next() を読んで右の葉に引き継いでいます。順序を逆にすると、元の右隣へのリンクが失われ、範囲検索で葉を1つ飛ばしてしまいます。
削除
削除は、キーが属する葉からエントリを取り除くだけにします。
// Delete はkeyのエントリを削除する
// 本シリーズではノードのマージ・再分配は行わない（葉が空になっても残す）
func (t *BPlusTree) Delete(key int64) error {
t.mu.Lock()
defer t.mu.Unlock()
leafID, err := t.findLeaf(key)
if err != nil {
return err
}
p, err := t.bpm.FetchPage(leafID)
if err != nil {
return err
}
n := node{p}
i := n.lowerBound(key)
if i >= n.numKeys() || n.key(i) != key {
t.bpm.UnpinPage(leafID, false)
return ErrKeyNotFound
}
n.removeLeafEntry(i)
return t.bpm.UnpinPage(leafID, true)
}教科書的なB+木では、削除でノードのエントリが半分を下回ったら、隣のノードからエントリを借りる（再分配）か、隣のノードと1つにまとめる（マージ）ことで、木のバランスを保ちます。マージすると親の区切りキーも1つ減るので、親でも同じ処理が連鎖することがあります。
本シリーズではこの再分配・マージを実装しません。エントリが少ない葉や空の葉が残っても、検索と範囲検索の結果は正しく、領域が無駄になるだけだからです。実際、PostgreSQLのB+木も、中身の残っているページどうしをマージすることはせず、完全に空になったページだけを後でVACUUMの際に取り除きます。
最後に、テストで木の高さを確かめるための Height も用意しておきます。すべての葉の深さは等しいので、最も左の子をたどって数えれば十分です。
// Height は木の高さ（ルートから葉までのノード数）を返す
func (t *BPlusTree) Height() (int, error) {
t.mu.RLock()
defer t.mu.RUnlock()
height := 1
id := t.rootPageID
for {
p, err := t.bpm.FetchPage(id)
if err != nil {
return 0, err
}
n := node{p}
leaf, next := n.isLeaf(), n.child(0)
if err := t.bpm.UnpinPage(id, false); err != nil {
return 0, err
}
if leaf {
return height, nil
}
height++
id = next
}
}テストを書く
1件の挿入と検索、重複キー、10万件の挿入による木の成長、ランダムな順序での挿入、範囲検索、削除をテストします。
// storage/btree/btree_test.go
package btree_test
import (
"errors"
"math/rand"
"os"
"testing"
"github.com/yourname/go-rdbms/storage/btree"
"github.com/yourname/go-rdbms/storage/buffer"
"github.com/yourname/go-rdbms/storage/disk"
"github.com/yourname/go-rdbms/storage/heap"
"github.com/yourname/go-rdbms/storage/page"
)
func setupBTree(t *testing.T) (*btree.BPlusTree, func()) {
t.Helper()
f, err := os.CreateTemp("", "test-btree-*.db")
if err != nil {
t.Fatal(err)
}
f.Close()
dm, err := disk.NewFileDiskManager(f.Name())
if err != nil {
os.Remove(f.Name())
t.Fatal(err)
}
bpm := buffer.NewBufferPoolManager(dm, 64)
bt, err := btree.NewBPlusTree(bpm)
if err != nil {
t.Fatal(err)
}
cleanup := func() {
dm.Close()
os.Remove(f.Name())
}
return bt, cleanup
}
// ridFor はテスト用に、キーから決まるダミーのRIDを作る
func ridFor(key int64) heap.RID {
return heap.RID{PageID: page.PageID(key / 100), SlotID: uint16(key % 100)}
}
func TestBPlusTree_InsertAndSearch(t *testing.T) {
bt, cleanup := setupBTree(t)
defer cleanup()
if err := bt.Insert(42, ridFor(42)); err != nil {
t.Fatal(err)
}
rid, found, err := bt.Search(42)
if err != nil {
t.Fatal(err)
}
if !found || rid != ridFor(42) {
t.Errorf("検索結果が不正: found=%v, rid=%v", found, rid)
}
if _, found, _ := bt.Search(999); found {
t.Error("存在しないキーが見つかった")
}
}
func TestBPlusTree_DuplicateKey(t *testing.T) {
bt, cleanup := setupBTree(t)
defer cleanup()
bt.Insert(1, ridFor(1))
if err := bt.Insert(1, ridFor(1)); !errors.Is(err, btree.ErrDuplicateKey) {
t.Errorf("重複キーはErrDuplicateKeyになるはず: got %v", err)
}
}
func TestBPlusTree_ManyKeysGrowTree(t *testing.T) {
bt, cleanup := setupBTree(t)
defer cleanup()
const n = 100000
for i := int64(0); i < n; i++ {
if err := bt.Insert(i, ridFor(i)); err != nil {
t.Fatalf("キー%dの挿入に失敗: %v", i, err)
}
}
height, err := bt.Height()
if err != nil {
t.Fatal(err)
}
t.Logf("%d件挿入後の木の高さ: %d", n, height)
if height < 3 {
t.Errorf("内部ノードが多段になっていない: height=%d", height)
}
for i := int64(0); i < n; i++ {
rid, found, err := bt.Search(i)
if err != nil {
t.Fatal(err)
}
if !found || rid != ridFor(i) {
t.Fatalf("キー%dが正しく引けない: found=%v, rid=%v", i, found, rid)
}
}
}
func TestBPlusTree_RandomOrder(t *testing.T) {
bt, cleanup := setupBTree(t)
defer cleanup()
const n = 20000
keys := rand.New(rand.NewSource(1)).Perm(n)
for _, k := range keys {
if err := bt.Insert(int64(k), ridFor(int64(k))); err != nil {
t.Fatal(err)
}
}
// 全範囲をスキャンすると、キー順（= RID順）に全件が返る
rids, err := bt.RangeScan(0, n-1)
if err != nil {
t.Fatal(err)
}
if len(rids) != n {
t.Fatalf("件数不一致: want %d, got %d", n, len(rids))
}
for i, rid := range rids {
if rid != ridFor(int64(i)) {
t.Fatalf("%d番目がキー順になっていない: %v", i, rid)
}
}
}
func TestBPlusTree_RangeScan(t *testing.T) {
bt, cleanup := setupBTree(t)
defer cleanup()
for i := int64(1); i <= 1000; i++ {
bt.Insert(i*10, ridFor(i*10)) // 10, 20, ..., 10000
}
tests := []struct {
min, max int64
want int
}{
{20, 40, 3}, // 20, 30, 40
{15, 45, 3}, // 境界がキーと一致しない場合
{1, 10000, 1000}, // 全件（複数の葉にまたがる）
{5000, 5000, 1}, // 1点
{10001, 20000, 0}, // 範囲外
{40, 20, 0}, // min > max
}
for _, tt := range tests {
rids, err := bt.RangeScan(tt.min, tt.max)
if err != nil {
t.Fatal(err)
}
if len(rids) != tt.want {
t.Errorf("RangeScan(%d, %d): want %d件, got %d件", tt.min, tt.max, tt.want, len(rids))
}
}
}
func TestBPlusTree_Delete(t *testing.T) {
bt, cleanup := setupBTree(t)
defer cleanup()
const n = 2000
for i := int64(0); i < n; i++ {
bt.Insert(i, ridFor(i))
}
// 偶数のキーを削除する
for i := int64(0); i < n; i += 2 {
if err := bt.Delete(i); err != nil {
t.Fatal(err)
}
}
for i := int64(0); i < n; i++ {
_, found, _ := bt.Search(i)
if want := i%2 == 1; found != want {
t.Fatalf("キー%d: want found=%v, got %v", i, want, found)
}
}
if err := bt.Delete(0); !errors.Is(err, btree.ErrKeyNotFound) {
t.Errorf("削除済みキーの削除はErrKeyNotFoundになるはず: got %v", err)
}
rids, _ := bt.RangeScan(0, n)
if len(rids) != n/2 {
t.Errorf("削除後の件数不一致: want %d, got %d", n/2, len(rids))
}
}go test ./storage/btree/... -v期待される出力：
=== RUN TestBPlusTree_InsertAndSearch
--- PASS: TestBPlusTree_InsertAndSearch (0.00s)
=== RUN TestBPlusTree_DuplicateKey
--- PASS: TestBPlusTree_DuplicateKey (0.00s)
=== RUN TestBPlusTree_ManyKeysGrowTree
btree_test.go:93: 100000件挿入後の木の高さ: 3
--- PASS: TestBPlusTree_ManyKeysGrowTree (0.09s)
=== RUN TestBPlusTree_RandomOrder
--- PASS: TestBPlusTree_RandomOrder (0.01s)
=== RUN TestBPlusTree_RangeScan
--- PASS: TestBPlusTree_RangeScan (0.00s)
=== RUN TestBPlusTree_Delete
--- PASS: TestBPlusTree_Delete (0.00s)
PASS
ok github.com/yourname/go-rdbms/storage/btree 0.342s10万件を昇順に挿入すると、葉は分割のたびに半分ずつ埋まった状態で残るので、約690枚の葉ができます。これは内部ノード1つに入る子の数（339）を超えるため、ルートの下に内部ノードの層がもう1段でき、高さが3になります。
ここまでのコード全体像
storage/
├── page/
│ ├── page.go
│ └── slotted_page.go
├── disk/
│ ├── disk_manager.go
│ └── file_disk_manager.go
├── buffer/
│ ├── replacer.go
│ ├── lru_replacer.go
│ └── buffer_pool_manager.go
├── heap/
│ ├── rid.go
│ ├── record.go
│ └── heap_file.go
└── btree/
├── node.go ← ノードのレイアウトと読み書き（本章）
└── btree.go ← 検索・範囲検索・挿入・削除（本章）B+木の設計で意識したポイント
① 区切りキーは右ノードの最小キー、子の選択は「key以下の個数」
葉の分割で右の葉の最小キーを親に上げるので、区切りキーと等しいキーは右の子に入ります。子を選ぶ childIndex もこの約束に合わせて「key以下のキーの個数」で数えます。この2つがずれると、区切りキーと同じ値のキーが見つからなくなります。
② 分割は再帰の戻り値で親に伝える
子のノードは親を知らなくてよく、分割の結果を返り値で返すだけです。ノードに親へのポインタを持たせずに済むので、分割のたびに親ポインタを書き換える手間がありません。
③ ルートのPageIDを固定する
ルートの中身を新しいページに移して木を高くするので、ルートのPageIDは作成時から変わりません。カタログに保存したルートのPageIDを、書き換えずに使い続けられます。
④ マージは省略する
削除でノードが空いても検索結果は正しいので、再分配・マージは実装しません。複雑な処理を省きつつ、正しさは保っています。
まとめ
- インデックスがなければ、1件を探すのにもフルスキャン（O(N)）が必要になる
- B+木は内部ノードに区切りキーだけを、葉にキーとRIDを持ち、葉同士をリンクでつなぐ。1ノードに数百のキーが入るので木が低く、10万件でも高さは3
- 検索はルートから子をたどり、範囲検索は開始位置の葉から右隣へリンクをたどる
- 満杯のノードは分割して区切りキーを親に伝える。葉の分割はキーを「コピー」、内部ノードの分割はキーを「移動」する
- ルートの分割で木は根の側に成長する。本シリーズではルートの中身を移すことでルートのPageIDを固定した
- 削除は葉からエントリを取り除くだけで、再分配・マージは行わない
次章からはSQLエンジンの実装に入ります。まずはSQLの文字列を解析して木構造に変換する**Lexer（字句解析器）とParser（構文解析器）**を実装します。