TsDB2/demo/btree_verify/main.go

package main

// =============================================================================
// B+ 树独立验证 Demo
//
// 目的: 绕开真实 DB 文件 / WAL / BufferPool 等上层, 直接用「内存页存储」驱动
//       B+ 树公开 API, 主动确认是否存在结构或查找错误。
//
// 覆盖路径:
//   - 插入: 叶子分裂 -> 内部节点分裂(升级根)
//   - 查找: 逐键精确查找
//   - 删除: 借位(左/右兄弟) -> 叶子合并 -> 内部节点合并
//
// 校验手段(两套独立证据):
//   1) 功能查找: 所有"存活键"必须查得到且值正确; 已删除键必须查不到
//   2) 结构校验: 父键 == 子树最小键 / 相邻子树严格分离 / 叶子链顺序 /
//      叶子条目集合 == 逻辑存活集合
// =============================================================================

import (
	"TsDB2/DB/core/index/btree"
	"TsDB2/DB/core/page"
	"bytes"
	"encoding/binary"
	"fmt"
	"math/rand"
	"sort"
	"unsafe"
)

var totalFail int

func report(ok bool, msg string) {
	if ok {
		fmt.Printf("  [PASS] %s\n", msg)
	} else {
		totalFail++
		fmt.Printf("  [FAIL] %s\n", msg)
	}
}

// =============================================================================
// 内存页存储 (实现 page.HandleDb)
// =============================================================================

type memStore struct {
	pages map[uint32][]byte
	next  uint32
}

func newMemStore() *memStore {
	return &memStore{pages: make(map[uint32][]byte), next: 1}
}

func (m *memStore) handle() page.HandleDb {
	return page.HandleDb{
		NewPage: func() uint32 {
			pid := m.next
			m.next++
			return pid
		},
		FreePage: func(pid uint32) { delete(m.pages, pid) },
		SavePage: func(pid uint32, buf []byte) error {
			cp := make([]byte, len(buf))
			copy(cp, buf)
			m.pages[pid] = cp
			return nil
		},
		ReadPage: func(pid uint32, buf []byte) error {
			p, ok := m.pages[pid]
			if !ok {
				return fmt.Errorf("page %d not found", pid)
			}
			copy(buf, p)
			return nil
		},
	}
}

// =============================================================================
// 原始节点解析 (不依赖 btree 包内部函数)
// =============================================================================

type rawNode struct {
	buf     []byte
	head    *page.IndexHead
	entries []byte
}

func loadNode(h page.HandleDb, pid uint32) *rawNode {
	buf := make([]byte, page.IndexPageSize)
	if err := h.ReadPage(pid, buf); err != nil {
		return nil
	}
	head := (*page.IndexHead)(unsafe.Pointer(&buf[0]))
	return &rawNode{buf: buf, head: head, entries: buf[page.IndexHeadSize:]}
}

func (n *rawNode) el() int    { return int(n.head.EntryLen) }
func (n *rawNode) cnt() int   { return int(n.head.Count) }
func (n *rawNode) leaf() bool { return n.head.IsLeaf == 1 }
func (n *rawNode) entry(i int) []byte {
	el := n.el()
	return n.entries[i*el : (i+1)*el]
}

// kb 把 key 的前 8 字节按大端整数打印, 便于阅读
func kb(k []byte) string {
	if len(k) >= 8 {
		return fmt.Sprintf("%d", binary.BigEndian.Uint64(k[:8]))
	}
	return fmt.Sprintf("%x", k)
}

func intKey(e []byte) []byte   { return e[:len(e)-4] }
func childPID(e []byte) uint32 { return binary.BigEndian.Uint32(e[len(e)-4:]) }

func leafKey(e []byte, secondary bool) []byte {
	if secondary {
		return e[:len(e)-8] // [key + PKID(8)]
	}
	return e[:len(e)-4] // [key(8) + dpID(4)]
}

func leftmostKeyOf(h page.HandleDb, pid uint32, secondary bool) ([]byte, bool) {
	for {
		n := loadNode(h, pid)
		if n == nil {
			return nil, false
		}
		if n.leaf() {
			if n.cnt() == 0 {
				return nil, false
			}
			k := leafKey(n.entry(0), secondary)
			out := make([]byte, len(k))
			copy(out, k)
			return out, true
		}
		if n.cnt() == 0 {
			return nil, false
		}
		pid = childPID(n.entry(0))
	}
}

func rightmostKeyOf(h page.HandleDb, pid uint32, secondary bool) ([]byte, bool) {
	for {
		n := loadNode(h, pid)
		if n == nil {
			return nil, false
		}
		if n.leaf() {
			if n.cnt() == 0 {
				return nil, false
			}
			k := leafKey(n.entry(n.cnt()-1), secondary)
			out := make([]byte, len(k))
			copy(out, k)
			return out, true
		}
		if n.cnt() == 0 {
			return nil, false
		}
		pid = childPID(n.entry(n.cnt() - 1))
	}
}

