TsDB2/DB/core/index/btree/primary.go

package btree

import (
	"TsDB2/DB/core/index/datapage"
	"TsDB2/DB/core/page"
	"encoding/binary"
	"errors"
	"fmt"
	"unsafe"
)

// btNode B+ 鏍戣妭鐐?(raw bytes + page.IndexHead 鎸囬拡, 鏃?IndexPage 瀵硅薄)
type btNode struct {
	buf     []byte          // 瀹屾暣椤电紦鍐插尯
	info    *page.IndexHead // 鎸囧悜 buf 澶撮儴鐨?page.IndexHead 鎸囬拡
	entries []byte          // buf[page.IndexHeadSize:] 鏉＄洰鍖哄煙
}

func (n *btNode) isLeaf() bool   { return n.info.IsLeaf == 1 }
func (n *btNode) pageID() uint32 { return n.info.Hdr.PageID }

// btPathEntry 璁板綍 B+ 鏍?descent 璺緞
type btPathEntry struct {
	nodePID  uint32
	childIdx int
}

// btSplitThreshold 璁＄畻鍒嗚闃堝€?
func btSplitThreshold() int {
	ff := page.BTreeFillFactor
	if ff < 50 {
		ff = 50
	}
	if ff > 100 {
		ff = 100
	}
	return int(page.IndexPageSize) * ff / 100
}

// ======================== 鑺傜偣 I/O ========================

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

func btSave(handle page.HandleDb, n *btNode) {
	_ = handle.SavePage(n.info.Hdr.PageID, n.buf)
}

func btNew(handle page.HandleDb, isLeaf bool, entryLen int) *btNode {
	pid := handle.NewPage()
	buf := make([]byte, page.IndexPageSize)
	info := (*page.IndexHead)(unsafe.Pointer(&buf[0]))
	info.Hdr.Type = page.IndexDataIndex
	info.Hdr.PageID = pid
	info.Hdr.UseSize = uint32(page.IndexHeadSize)
	info.IndexType = page.IndexTypePrimary
	info.EntryLen = uint16(entryLen)
	info.Count = 0
	if isLeaf {
		info.IsLeaf = 1
	}
	return &btNode{buf: buf, info: info, entries: buf[page.IndexHeadSize:]}
}

// ======================== 鏉＄洰鎿嶄綔 ========================

func btEntry(n *btNode, i int) []byte {
	el := int(n.info.EntryLen)
	return n.entries[i*el : (i+1)*el]
}

func btKey(e []byte) []byte       { return e[:len(e)-4] }
func btPID(e []byte) uint32       { return binary.BigEndian.Uint32(e[len(e)-4:]) }
func btSetPID(e []byte, p uint32) { binary.BigEndian.PutUint32(e[len(e)-4:], p) }

func btCmp(a, b []byte) int {
	ml := len(a)
	if len(b) < ml {
		ml = len(b)
	}
	for i := 0; i < ml; i++ {
		if a[i] < b[i] {
			return -1
		}
		if a[i] > b[i] {
			return 1
		}
	}
	if len(a) < len(b) {
		return -1
	}
	if len(a) > len(b) {
		return 1
	}
	return 0
}

func btRoute(n *btNode, key []byte) uint32 {
	cnt := int(n.info.Count)
	// 二分查找: 找最后一个 entry.key <= key 的位置 (与二级 B+ 树统一 <= 约定)
	left, right := 0, cnt-1
	result := 0
	for left <= right {
		mid := (left + right) / 2
		if btCmp(btKey(btEntry(n, mid)), key) <= 0 {
			result = mid
			left = mid + 1 // 继续向右找
		} else {
			right = mid - 1
		}
	}
	return btPID(btEntry(n, result))
}

// maxLeafEntries 单个叶节点最大条目数
func maxLeafEntries(entryLen int) int {
	threshold := btSplitThreshold()
	available := threshold - page.IndexHeadSize
	if available <= 0 {
		return 1
	}
	return available / entryLen
}