// leafChain 从最左叶沿 NextPage 走完整条叶子链
func leafChain(h page.HandleDb, root uint32) []uint32 {
	if root == 0 {
		return nil
	}
	pid := root
	for {
		n := loadNode(h, pid)
		if n == nil {
			return nil
		}
		if n.leaf() {
			break
		}
		if n.cnt() == 0 {
			return nil
		}
		pid = childPID(n.entry(0))
	}
	var out []uint32
	seen := map[uint32]bool{}
	for pid != 0 && !seen[pid] {
		seen[pid] = true
		out = append(out, pid)
		n := loadNode(h, pid)
		if n == nil {
			break
		}
		pid = n.head.Hdr.NextPage
	}
	return out
}

// =============================================================================
// 结构校验器
// =============================================================================

func validateTree(h page.HandleDb, root uint32, secondary bool) []string {
	var issues []string
	if root == 0 {
		return issues
	}
	visited := map[uint32]bool{}
	var leafSeq []uint32

	var walk func(pid uint32, depth int)
	walk = func(pid uint32, depth int) {
		if visited[pid] {
			issues = append(issues, fmt.Sprintf("节点被重复引用/成环 pid=%d", pid))
			return
		}
		visited[pid] = true

		n := loadNode(h, pid)
		if n == nil {
			issues = append(issues, fmt.Sprintf("加载失败 pid=%d", pid))
			return
		}
		// 根节点为空叶是合法的"空树"; 非根节点为空则说明删除收尾有问题
		if n.cnt() == 0 && depth > 0 {
			issues = append(issues, fmt.Sprintf("节点为空 pid=%d leaf=%v", pid, n.leaf()))
		}
		if n.leaf() {
			for i := 1; i < n.cnt(); i++ {
				if bytes.Compare(leafKey(n.entry(i-1), secondary), leafKey(n.entry(i), secondary)) >= 0 {
					issues = append(issues, fmt.Sprintf("叶节点键未严格递增 pid=%d idx=%d", pid, i))
				}
			}
			leafSeq = append(leafSeq, pid)
			return
		}

		// 内部节点: 条目有序
		for i := 1; i < n.cnt(); i++ {
			if bytes.Compare(intKey(n.entry(i-1)), intKey(n.entry(i))) >= 0 {
				issues = append(issues, fmt.Sprintf("内部节点键未严格递增 pid=%d idx=%d", pid, i))
			}
		}
		for i := 0; i < n.cnt(); i++ {
			cp := childPID(n.entry(i))
			ck, ok := leftmostKeyOf(h, cp, secondary)
			if !ok {
				issues = append(issues, fmt.Sprintf("内部节点 pid=%d 的第 %d 个子节点无最左键(空?) pid=%d", pid, i, cp))
				continue
			}
			stored := intKey(n.entry(i))
			if secondary {
				// 二级树内部键 = key + 4B 填充, 取前缀比较
				if len(stored) < len(ck) || !bytes.Equal(stored[:len(ck)], ck) {
					issues = append(issues, fmt.Sprintf("父键 != 子树最小键 pid=%d entry%d storedKey=%s childMin=%s", pid, i, kb(stored), kb(ck)))
				}
			} else if !bytes.Equal(stored, ck) {
				issues = append(issues, fmt.Sprintf("父键 != 子树最小键 pid=%d entry%d storedKey=%s childMin=%s", pid, i, kb(stored), kb(ck)))
			}
			if i > 0 {
				pm, ok2 := rightmostKeyOf(h, childPID(n.entry(i-1)), secondary)
				if !ok2 || bytes.Compare(pm, ck) >= 0 {
					issues = append(issues, fmt.Sprintf("相邻子树未严格分离 pid=%d child%d.max >= child%d.min", pid, i-1, i))
				}
			}
			walk(cp, depth+1)
		}
	}
	walk(root, 0)

	chain := leafChain(h, root)
	if len(chain) != len(leafSeq) {
		issues = append(issues, fmt.Sprintf("叶子链长度=%d 与 DFS 可达叶子数=%d 不一致", len(chain), len(leafSeq)))
	} else {
		for i := range chain {
			if chain[i] != leafSeq[i] {
				issues = append(issues, fmt.Sprintf("叶子链顺序与树结构不一致 idx=%d chain=%d dfs=%d", i, chain[i], leafSeq[i]))
				break
			}
		}
	}
	return issues
}

// collectLeafEntries 沿叶子链收集所有条目 (hex), 排序返回
func collectLeafEntries(h page.HandleDb, root uint32) []string {
	var out []string
	for _, pid := range leafChain(h, root) {
		n := loadNode(h, pid)
		if n == nil {
			continue
		}
		el := n.el()
		for i := 0; i < n.cnt(); i++ {
			out = append(out, fmt.Sprintf("%x", n.entry(i)[:el]))
		}
	}
	sort.Strings(out)
	return out
}

func sameStrings(a, b []string) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func stats(h page.HandleDb, root uint32) (leafCount, entryCount, depth int) {
	if root == 0 {
		return 0, 0, 0
	}
	var walk func(pid uint32, d int)
	walk = func(pid uint32, d int) {
		n := loadNode(h, pid)
		if n == nil {
			return
		}
		if d+1 > depth {
			depth = d + 1
		}
		if n.leaf() {
			leafCount++
			entryCount += n.cnt()
			return
		}
		for i := 0; i < n.cnt(); i++ {
			walk(childPID(n.entry(i)), d+1)
		}
	}
	walk(root, 0)
	return
}