// BuildFromSorted 从已排序的叶条目批量构建 B+ 树 (自底向上)
// leafEntries: 每个条目 = [key(8B) + dpID(4B BE)], 已按 key 升序排列
// 返回新树根 pageID
//
// 内存优化: 避免逐行 B+ 树搜索 (每次 btLoad 16KB), 改为顺序创建所有节点
func BuildFromSorted(leafEntries [][]byte, handle page.HandleDb) uint32 {
	if len(leafEntries) == 0 {
		return 0
	}

	el := 12 // entry len: 8 key + 4 pid
	maxPerLeaf := maxLeafEntries(el)

	// ---- 构建叶节点层 ----
	type childInfo struct {
		pid      uint32
		firstKey []byte // 该子树第一个 key (用于 > 路由)
	}

	var children []childInfo
	var prevLeafPID uint32

	// 将条目分组到叶节点 (带链表链接)
	for i := 0; i < len(leafEntries); {
		end := i + maxPerLeaf
		if end > len(leafEntries) {
			end = len(leafEntries)
		}
		leaf := btNew(handle, true, el)
		for j := i; j < end; j++ {
			src := leafEntries[j]
			dst := btEntry(leaf, int(leaf.info.Count))
			copy(dst, src)
			leaf.info.Count++
			leaf.info.Hdr.UseSize += uint32(el)
		}
		// 设置叶节点链表链接
		leaf.info.Hdr.PrePage = prevLeafPID
		if prevLeafPID != 0 {
			// 更新前一个叶节点的 NextPage
			// 注意: 前一个叶节点已经保存, 需要重新加载并更新
			// 但我们可以在保存前就设置好 NextPage
		}
		btSave(handle, leaf)
		// 更新前一个叶节点的 NextPage 指向当前叶
		if prevLeafPID != 0 {
			prevLeaf := btLoad(handle, prevLeafPID)
			if prevLeaf != nil {
				prevLeaf.info.Hdr.NextPage = leaf.pageID()
				btSave(handle, prevLeaf)
			}
		}
		prevLeafPID = leaf.pageID()
		children = append(children, childInfo{
			pid:      leaf.pageID(),
			firstKey: leafEntries[i][:8],
		})
		i = end
	}

	if len(children) == 1 {
		return children[0].pid
	}

	// ---- 自底向上构建内部节点 ----
	// 路由约定 (btRoute): 找最后一个 entry.key <= searchKey
	// 内部节点条目: entry[i] = (child[i].firstKey, child[i].pid)
	// 即 entry[i].key = 该子树最左叶的第一个 key
	intEl := 12
	maxPerInt := maxLeafEntries(intEl)

	for len(children) > 1 {
		var parents []childInfo
		for i := 0; i < len(children); {
			end := i + maxPerInt
			if end > len(children) {
				end = len(children)
			}
			node := btNew(handle, false, intEl)
			for j := i; j < end; j++ {
				e := make([]byte, intEl)
				// 分隔键 = 该 child 的第一个 key
				copy(e[:intEl-4], children[j].firstKey)
				btSetPID(e, children[j].pid)
				dst := btEntry(node, int(node.info.Count))
				copy(dst, e)
				node.info.Count++
				node.info.Hdr.UseSize += uint32(intEl)
			}
			btSave(handle, node)
			parents = append(parents, childInfo{
				pid:      node.pageID(),
				firstKey: children[i].firstKey,
			})
			i = end
		}
		children = parents
	}

	return children[0].pid
}

func btChildIdx(n *btNode, key []byte) int {
	el := int(n.info.EntryLen)
	cnt := int(n.info.Count)
	// 二分查找: 找最后一个 entry.key <= key 的位置 (与二级 B+ 树统一 <= 约定)
	left, right := 0, cnt-1
	result := 0
	for left <= right {
		mid := (left + right) / 2
		if btCmp(btEntry(n, mid)[:el-4], key) <= 0 {
			result = mid
			left = mid + 1 // 继续向右找
		} else {
			right = mid - 1
		}
	}
	return result
}

func btInsEntry(n *btNode, entry []byte, pos int) {
	el := int(n.info.EntryLen)
	cnt := int(n.info.Count)
	for i := cnt; i > pos; i-- {
		copy(btEntry(n, i), btEntry(n, i-1))
	}
	copy(btEntry(n, pos), entry)
	n.info.Count++
	n.info.Hdr.UseSize += uint32(el)
}

func btRmEntry(n *btNode, pos int) {
	el := int(n.info.EntryLen)
	cnt := int(n.info.Count)
	for i := pos; i < cnt-1; i++ {
		copy(btEntry(n, i), btEntry(n, i+1))
	}
	n.info.Count--
	n.info.Hdr.UseSize -= uint32(el)
}

func btLeafFind(n *btNode, key []byte) (int, bool) {
	el := int(n.info.EntryLen)
	cnt := int(n.info.Count)
	for i := 0; i < cnt; i++ {
		if btCmp(btEntry(n, i)[:el-4], key) == 0 {
			return i, true
		}
	}
	return 0, false
}

func btLeafPos(n *btNode, key []byte) int {
	el := int(n.info.EntryLen)
	cnt := int(n.info.Count)
	for i := 0; i < cnt; i++ {
		if btCmp(btEntry(n, i)[:el-4], key) >= 0 {
			return i
		}
	}
	return cnt
}

// btLeftmostKey 获取子树最左叶的第一个 key（用于 promoKey）
func btLeftmostKey(handle page.HandleDb, nodePID uint32) []byte {
	cur := nodePID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return nil
		}
		if n.isLeaf() {
			if n.info.Count == 0 {
				return nil
			}
			e := btEntry(n, 0)
			key := make([]byte, len(btKey(e)))
			copy(key, btKey(e))
			return key
		}
		// 非叶节点，继续向左下遍历
		cur = btPID(btEntry(n, 0))
	}
}

// ======================== B+ 鏍戞悳绱?========================

func BTreePKSearch(rootPID uint32, key []byte, handle page.HandleDb) (uint32, bool) {
	if rootPID == 0 {
		return 0, false
	}
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return 0, false
		}
		if n.isLeaf() {
			pos, ok := btLeafFind(n, key)
			if !ok {
				return 0, false
			}
			return btPID(btEntry(n, pos)), true
		}
		cur = btRoute(n, key)
	}
}

// ======================== B+ 鏍戝彾瀛愯妭鐐瑰畾浣?========================

// BTreeFindLeftmostLeaf 浠庢牴鑺傜偣璺敱鍒版渶宸﹀彾鑺傜偣锛岃繑鍥炲彾鑺傜偣 pageID
func BTreeFindLeftmostLeaf(rootPID uint32, handle page.HandleDb) uint32 {
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return 0
		}
		if n.isLeaf() {
			return n.info.Hdr.PageID
		}
		cur = btPID(btEntry(n, 0))
	}
}

// BTreeFindRightmostLeaf 浠庢牴鑺傜偣璺敱鍒版渶鍙冲彾鑺傜偣锛岃繑鍥炲彾鑺傜偣 pageID
func BTreeFindRightmostLeaf(rootPID uint32, handle page.HandleDb) uint32 {
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return 0
		}
		if n.isLeaf() {
			return n.info.Hdr.PageID
		}
		cur = btPID(btEntry(n, int(n.info.Count)-1))
	}
}

// ======================== B+ 鏍戣寖鍥存壂鎻?========================

// BTreePKRangeScan 涓婚敭 B+ 鏍戣寖鍥存壂鎻?
func BTreePKRangeScan(rootPID uint32, handle page.HandleDb,
	startKey, endKey []byte, startInc, endInc bool, reverse bool,
	callback func(row []byte) bool) error {
	if rootPID == 0 {
		return nil
	}
	if !reverse {
		// 正向: 路由到 startKey 所在叶, 沿 NextPage 遍历
		cur := rootPID
		for {
			n := btLoad(handle, cur)
			if n == nil {
				return nil
			}
			if n.isLeaf() {
				break
			}
			cur = btRoute(n, startKey)
		}
		for cur != 0 {
			n := btLoad(handle, cur)
			if n == nil {
				break
			}
			for i := 0; i < int(n.info.Count); i++ {
				entry := btEntry(n, i)
				key := btKey(entry)
				if endKey != nil {
					cmp := btCmp(key, endKey)
					if cmp > 0 || (cmp == 0 && !endInc) {
						return nil
					}
				}
				if startKey != nil {
					cmp := btCmp(key, startKey)
					if cmp < 0 || (cmp == 0 && !startInc) {
						continue
					}
				}
				dpID := btPID(entry)
				dp, err := datapage.Load(handle, dpID)
				if err != nil {
					continue
				}
				// 每个 B+ 树条目精确匹配一行 (FindRowByIndexKey 按索引键过滤)
				if row, ok := dp.FindRowByIndexKey(key, 9); ok {
					if !callback(row) {
						return nil
					}
				}
			}
			cur = n.info.Hdr.NextPage
		}
	} else {
		// 反向: 路由到 endKey 所在叶(或最右叶), 沿 PrePage 遍历
		cur := rootPID
		if endKey != nil {
			for {
				n := btLoad(handle, cur)
				if n == nil {
					return nil
				}
				if n.isLeaf() {
					break
				}
				cur = btRoute(n, endKey)
			}
		} else {
			cur = BTreeFindRightmostLeaf(rootPID, handle)
		}
		for cur != 0 {
			n := btLoad(handle, cur)
			if n == nil {
				break
			}
			for i := int(n.info.Count) - 1; i >= 0; i-- {
				entry := btEntry(n, i)
				key := btKey(entry)
				if startKey != nil {
					cmp := btCmp(key, startKey)
					if cmp < 0 || (cmp == 0 && !startInc) {
						return nil
					}
				}
				if endKey != nil {
					cmp := btCmp(key, endKey)
					if cmp > 0 || (cmp == 0 && !endInc) {
						continue
					}
				}
				dpID := btPID(entry)
				dp, err := datapage.Load(handle, dpID)
				if err != nil {
					continue
				}
				if row, ok := dp.FindRowByIndexKey(key, 9); ok {
					if !callback(row) {
						return nil
					}
				}
			}
			cur = n.info.Hdr.PrePage
		}
	}
	return nil
}

// ======================== B+ 鏍戞彃鍏?========================