// =============================================================================
// 通用验证
// =============================================================================

type treeAPI struct {
	name      string
	secondary bool
	keyOf     func(v uint64) []byte
	search    func(root uint32, key []byte, h page.HandleDb) (uint64, bool)
	entryHex  func(v uint64) string
}

func verify(api treeAPI, title string, root uint32, h page.HandleDb, alive, dead []uint64) {
	leafCount, entryCount, depth := stats(h, root)
	fmt.Printf("\n--- %s ---\n", title)
	fmt.Printf("  [info] root=%d 叶子数=%d 条目数=%d 层数=%d 逻辑存活=%d\n",
		root, leafCount, entryCount, depth, len(alive))

	// 1) 存活键必须可查
	miss := 0
	wrongVal := 0
	var missSamples, wrongSamples []uint64
	for _, v := range alive {
		got, ok := api.search(root, api.keyOf(v), h)
		if !ok {
			miss++
			if len(missSamples) < 8 {
				missSamples = append(missSamples, v)
			}
			continue
		}
		if got != v {
			wrongVal++
			if len(wrongSamples) < 8 {
				wrongSamples = append(wrongSamples, v)
			}
		}
	}
	report(miss == 0, fmt.Sprintf("查找存活键: %d/%d 命中, 缺失 %d", len(alive)-miss, len(alive), miss))
	if len(missSamples) > 0 {
		fmt.Printf("         [样例] 查不到的存活键: %v\n", missSamples)
	}
	report(wrongVal == 0, fmt.Sprintf("查找值正确性: 值错误 %d", wrongVal))
	if len(wrongSamples) > 0 {
		fmt.Printf("         [样例] 返回值错误的键: %v\n", wrongSamples)
	}

	// 2) 已删除键必须查不到
	if len(dead) > 0 {
		ghost := 0
		var ghostSamples []uint64
		for _, v := range dead {
			if _, ok := api.search(root, api.keyOf(v), h); ok {
				ghost++
				if len(ghostSamples) < 8 {
					ghostSamples = append(ghostSamples, v)
				}
			}
		}
		report(ghost == 0, fmt.Sprintf("已删除键不应被查到: 幽灵 %d/%d", ghost, len(dead)))
		if len(ghostSamples) > 0 {
			fmt.Printf("         [样例] 删除后仍能查到的键: %v\n", ghostSamples)
		}
	}

	// 3) 结构校验
	issues := validateTree(h, root, api.secondary)
	report(len(issues) == 0, fmt.Sprintf("结构校验: 问题 %d 条", len(issues)))
	for i, s := range issues {
		if i >= 12 {
			fmt.Printf("         ... 其余 %d 条省略\n", len(issues)-i)
			break
		}
		fmt.Printf("         - %s\n", s)
	}

	// 4) 叶子条目集合 == 逻辑存活集合
	got := collectLeafEntries(h, root)
	want := make([]string, 0, len(alive))
	for _, v := range alive {
		want = append(want, api.entryHex(v))
	}
	sort.Strings(want)
	report(sameStrings(got, want), fmt.Sprintf("叶子条目集合 == 逻辑存活集合 (叶子=%d 逻辑=%d)", len(got), len(want)))
	if !sameStrings(got, want) {
		gm, wm := map[string]bool{}, map[string]bool{}
		for _, s := range got {
			gm[s] = true
		}
		for _, s := range want {
			wm[s] = true
		}
		lost, extra := 0, 0
		for _, s := range want {
			if !gm[s] {
				lost++
			}
		}
		for _, s := range got {
			if !wm[s] {
				extra++
			}
		}
		fmt.Printf("         [样例] 叶子中丢失 %d 条, 多出 %d 条\n", lost, extra)
	}
}

// =============================================================================
// 主键 B+ 树测试
// =============================================================================