func BTreePKInsert(rootPID uint32, key []byte, dpID uint32, handle page.HandleDb) (uint32, uint32, bool, error) {
	if rootPID == 0 {
		el := 12
		leaf := btNew(handle, true, el)
		e := make([]byte, el)
		copy(e[:8], key)
		btSetPID(e, dpID)
		btInsEntry(leaf, e, 0)
		btSave(handle, leaf)
		return leaf.pageID(), 0, false, nil
	}
	var path []btPathEntry
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return rootPID, 0, false, errors.New("load failed")
		}
		if n.isLeaf() {
			pos, found := btLeafFind(n, key)
			if found {
				return rootPID, btPID(btEntry(n, pos)), true, nil
			}
			el := 12
			ne := make([]byte, el)
			copy(ne[:8], key)
			btSetPID(ne, dpID)
			ip := btLeafPos(n, key)
			if int(n.info.Hdr.UseSize)+el <= btSplitThreshold() {
				btInsEntry(n, ne, ip)
				btSave(handle, n)
				return rootPID, 0, false, nil
			}
			cnt := int(n.info.Count)
			total := cnt + 1
			all := make([]byte, total*el)
			if ip > 0 {
				copy(all, n.entries[:ip*el])
			}
			copy(all[ip*el:], ne)
			if cnt > ip {
				copy(all[(ip+1)*el:], n.entries[ip*el:cnt*el])
			}
			mid := total / 2
			// <= 路由约定: 左子叶所有 key 必须严格小于右子叶第一个 key (promoKey)
			// 如果 all[mid-1].key == all[mid].key, 右移 mid 直到分隔
			for mid < total-1 {
				if btCmp(all[(mid-1)*el:mid*el-4], all[mid*el:(mid+1)*el-4]) < 0 {
					break
				}
				mid++
			}
			rl := btNew(handle, true, el)
			rc := total - mid
			copy(rl.entries, all[mid*el:total*el])
			rl.info.Count = uint32(rc)
			rl.info.Hdr.UseSize = uint32(page.IndexHeadSize) + uint32(rc*el)
			rl.info.Hdr.NextPage = n.info.Hdr.NextPage
			rl.info.Hdr.PrePage = n.info.Hdr.PageID
			n.info.Hdr.NextPage = rl.info.Hdr.PageID
			copy(n.entries, all[:mid*el])
			n.info.Count = uint32(mid)
			n.info.Hdr.UseSize = uint32(page.IndexHeadSize) + uint32(mid*el)
			btSave(handle, n)
			btSave(handle, rl)
			if rl.info.Hdr.NextPage != 0 {
				nl := btLoad(handle, rl.info.Hdr.NextPage)
				if nl != nil {
					nl.info.Hdr.PrePage = rl.info.Hdr.PageID
					btSave(handle, nl)
				}
			}
			// 使用右子树最左叶的第一个 key 作为 promoKey
			pk := btLeftmostKey(handle, rl.info.Hdr.PageID)
			nr, err := btPromote(handle, rootPID, path, n.info.Hdr.PageID, pk, rl.info.Hdr.PageID)
			return nr, 0, false, err
		}
		ci := btChildIdx(n, key)
		cpid := btPID(btEntry(n, ci))
		path = append(path, btPathEntry{nodePID: cur, childIdx: ci})
		cur = cpid
	}
}

func btPromote(handle page.HandleDb, rootPID uint32, path []btPathEntry, leftPID uint32, promoKey []byte, rightPID uint32) (uint32, error) {
	if len(path) == 0 {
		el := 12
		nr := btNew(handle, false, el)
		leftKey := btLeftmostKey(handle, leftPID)
		le := make([]byte, el)
		copy(le[:8], leftKey)
		btSetPID(le, leftPID)
		re := make([]byte, el)
		copy(re[:8], promoKey)
		btSetPID(re, rightPID)
		btInsEntry(nr, le, 0)
		btInsEntry(nr, re, 1)
		btSave(handle, nr)
		return nr.pageID(), nil
	}
	pi := len(path) - 1
	parent := btLoad(handle, path[pi].nodePID)
	if parent == nil {
		return rootPID, errors.New("parent load failed")
	}
	ci := path[pi].childIdx
	el := int(parent.info.EntryLen)
	ok := make([]byte, el-4)
	copy(ok, btKey(btEntry(parent, ci)))
	// 叶子分裂后: 左半部分=原节点(保持 ok), 右半部分=新节点(需要 promoKey)
	// 更新 entry[ci] = (ok, leftPID) — key 不变, 只更新 PID
	btSetPID(btEntry(parent, ci), leftPID)
	// 在排序位置插入 (promoKey, rightPID)
	newPos := int(parent.info.Count)
	for i := ci + 1; i < int(parent.info.Count); i++ {
		if btCmp(btKey(btEntry(parent, i)), promoKey) >= 0 {
			newPos = i
			break
		}
	}
	for i := int(parent.info.Count); i > newPos; i-- {
		copy(btEntry(parent, i), btEntry(parent, i-1))
	}
	ne := make([]byte, el)
	copy(ne[:el-4], promoKey)
	btSetPID(ne, rightPID)
	copy(btEntry(parent, newPos), ne)
	parent.info.Count++
	parent.info.Hdr.UseSize += uint32(el)
	if int(parent.info.Hdr.UseSize)+el <= btSplitThreshold() {
		btSave(handle, parent)
		return rootPID, nil
	}
	cnt := int(parent.info.Count)
	mid := cnt / 2
	rn := btNew(handle, false, el)
	rc := cnt - mid
	copy(rn.entries, parent.entries[mid*el:cnt*el])
	rn.info.Count = uint32(rc)
	rn.info.Hdr.UseSize = uint32(page.IndexHeadSize) + uint32(rc*el)
	parent.info.Count = uint32(mid)
	parent.info.Hdr.UseSize = uint32(page.IndexHeadSize) + uint32(mid*el)
	btSave(handle, parent)
	btSave(handle, rn)
	pk2 := make([]byte, 8)
	copy(pk2, btKey(btEntry(rn, 0)))
	return btPromote(handle, rootPID, path[:pi], parent.info.Hdr.PageID, pk2, rn.info.Hdr.PageID)
}

// ======================== B+ 鏍戝垹闄?(閫掑綊 + 鍚堝苟/鍊熶綅) ========================

func BTreePKDelete(rootPID uint32, key []byte, handle page.HandleDb) (uint32, uint32, error) {
	if rootPID == 0 {
		return 0, 0, page.ErrNotFound
	}
	delDP, err := btDeleteRec(rootPID, key, nil, handle)
	if err != nil {
		return rootPID, delDP, err
	}
	n := btLoad(handle, rootPID)
	if n != nil && n.info.Count == 0 {
		if !n.isLeaf() && n.info.Count == 0 {
			return rootPID, delDP, nil
		}
	}
	return rootPID, delDP, nil
}

func btDeleteRec(nodePID uint32, key []byte, path []btPathEntry, handle page.HandleDb) (uint32, error) {
	node := btLoad(handle, nodePID)
	if node == nil {
		return nodePID, page.ErrNotFound
	}
	el := int(node.info.EntryLen)
	if node.isLeaf() {
		pos, ok := btLeafFind(node, key)
		if !ok {
			return nodePID, page.ErrNotFound
		}
		delDP := btPID(btEntry(node, pos))
		btRmEntry(node, pos)
		if node.info.Count == 0 && len(path) == 0 {
			btSave(handle, node)
			return delDP, nil
		}
		btSave(handle, node)
		if len(path) > 0 && node.info.Count > 0 {
			btTryMerge(handle, path, node, el)
		}
		return delDP, nil
	}
	ci := btChildIdx(node, key)
	childPID := btPID(btEntry(node, ci))
	newPath := make([]btPathEntry, len(path)+1)
	copy(newPath, path)
	newPath[len(path)] = btPathEntry{nodePID: nodePID, childIdx: ci}
	delDP, err := btDeleteRec(childPID, key, newPath, handle)
	if err != nil {
		return delDP, err
	}
	node = btLoad(handle, nodePID)
	if node == nil {
		return delDP, errors.New("reload node failed")
	}
	if node.info.Count > 0 {
		ci2 := btChildIdx(node, key)
		if ci2 >= 0 && ci2 < int(node.info.Count) {
			cpID := btPID(btEntry(node, ci2))
			child := btLoad(handle, cpID)
			if child != nil && child.info.Count == 0 {
				btHandleUnderflow(node, ci2, el, handle)
			}
		}
	}
	if node.info.Count == 0 {
		return delDP, nil
	}
	btSave(handle, node)
	return delDP, nil
}

func btTryMerge(handle page.HandleDb, path []btPathEntry, node *btNode, el int) {
	if len(path) == 0 {
		return
	}
	pp := path[len(path)-1].nodePID
	parent := btLoad(handle, pp)
	if parent == nil {
		return
	}
	ci := -1
	for i := 0; i < int(parent.info.Count); i++ {
		if btPID(btEntry(parent, i)) == node.info.Hdr.PageID {
			ci = i
			break
		}
	}
	if ci < 0 {
		return
	}
	if ci > 0 {
		leftPID := btPID(btEntry(parent, ci-1))
		left := btLoad(handle, leftPID)
		if left != nil && left.isLeaf() {
			combined := uint32(page.IndexHeadSize) + (left.info.Count+node.info.Count)*uint32(el)
			threshold := uint32(btSplitThreshold())
			if combined <= threshold {
				rc := int(node.info.Count)
				copy(left.entries[int(left.info.Count)*el:], node.entries[:rc*el])
				left.info.Count += node.info.Count
				left.info.Hdr.UseSize += uint32(rc * el)
				left.info.Hdr.NextPage = node.info.Hdr.NextPage
				btSave(handle, left)
				if left.info.Hdr.NextPage != 0 {
					nl := btLoad(handle, left.info.Hdr.NextPage)
					if nl != nil {
						nl.info.Hdr.PrePage = leftPID
						btSave(handle, nl)
					}
				}
				btRmEntry(parent, ci)
				btSave(handle, parent)
				return
			}
		}
	}
	if ci < int(parent.info.Count)-1 {
		rightPID := btPID(btEntry(parent, ci+1))
		right := btLoad(handle, rightPID)
		if right != nil && right.isLeaf() {
			combined := uint32(page.IndexHeadSize) + (node.info.Count+right.info.Count)*uint32(el)
			threshold := uint32(btSplitThreshold())
			if combined <= threshold {
				rc := int(right.info.Count)
				copy(node.entries[int(node.info.Count)*el:], right.entries[:rc*el])
				node.info.Count += right.info.Count
				node.info.Hdr.UseSize += uint32(rc * el)
				node.info.Hdr.NextPage = right.info.Hdr.NextPage
				btSave(handle, node)
				if node.info.Hdr.NextPage != 0 {
					nl := btLoad(handle, node.info.Hdr.NextPage)
					if nl != nil {
						nl.info.Hdr.PrePage = node.info.Hdr.PageID
						btSave(handle, nl)
					}
				}
				btRmEntry(parent, ci+1)
				btSave(handle, parent)
				return
			}
		}
	}
}