func testPrimary() {
	fmt.Println("\n================ 主键 B+ 树 (BTreePKInsert / Search / Delete) ================")
	h := newMemStore().handle()
	const N = 2500

	api := treeAPI{
		name:      "primary",
		secondary: false,
		keyOf:     u64key,
		search: func(root uint32, key []byte, hh page.HandleDb) (uint64, bool) {
			dp, ok := btree.BTreePKSearch(root, key, hh)
			return uint64(dp), ok
		},
		entryHex: func(v uint64) string { return pkEntryHex(v, uint32(v)) },
	}

	// ---- 阶段 1: 全量插入 ----
	root := uint32(0)
	insertErr := 0
	for i := 1; i <= N; i++ {
		r, _, _, err := btree.BTreePKInsert(root, u64key(uint64(i)), uint32(i), h)
		if err != nil {
			insertErr++
			if insertErr <= 5 {
				fmt.Printf("  [FAIL] 插入 key=%d 出错: %v\n", i, err)
			}
			continue
		}
		root = r
	}
	report(insertErr == 0, fmt.Sprintf("插入 %d 个键", N))

	alive := make([]uint64, 0, N)
	for i := 1; i <= N; i++ {
		alive = append(alive, uint64(i))
	}
	verify(api, "阶段1: 全量插入后", root, h, alive, nil)

	// ---- 阶段 2: 删除偶数键 (打散, 触发合并/借位) ----
	var dead []uint64
	var nextAlive []uint64
	delErr := 0
	for _, v := range alive {
		if v%2 != 0 {
			nextAlive = append(nextAlive, v)
			continue
		}
		r, _, err := btree.BTreePKDelete(root, u64key(v), h)
		if err != nil {
			delErr++
			if delErr <= 5 {
				fmt.Printf("  [FAIL] 删除 key=%d 出错: %v\n", v, err)
			}
			nextAlive = append(nextAlive, v) // 删不掉则仍视为存活
			continue
		}
		root = r
		dead = append(dead, v)
	}
	report(delErr == 0, fmt.Sprintf("删除偶数键 (%d 个)", len(dead)))
	verify(api, "阶段2: 删除偶数键后", root, h, nextAlive, dead)

	// ---- 阶段 3: 逆序删除剩余全部键 ----
	cur := append([]uint64(nil), nextAlive...)
	sort.Slice(cur, func(i, j int) bool { return cur[i] > cur[j] })
	delErr = 0
	for _, v := range cur {
		r, _, err := btree.BTreePKDelete(root, u64key(v), h)
		if err != nil {
			delErr++
			if delErr <= 5 {
				fmt.Printf("  [FAIL] 删除 key=%d 出错: %v\n", v, err)
			}
			continue
		}
		root = r
		dead = append(dead, v)
	}
	report(delErr == 0, fmt.Sprintf("逆序删除剩余 %d 个键", len(cur)))
	verify(api, "阶段3: 全部删除后", root, h, nil, dead)
}

// =============================================================================
// 二级 B+ 树测试
// =============================================================================

func testSecondary() {
	fmt.Println("\n================ 二级 B+ 树 (SBTInsert / SBTSearch / SBTDelete) ================")
	h := newMemStore().handle()
	const N = 2500

	api := treeAPI{
		name:      "secondary",
		secondary: true,
		keyOf:     u64key,
		search: func(root uint32, key []byte, hh page.HandleDb) (uint64, bool) {
			return btree.SBTSearch(root, key, hh)
		},
		entryHex: func(v uint64) string { return sbtEntryHex(v, v) },
	}

	// ---- 阶段 1: 顺序插入 ----
	root := uint32(0)
	insertErr := 0
	for i := 1; i <= N; i++ {
		r, err := btree.SBTInsert(root, sbtEntryBytes(uint64(i), uint64(i)), h)
		if err != nil {
			insertErr++
			if insertErr <= 5 {
				fmt.Printf("  [FAIL] 插入 key=%d 出错: %v\n", i, err)
			}
			continue
		}
		root = r
	}
	report(insertErr == 0, fmt.Sprintf("插入 %d 个条目", N))

	alive := make([]uint64, 0, N)
	for i := 1; i <= N; i++ {
		alive = append(alive, uint64(i))
	}
	verify(api, "阶段1: 全量插入后", root, h, alive, nil)

	// ---- 阶段 2: 删除偶数键 ----
	var dead []uint64
	var nextAlive []uint64
	delErr := 0
	for _, v := range alive {
		if v%2 != 0 {
			nextAlive = append(nextAlive, v)
			continue
		}
		r, err := btree.SBTDelete(root, u64key(v), h)
		if err != nil {
			delErr++
			if delErr <= 5 {
				fmt.Printf("  [FAIL] 删除 key=%d 出错: %v\n", v, err)
			}
			nextAlive = append(nextAlive, v)
			continue
		}
		root = r
		dead = append(dead, v)
	}
	report(delErr == 0, fmt.Sprintf("删除偶数键 (%d 个)", len(dead)))
	verify(api, "阶段2: 删除偶数键后", root, h, nextAlive, dead)

	// ---- 阶段 3: 逆序删除剩余全部 ----
	cur := append([]uint64(nil), nextAlive...)
	sort.Slice(cur, func(i, j int) bool { return cur[i] > cur[j] })
	delErr = 0
	for _, v := range cur {
		r, err := btree.SBTDelete(root, u64key(v), h)
		if err != nil {
			delErr++
			if delErr <= 5 {
				fmt.Printf("  [FAIL] 删除 key=%d 出错: %v\n", v, err)
			}
			continue
		}
		root = r
		dead = append(dead, v)
	}
	report(delErr == 0, fmt.Sprintf("逆序删除剩余 %d 个键", len(cur)))
	verify(api, "阶段3: 全部删除后", root, h, nil, dead)
}

// =============================================================================
// 二级 B+ 树 (大键) 测试: 用小容量节点强制「内部节点分裂」, 得到 3 层树
// =============================================================================

const bigKeyLen = 248 // key 长度 (字节); 使单节点仅容纳 (8192-32)/256 = 31 个子节点

func bigKey(v uint64) []byte {
	b := make([]byte, bigKeyLen)
	binary.BigEndian.PutUint64(b, v)
	return b
}

func bigEntry(k, pkid uint64) []byte {
	b := make([]byte, bigKeyLen+8)
	binary.BigEndian.PutUint64(b, k)
	binary.BigEndian.PutUint64(b[bigKeyLen:], pkid)
	return b
}

// mkKey 生成指定长度的索引键 (前 8 字节为大端整数, 其余补零)
func mkKey(keyLen int, v uint64) []byte {
	b := make([]byte, keyLen)
	binary.BigEndian.PutUint64(b, v)
	return b
}

// mkEntry 生成二级索引条目 [key(keyLen) + pkID(8)]
func mkEntry(keyLen int, k, pkid uint64) []byte {
	b := make([]byte, keyLen+8)
	binary.BigEndian.PutUint64(b, k)
	binary.BigEndian.PutUint64(b[keyLen:], pkid)
	return b
}

func testSecondaryBigKey() {
	fmt.Println("\n============ 二级 B+ 树 (keyLen=248, 强制内部节点分裂 => 3 层) ============")
	h := newMemStore().handle()
	const N = 1500

	api := treeAPI{
		name:      "secondary-bigkey",
		secondary: true,
		keyOf:     bigKey,
		search: func(root uint32, key []byte, hh page.HandleDb) (uint64, bool) {
			return btree.SBTSearch(root, key, hh)
		},
		entryHex: func(v uint64) string { return fmt.Sprintf("%x", bigEntry(v, v)) },
	}

	root := uint32(0)
	insertErr := 0
	for i := 1; i <= N; i++ {
		r, err := btree.SBTInsert(root, bigEntry(uint64(i), uint64(i)), h)
		if err != nil {
			insertErr++
			if insertErr <= 5 {
				fmt.Printf("  [FAIL] 插入 key=%d 出错: %v\n", i, err)
			}
			continue
		}
		root = r
	}
	report(insertErr == 0, fmt.Sprintf("插入 %d 个大键条目", N))

	alive := make([]uint64, 0, N)
	for i := 1; i <= N; i++ {
		alive = append(alive, uint64(i))
	}
	verify(api, "阶段1: 大键全量插入后(应为 3 层)", root, h, alive, nil)
}

// =============================================================================
// 定向测试: 触发「从右兄弟借位」
// 触发条件: 待删除叶子位于 childIdx==0 (没有左兄弟), 且右兄弟条目数 > 1
// 做法: 先建树, 再清空最左叶子的全部键
// =============================================================================

func apiPrimary() treeAPI {
	return treeAPI{
		name:      "primary",
		secondary: false,
		keyOf:     u64key,
		search: func(root uint32, key []byte, hh page.HandleDb) (uint64, bool) {
			dp, ok := btree.BTreePKSearch(root, key, hh)
			return uint64(dp), ok
		},
		entryHex: func(v uint64) string { return pkEntryHex(v, uint32(v)) },
	}
}

func apiSecondary() treeAPI {
	return treeAPI{
		name:      "secondary",
		secondary: true,
		keyOf:     u64key,
		search: func(root uint32, key []byte, hh page.HandleDb) (uint64, bool) {
			return btree.SBTSearch(root, key, hh)
		},
		entryHex: func(v uint64) string { return sbtEntryHex(v, v) },
	}
}

func k2v8(k []byte) uint64 { return binary.BigEndian.Uint64(k[:8]) }

// collectLeafKeys 取指定叶子页中所有条目的索引键
func collectLeafKeys(h page.HandleDb, pid uint32, secondary bool) [][]byte {
	n := loadNode(h, pid)
	if n == nil {
		return nil
	}
	out := make([][]byte, 0, n.cnt())
	for i := 0; i < n.cnt(); i++ {
		k := leafKey(n.entry(i), secondary)
		c := make([]byte, len(k))
		copy(c, k)
		out = append(out, c)
	}
	return out
}

func deleteLeftmostLeaf(title string, api treeAPI, root uint32, h page.HandleDb, n int,
	remove func(root uint32, v uint64, h page.HandleDb) (uint32, error)) uint32 {
	chain := leafChain(h, root)
	if len(chain) < 2 {
		report(false, title+": 前置条件不足(叶子数<2), 无法触发借位")
		return root
	}
	keys := collectLeafKeys(h, chain[0], api.secondary)
	fmt.Printf("  [info] 最左叶子 pid=%d 含 %d 个键\n", chain[0], len(keys))
	dead := map[uint64]bool{}
	errCnt := 0
	for _, k := range keys {
		v := k2v8(k)
		r, err := remove(root, v, h)
		if err != nil {
			errCnt++
			if errCnt <= 5 {
				fmt.Printf("  [FAIL] %s: 删除最左叶子键 %d 出错: %v\n", title, v, err)
			}
			continue
		}
		root = r
		dead[v] = true
	}
	report(errCnt == 0, fmt.Sprintf("%s: 清空最左叶子 (%d 个键, 失败 %d)", title, len(keys), errCnt))
	var alive, deadList []uint64
	for i := 1; i <= n; i++ {
		if dead[uint64(i)] {
			deadList = append(deadList, uint64(i))
		} else {
			alive = append(alive, uint64(i))
		}
	}
	verify(api, "清空最左叶子后", root, h, alive, deadList)
	return root
}