func btHandleUnderflow(parent *btNode, childIdx int, el int, handle page.HandleDb) {
	childPID := btPID(btEntry(parent, childIdx))
	child := btLoad(handle, childPID)
	if child == nil {
		return
	}
	if childIdx > 0 {
		leftPID := btPID(btEntry(parent, childIdx-1))
		leftSib := btLoad(handle, leftPID)
		if leftSib != nil && int(leftSib.info.Count) > 1 {
			borrowed := make([]byte, el)
			copy(borrowed, btEntry(leftSib, int(leftSib.info.Count)-1))
			btRmEntry(leftSib, int(leftSib.info.Count)-1)
			btInsEntry(child, borrowed, 0)
			copy(btEntry(parent, childIdx)[:8], btKey(btEntry(child, 0)))
			btSave(handle, leftSib)
			btSave(handle, child)
			btSave(handle, parent)
			return
		}
	}
	if childIdx < int(parent.info.Count)-1 {
		rightPID := btPID(btEntry(parent, childIdx+1))
		rightSib := btLoad(handle, rightPID)
		if rightSib != nil && int(rightSib.info.Count) > 1 {
			borrowed := make([]byte, el)
			copy(borrowed, btEntry(rightSib, 0))
			btRmEntry(rightSib, 0)
			btInsEntry(child, borrowed, int(child.info.Count))
			copy(btEntry(parent, childIdx)[:8], btKey(btEntry(rightSib, 0)))
			btSave(handle, rightSib)
			btSave(handle, child)
			btSave(handle, parent)
			return
		}
	}
	if childIdx > 0 {
		btMergeChildren(handle, parent, childIdx-1, el)
	} else if childIdx < int(parent.info.Count)-1 {
		btMergeChildren(handle, parent, childIdx, el)
	}
}

func btMergeChildren(handle page.HandleDb, parent *btNode, sepIdx int, el int) {
	leftPID := btPID(btEntry(parent, sepIdx))
	rightPID := btPID(btEntry(parent, sepIdx+1))
	left := btLoad(handle, leftPID)
	right := btLoad(handle, rightPID)
	if left == nil || right == nil {
		return
	}
	if left.isLeaf() {
		rc := int(right.info.Count)
		copy(left.entries[int(left.info.Count)*el:], right.entries[:rc*el])
		left.info.Count += right.info.Count
		left.info.Hdr.UseSize += uint32(rc * el)
		left.info.Hdr.NextPage = right.info.Hdr.NextPage
	} else {
		sepEntry := make([]byte, el)
		copy(sepEntry, btEntry(parent, sepIdx))
		rc := int(right.info.Count)
		off := int(left.info.Count) * el
		copy(left.entries[off:], sepEntry)
		off += el
		copy(left.entries[off:], right.entries[:rc*el])
		left.info.Count += 1 + right.info.Count
		left.info.Hdr.UseSize += uint32((1 + rc) * el)
	}
	btSave(handle, left)
	if left.isLeaf() && left.info.Hdr.NextPage != 0 {
		nl := btLoad(handle, left.info.Hdr.NextPage)
		if nl != nil {
			nl.info.Hdr.PrePage = leftPID
			btSave(handle, nl)
		}
	}
	btRmEntry(parent, sepIdx+1)
	btSetPID(btEntry(parent, sepIdx), leftPID)
	btSave(handle, parent)
}

// ======================== DataPage 鎿嶄綔 ========================

// FindSpaceInLeaf 鍦ㄥ彾鑺傜偣涓壘鍒版湁绌洪棿鐨?DataPage
func FindSpaceInLeaf(handle page.HandleDb, rootPID uint32, rowSize uint32, key []byte) (uint32, bool) {
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return 0, false
		}
		if n.isLeaf() {
			pos := btLeafPos(n, key)
			if pos >= int(n.info.Count) {
				pos = int(n.info.Count) - 1
			}
			if pos < 0 {
				return 0, false
			}
			dpID := btPID(btEntry(n, pos))
			dp, err := datapage.Load(handle, dpID)
			if err == nil && !dp.IsFull(rowSize) {
				return dpID, true
			}
			if n.info.Hdr.PrePage != 0 {
				prevN := btLoad(handle, n.info.Hdr.PrePage)
				if prevN != nil && prevN.isLeaf() && prevN.info.Count > 0 {
					prevDPID := btPID(btEntry(prevN, int(prevN.info.Count)-1))
					prevDP, err := datapage.Load(handle, prevDPID)
					if err == nil && !prevDP.IsFull(rowSize) {
						return prevDPID, true
					}
				}
			}
			if n.info.Hdr.NextPage != 0 {
				nextN := btLoad(handle, n.info.Hdr.NextPage)
				if nextN != nil && nextN.isLeaf() && nextN.info.Count > 0 {
					nextDPID := btPID(btEntry(nextN, 0))
					nextDP, err := datapage.Load(handle, nextDPID)
					if err == nil && !nextDP.IsFull(rowSize) {
						return nextDPID, true
					}
				}
			}
			return 0, false
		}
		cur = btRoute(n, key)
	}
}