func testPrimaryBorrowRight() {
	fmt.Println("\n========= 主键 B+ 树: 定向触发「从右兄弟借位」=========")
	h := newMemStore().handle()
	const N = 20000
	root := uint32(0)
	for i := 1; i <= N; i++ {
		r, _, _, err := btree.BTreePKInsert(root, u64key(uint64(i)), uint32(i), h)
		if err != nil {
			fmt.Printf("  [FAIL] 插入 %d 出错: %v\n", i, err)
			return
		}
		root = r
	}
	deleteLeftmostLeaf("主键树", apiPrimary(), root, h, N,
		func(r uint32, v uint64, hh page.HandleDb) (uint32, error) {
			nr, _, err := btree.BTreePKDelete(r, u64key(v), hh)
			return nr, err
		})
}

func testSecondaryBorrowRight() {
	fmt.Println("\n========= 二级 B+ 树(大键,3层): 定向触发「从右兄弟借位」=========")
	h := newMemStore().handle()
	const N = 3000
	root := uint32(0)
	for i := 1; i <= N; i++ {
		r, err := btree.SBTInsert(root, bigEntry(uint64(i), uint64(i)), h)
		if err != nil {
			fmt.Printf("  [FAIL] 插入 %d 出错: %v\n", i, err)
			return
		}
		root = r
	}
	api := apiSecondary()
	api.keyOf = bigKey
	api.entryHex = func(v uint64) string { return fmt.Sprintf("%x", bigEntry(v, v)) }
	deleteLeftmostLeaf("二级树", api, root, h, N,
		func(r uint32, v uint64, hh page.HandleDb) (uint32, error) {
			return btree.SBTDelete(r, bigKey(v), hh)
		})
}

// =============================================================================
// 批量建树 SBTBuildFromSorted (deleter.go 压缩流程会用到)
// =============================================================================

func testSBTBuildFromSorted() {
	fmt.Println("\n========= 二级 B+ 树: SBTBuildFromSorted 批量建树 ===========")
	cases := []struct {
		name   string
		bigKey bool
		n      int
	}{
		{"小键(2层)", false, 2000},
		{"大键(3层)", true, 1500},
	}
	for _, c := range cases {
		h := newMemStore().handle()
		entries := make([][]byte, 0, c.n)
		for i := 1; i <= c.n; i++ {
			if c.bigKey {
				entries = append(entries, bigEntry(uint64(i), uint64(i)))
			} else {
				entries = append(entries, sbtEntryBytes(uint64(i), uint64(i)))
			}
		}
		root := btree.SBTBuildFromSorted(entries, h)
		api := apiSecondary()
		if c.bigKey {
			api.keyOf = bigKey
			api.entryHex = func(v uint64) string { return fmt.Sprintf("%x", bigEntry(v, v)) }
		}
		alive := make([]uint64, 0, c.n)
		for i := 1; i <= c.n; i++ {
			alive = append(alive, uint64(i))
		}
		verify(api, fmt.Sprintf("SBTBuildFromSorted %s n=%d", c.name, c.n), root, h, alive, nil)
	}
}

// =============================================================================
// 深层树验证: 强制 4 层以上, 证明分裂/提升递归没有层数上限
//
// 原理: 节点容量 ≈ (btSplitThreshold - IndexHeadSize) / (keyLen+8)。
//      键长越大, 单节点能放的条目越少, 用较少的数据量即可把树逼到很深。
//      覆盖三条会产生/消除高度的路径:
//        1) 逐条插入  -> 内部节点递归分裂, 树不停长高
//        2) 逆序删除  -> 深层合并/借位 + 根逐层收缩
//        3) 批量建树  -> 自底向上循环, 层数同样不受限
// =============================================================================