// FindLastLeafDP 路由到目标叶子, 检查最后一个条目的 DataPage 是否有空间
// 只检查路由目标叶子, 不跨叶子查找 (保证 B+ 树不变性)
func FindLastLeafDP(handle page.HandleDb, rootPID uint32, rowSize uint32, key []byte) (uint32, bool) {
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return 0, false
		}
		if n.isLeaf() {
			if n.info.Count == 0 {
				return 0, false
			}
			// 检查最后一个条目的 DataPage
			lastIdx := int(n.info.Count) - 1
			dpID := btPID(btEntry(n, lastIdx))
			dp, err := datapage.Load(handle, dpID)
			if err == nil && !dp.IsFull(rowSize) {
				return dpID, true
			}
			return 0, false
		}
		cur = btRoute(n, key)
	}
}

// GetDataPageIDs 返回所有 DataPage ID (去重, 用于全表扫描)
func GetDataPageIDs(handle page.HandleDb, rootPID uint32) []uint32 {
	if rootPID == 0 {
		return nil
	}
	var dpIDs []uint32
	seen := make(map[uint32]bool)
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			break
		}
		if n.isLeaf() {
			break
		}
		cur = btPID(btEntry(n, 0))
	}
	for cur != 0 {
		n := btLoad(handle, cur)
		if n == nil {
			break
		}
		for i := 0; i < int(n.info.Count); i++ {
			dpID := btPID(btEntry(n, i))
			if !seen[dpID] {
				seen[dpID] = true
				dpIDs = append(dpIDs, dpID)
			}
		}
		cur = n.info.Hdr.NextPage
	}
	return dpIDs
}

// ScanAllLeavesForPK 扫描所有叶子查找 pkID(LE)
func ScanAllLeavesForPK(rootPID uint32, handle page.HandleDb, pkKeyBE []byte) ([]byte, bool) {
	if rootPID == 0 {
		return nil, false
	}
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return nil, false
		}
		if n.isLeaf() {
			break
		}
		cur = btPID(btEntry(n, 0))
	}
	for cur != 0 {
		n := btLoad(handle, cur)
		if n == nil {
			break
		}
		for i := 0; i < int(n.info.Count); i++ {
			dpID := btPID(btEntry(n, i))
			dp, err := datapage.Load(handle, dpID)
			if err == nil {
				if rowData, ok := dp.FindRowByPK(pkKeyBE); ok {
					return rowData, true
				}
			}
		}
		cur = n.info.Hdr.NextPage
	}
	return nil, false
}

// ScanAndDelete 扫描所有叶子按 indexKey 删除
func ScanAndDelete(rootPID uint32, handle page.HandleDb, indexKey, pkKeyBE []byte) error {
	if rootPID == 0 {
		return page.ErrNotFound
	}
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return page.ErrNotFound
		}
		if n.isLeaf() {
			break
		}
		cur = btPID(btEntry(n, 0))
	}
	for cur != 0 {
		n := btLoad(handle, cur)
		if n == nil {
			break
		}
		for i := 0; i < int(n.info.Count); i++ {
			dpID := btPID(btEntry(n, i))
			dp, err := datapage.Load(handle, dpID)
			if err == nil {
				deleted := false
				if dp.DeleteByIndexKey(indexKey, 8) {
					deleted = true
				} else if dp.DeleteByPK(pkKeyBE) {
					deleted = true
				}
				if deleted {
					if dp.AllDeleted() {
						newRoot, _, err := BTreePKDelete(rootPID, indexKey, handle)
						if err != nil {
							return err
						}
						_ = newRoot
					} else {
						dp.Save()
					}
					return nil
				}
			}
		}
		cur = n.info.Hdr.NextPage
	}
	return page.ErrNotFound
}

// ScanAndDeleteByPK 扫描所有叶子按 pkID 删除
func ScanAndDeleteByPK(rootPID uint32, handle page.HandleDb, pkKeyBE []byte) error {
	if rootPID == 0 {
		return page.ErrNotFound
	}
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return page.ErrNotFound
		}
		if n.isLeaf() {
			break
		}
		cur = btPID(btEntry(n, 0))
	}
	for cur != 0 {
		n := btLoad(handle, cur)
		if n == nil {
			break
		}
		for i := 0; i < int(n.info.Count); i++ {
			dpID := btPID(btEntry(n, i))
			dp, err := datapage.Load(handle, dpID)
			if err == nil {
				if dp.DeleteByPK(pkKeyBE) {
					if dp.AllDeleted() {
						newRoot, _, err := BTreePKDelete(rootPID, pkKeyBE, handle)
						if err != nil {
							return err
						}
						_ = newRoot
					} else {
						dp.Save()
					}
					return nil
				}
			}
		}
		cur = n.info.Hdr.NextPage
	}
	return page.ErrNotFound
}