func testDeepTree() {
	fmt.Println("\n========= 深层树验证 (强制 4 层以上, 验证深度可无限分裂) ==========")
	cases := []struct {
		keyLen int
		n      int
		minDep int
	}{
		{1000, 4000, 4}, // 单节点约 8 条 -> 预期 5~6 层
		{2000, 1500, 4}, // 单节点约 4 条 -> 预期 7~8 层
	}
	for _, c := range cases {
		kl, n := c.keyLen, c.n
		h := newMemStore().handle()
		api := apiSecondary()
		api.keyOf = func(v uint64) []byte { return mkKey(kl, v) }
		api.entryHex = func(v uint64) string { return fmt.Sprintf("%x", mkEntry(kl, v, v)) }

		// --- 1) 逐条插入 ---
		root := uint32(0)
		insErr := 0
		for i := 1; i <= n; i++ {
			r, err := btree.SBTInsert(root, mkEntry(kl, uint64(i), uint64(i)), h)
			if err != nil {
				insErr++
				if insErr <= 5 {
					fmt.Printf("  [FAIL] keyLen=%d 插入 %d 出错: %v\n", kl, i, err)
				}
				continue
			}
			root = r
		}
		report(insErr == 0, fmt.Sprintf("keyLen=%d 逐条插入 %d 条", kl, n))

		_, _, depth := stats(h, root)
		report(depth >= c.minDep, fmt.Sprintf("keyLen=%d 插入后树高=%d (要求 >=%d: 已突破 3 层)",
			kl, depth, c.minDep))

		alive := make([]uint64, 0, n)
		for i := 1; i <= n; i++ {
			alive = append(alive, uint64(i))
		}
		verify(api, fmt.Sprintf("深层树(keyLen=%d,n=%d) 全量校验", kl, n), root, h, alive, nil)

		// --- 2) 逆序删除全部: 深层合并/借位 + 根逐层收缩 ---
		delErr := 0
		midIssues := 0
		step := n / 8
		if step < 1 {
			step = 1
		}
		for i := n; i >= 1; i-- {
			r, err := btree.SBTDelete(root, mkKey(kl, uint64(i)), h)
			if err != nil {
				delErr++
				if delErr <= 5 {
					fmt.Printf("  [FAIL] keyLen=%d 删除 %d 出错: %v\n", kl, i, err)
				}
				continue
			}
			root = r
			if i%step == 0 {
				if iss := validateTree(h, root, true); len(iss) > 0 {
					midIssues++
					if midIssues <= 3 {
						fmt.Printf("  [info] keyLen=%d 剩 %d 条时结构问题 %d: %s\n", kl, i-1, len(iss), iss[0])
					}
				}
			}
		}
		report(midIssues == 0, fmt.Sprintf("keyLen=%d 删除过程中(每%d步采样)结构始终保持", kl, step))
		report(delErr == 0, fmt.Sprintf("keyLen=%d 逆序删除全部 %d 条", kl, n))
		verify(api, fmt.Sprintf("深层树(keyLen=%d) 删除全部后", kl), root, h, nil, alive)

		// --- 3) SBTBuildFromSorted 批量建树 ---
		h2 := newMemStore().handle()
		entries := make([][]byte, 0, n)
		for i := 1; i <= n; i++ {
			entries = append(entries, mkEntry(kl, uint64(i), uint64(i)))
		}
		root2 := btree.SBTBuildFromSorted(entries, h2)
		_, _, depth2 := stats(h2, root2)
		report(depth2 >= c.minDep, fmt.Sprintf("keyLen=%d 批量建树树高=%d (要求 >=%d)",
			kl, depth2, c.minDep))
		verify(api, fmt.Sprintf("深层批量建树(keyLen=%d,n=%d)", kl, n), root2, h2, alive, nil)
	}
}

// =============================================================================
// 随机压测: 乱序全量插入 -> 随机增删, 每轮做结构校验 + 随机抽样查找
// =============================================================================

type stressConfig struct {
	title    string
	api      treeAPI
	insert   func(root uint32, v uint64, h page.HandleDb) (uint32, error)
	remove   func(root uint32, v uint64, h page.HandleDb) (uint32, error)
	keySpace uint64
	rounds   int
	batch    int
	seed     int64
}

func runStress(h page.HandleDb, c stressConfig) {
	fmt.Printf("\n--- 随机压测 %s (keySpace=%d, %d 轮 x %d 次) ---\n",
		c.title, c.keySpace, c.rounds, c.batch)
	rng := rand.New(rand.NewSource(c.seed))
	root := uint32(0)
	alive := map[uint64]bool{}
	deadSet := map[uint64]bool{}
	opErr := 0
	mark := func(format string, a ...interface{}) {
		opErr++
		if opErr <= 8 {
			fmt.Printf("  [FAIL] "+format+"\n", a...)
		}
	}

	// 阶段 A: 乱序全量插入
	for _, idx := range rng.Perm(int(c.keySpace)) {
		v := uint64(idx) + 1
		nr, err := c.insert(root, v, h)
		if err != nil {
			mark("%s 乱序插入 %d 出错: %v", c.title, v, err)
			continue
		}
		root = nr
		alive[v] = true
	}
	report(opErr == 0, fmt.Sprintf("%s 阶段A: 乱序全量插入 %d 个键", c.title, c.keySpace))

	// 阶段 B: 以删除为主的随机增删, 迫使不断合并/借位/收缩
	for r := 0; r < c.rounds; r++ {
		for b := 0; b < c.batch; b++ {
			v := uint64(rng.Int63n(int64(c.keySpace))) + 1
			if alive[v] {
				nr, err := c.remove(root, v, h)
				if err != nil {
					mark("%s 第%d轮 删除 %d 出错: %v", c.title, r, v, err)
					continue
				}
				root = nr
				delete(alive, v)
				deadSet[v] = true
			} else if rng.Intn(10) < 3 {
				nr, err := c.insert(root, v, h)
				if err != nil {
					mark("%s 第%d轮 插入 %d 出错: %v", c.title, r, v, err)
					continue
				}
				root = nr
				alive[v] = true
				delete(deadSet, v)
			}
		}
		// 每轮: 结构校验
		issues := validateTree(h, root, c.api.secondary)
		if len(issues) > 0 {
			mark("%s 第%d轮 结构问题 %d 条, 例: %s", c.title, r, len(issues), issues[0])
		}
		// 每轮: 随机抽样查找
		for s := 0; s < 300; s++ {
			v := uint64(rng.Int63n(int64(c.keySpace))) + 1
			_, found := c.api.search(root, c.api.keyOf(v), h)
			if alive[v] && !found {
				mark("%s 第%d轮: 存活键 %d 查不到", c.title, r, v)
			}
			if !alive[v] && found {
				mark("%s 第%d轮: 已删/未插入的键 %d 被查到", c.title, r, v)
			}
		}
	}
	report(opErr == 0, fmt.Sprintf("%s 阶段B: 随机增删 %d 轮, 累计异常 %d", c.title, c.rounds, opErr))

	aliveList := make([]uint64, 0, len(alive))
	for v := range alive {
		aliveList = append(aliveList, v)
	}
	deadList := make([]uint64, 0, len(deadSet))
	for v := range deadSet {
		deadList = append(deadList, v)
	}
	verify(c.api, "压测结束: 全量校验", root, h, aliveList, deadList)
}