// ScanAndUpdate 扫描所有叶子按 pkID 更新
func ScanAndUpdate(rootPID uint32, handle page.HandleDb, pkKeyBE, storeRowData []byte) error {
	if rootPID == 0 {
		return page.ErrNotFound
	}
	cur := rootPID
	for {
		n := btLoad(handle, cur)
		if n == nil {
			return page.ErrNotFound
		}
		if n.isLeaf() {
			break
		}
		cur = btPID(btEntry(n, 0))
	}
	for cur != 0 {
		n := btLoad(handle, cur)
		if n == nil {
			break
		}
		for i := 0; i < int(n.info.Count); i++ {
			dpID := btPID(btEntry(n, i))
			dp, err := datapage.Load(handle, dpID)
			if err == nil {
				if err := dp.UpdateByPK(pkKeyBE, storeRowData); err == nil {
					dp.Save()
					return nil
				}
			}
		}
		cur = n.info.Hdr.NextPage
	}
	return page.ErrNotFound
}

// BTreeValidate 检查 B+ 树内部节点条目排序
func BTreeValidate(handle page.HandleDb, rootPID uint32) []string {
	var issues []string
	if rootPID == 0 {
		return issues
	}
	var check func(pid uint32, depth int)
	check = func(pid uint32, depth int) {
		n := btLoad(handle, pid)
		if n == nil {
			issues = append(issues, fmt.Sprintf("d=%d: load fail pid=%d", depth, pid))
			return
		}
		cnt := int(n.info.Count)
		if n.isLeaf() {
			for i := 1; i < cnt; i++ {
				pk := btKey(btEntry(n, i-1))
				ck := btKey(btEntry(n, i))
				if btCmp(pk, ck) >= 0 {
					issues = append(issues, fmt.Sprintf("d=%d leaf=%d: unsorted [%d]>=[%d]", depth, pid, i-1, i))
				}
			}
			return
		}
		for i := 1; i < cnt; i++ {
			pk := btKey(btEntry(n, i-1))
			ck := btKey(btEntry(n, i))
			if btCmp(pk, ck) > 0 {
				issues = append(issues, fmt.Sprintf("d=%d int=%d: UNSORTED [%d]>[%d]", depth, pid, i-1, i))
			}
		}
		for i := 0; i < cnt; i++ {
			childPID := btPID(btEntry(n, i))
			check(childPID, depth+1)
		}
	}
	check(rootPID, 0)
	return issues
}

// BTreeTraceSearch 搜索并打印路由路径
func BTreeTraceSearch(rootPID uint32, key []byte, handle page.HandleDb) {
	if rootPID == 0 {
		fmt.Println("Tree is empty")
		return
	}
	cur := rootPID
	depth := 0
	for {
		n := btLoad(handle, cur)
		if n == nil {
			fmt.Printf("  d=%d: LOAD FAIL pid=%d\n", depth, cur)
			return
		}
		el := int(n.info.EntryLen)
		cnt := int(n.info.Count)
		if n.isLeaf() {
			fk := uint64(0)
			lk := uint64(0)
			if cnt > 0 {
				fk = binary.BigEndian.Uint64(btKey(btEntry(n, 0)))
				lk = binary.BigEndian.Uint64(btKey(btEntry(n, cnt-1)))
			}
			pos, found := btLeafFind(n, key)
			fmt.Printf("  d=%d LEAF pid=%d cnt=%d first=%d last=%d pos=%d found=%v\n",
				depth, cur, cnt, fk, lk, pos, found)
			return
		}
		fmt.Printf("  d=%d INT pid=%d cnt=%d [", depth, cur, cnt)
		for i := 0; i < cnt; i++ {
			k := binary.BigEndian.Uint64(btEntry(n, i)[:el-4])
			p := btPID(btEntry(n, i))
			if i > 0 {
				fmt.Printf(", ")
			}
			if i < 3 || i >= cnt-2 {
				fmt.Printf("(k=%d,p=%d)", k, p)
			} else if i == 3 {
				fmt.Printf("...")
			}
		}
		fmt.Printf("]\n")
		ci := btChildIdx(n, key)
		fmt.Printf("    btChildIdx(%d) = %d\n", binary.BigEndian.Uint64(key), ci)
		cur = btPID(btEntry(n, ci))
		depth++
	}
}

// CollectAllPageIDs 收集 B+ 树所有页 ID (包括内部节点和叶子节点)
// 用于 DropTable 时释放所有 B+ 树占用的页
func CollectAllPageIDs(handle page.HandleDb, rootPID uint32) []uint32 {
	if rootPID == 0 {
		return nil
	}
	var pages []uint32
	// BFS 遍历所有节点
	queue := []uint32{rootPID}
	for len(queue) > 0 {
		pid := queue[0]
		queue = queue[1:]
		pages = append(pages, pid)
		n := btLoad(handle, pid)
		if n == nil {
			continue
		}
		if !n.isLeaf() {
			// 内部节点: 收集所有子节点
			for i := 0; i < int(n.info.Count); i++ {
				childPID := btPID(btEntry(n, i))
				if childPID != 0 {
					queue = append(queue, childPID)
				}
			}
		}
	}
	return pages
}