func testStress() {
	{
		h := newMemStore().handle()
		runStress(h, stressConfig{
			title:    "主键树",
			api:      apiPrimary(),
			keySpace: 3000,
			rounds:   120,
			batch:    200,
			seed:     20260910,
			insert: func(root uint32, v uint64, hh page.HandleDb) (uint32, error) {
				nr, _, _, err := btree.BTreePKInsert(root, u64key(v), uint32(v), hh)
				return nr, err
			},
			remove: func(root uint32, v uint64, hh page.HandleDb) (uint32, error) {
				nr, _, err := btree.BTreePKDelete(root, u64key(v), hh)
				return nr, err
			},
		})
	}
	{
		// 大键 -> 每节点仅 31 条, 3 层树, 能充分触发分裂/合并/借位
		h := newMemStore().handle()
		api := apiSecondary()
		api.keyOf = bigKey
		api.entryHex = func(v uint64) string { return fmt.Sprintf("%x", bigEntry(v, v)) }
		runStress(h, stressConfig{
			title:    "二级树(大键,3层)",
			api:      api,
			keySpace: 2000,
			rounds:   120,
			batch:    120,
			seed:     20260911,
			insert: func(root uint32, v uint64, hh page.HandleDb) (uint32, error) {
				return btree.SBTInsert(root, bigEntry(v, v), hh)
			},
			remove: func(root uint32, v uint64, hh page.HandleDb) (uint32, error) {
				return btree.SBTDelete(root, bigKey(v), hh)
			},
		})
	}
	{
		// 超长键(keyLen=1000) -> 每节点仅约 8 条, 树高 5+,
		// 随机增删时每轮都做结构校验, 覆盖深层分裂/合并/借位与根收缩。
		const kl = 1000
		h := newMemStore().handle()
		api := apiSecondary()
		api.keyOf = func(v uint64) []byte { return mkKey(kl, v) }
		api.entryHex = func(v uint64) string { return fmt.Sprintf("%x", mkEntry(kl, v, v)) }
		runStress(h, stressConfig{
			title:    "二级树(深,keyLen=1000)",
			api:      api,
			keySpace: 2500,
			rounds:   80,
			batch:    150,
			seed:     20260912,
			insert: func(root uint32, v uint64, hh page.HandleDb) (uint32, error) {
				return btree.SBTInsert(root, mkEntry(kl, v, v), hh)
			},
			remove: func(root uint32, v uint64, hh page.HandleDb) (uint32, error) {
				return btree.SBTDelete(root, mkKey(kl, v), hh)
			},
		})
	}
}

// =============================================================================
// 工具
// =============================================================================

func u64key(v uint64) []byte {
	b := make([]byte, 8)
	binary.BigEndian.PutUint64(b, v)
	return b
}

func pkEntryHex(k uint64, dp uint32) string {
	b := make([]byte, 12)
	binary.BigEndian.PutUint64(b, k)
	binary.BigEndian.PutUint32(b[8:], dp)
	return fmt.Sprintf("%x", b)
}

func sbtEntryHex(k uint64, pkid uint64) string {
	return fmt.Sprintf("%x", sbtEntryBytes(k, pkid))
}

func sbtEntryBytes(k uint64, pkid uint64) []byte {
	b := make([]byte, 16)
	binary.BigEndian.PutUint64(b, k)
	binary.BigEndian.PutUint64(b[8:], pkid)
	return b
}

func main() {
	// 降低填充因子, 在数据量较小的情况下也能触发分裂/合并
	page.BTreeFillFactor = 50

	fmt.Println("============================================================")
	fmt.Println("  TsDB2 B+ 树独立验证 (内存页存储, 不涉及真实 DB 文件)")
	fmt.Printf("  页大小=%d  页头=%d  填充因子=%d%%  分裂阈值=%d\n",
		page.IndexPageSize, page.IndexHeadSize, page.BTreeFillFactor,
		page.IndexPageSize*page.BTreeFillFactor/100)
	fmt.Println("============================================================")

	testPrimary()
	testSecondary()
	testSecondaryBigKey()
	testSBTBuildFromSorted()
	testDeepTree()
	testPrimaryBorrowRight()
	testSecondaryBorrowRight()
	testStress()

	fmt.Println("\n============================================================")
	if totalFail == 0 {
		fmt.Println("  结论: 全部检查通过 (未发现 B+ 树问题)")
	} else {
		fmt.Printf("  结论: 共发现 %d 项检查失败, B+ 树存在问题\n", totalFail)
	}
	fmt.Println("============================================================")
}