TsDB2/DB/index/btree/primary.go

package btree

import (
	"TsDB2/DB/index/datapage"
	"TsDB2/DB/page"
	"encoding/binary"
	"errors"
	"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) *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 = 12
	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)
	for i := 0; i < cnt; i++ {
		if btCmp(btKey(btEntry(n, i)), key) > 0 {
			return btPID(btEntry(n, i))
		}
	}
	return btPID(btEntry(n, cnt-1))
}

func btChildIdx(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 - 1
}

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, 8) // 主键固定8字节
			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, 8); 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, 8); 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 {
		leaf := btNew(handle, true)
		e := make([]byte, 12)
		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
			}
			ne := make([]byte, 12)
			copy(ne[:8], key)
			btSetPID(ne, dpID)
			ip := btLeafPos(n, key)
			if int(n.info.Hdr.UseSize)+12 <= 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*12)
			if ip > 0 {
				copy(all, n.entries[:ip*12])
			}
			copy(all[ip*12:], ne)
			if cnt > ip {
				copy(all[(ip+1)*12:], n.entries[ip*12:cnt*12])
			}
			mid := total / 2
			rl := btNew(handle, true)
			rc := total - mid
			copy(rl.entries, all[mid*12:total*12])
			rl.info.Count = uint32(rc)
			rl.info.Hdr.UseSize = uint32(page.IndexHeadSize) + uint32(rc*12)
			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*12])
			n.info.Count = uint32(mid)
			n.info.Hdr.UseSize = uint32(page.IndexHeadSize) + uint32(mid*12)
			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 {
		nr := btNew(handle, false)
		le := make([]byte, 12)
		copy(le[:8], promoKey)
		btSetPID(le, leftPID)
		re := make([]byte, 12)
		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
	ok := make([]byte, 8)
	copy(ok, btKey(btEntry(parent, ci)))
	copy(btEntry(parent, ci), promoKey)
	btSetPID(btEntry(parent, ci), leftPID)
	cnt := int(parent.info.Count)
	pos := cnt
	for i := ci + 1; i < cnt; i++ {
		if btCmp(ok, btKey(btEntry(parent, i))) <= 0 {
			pos = i
			break
		}
	}
	el := int(parent.info.EntryLen)
	for i := cnt; i > pos; i-- {
		copy(btEntry(parent, i), btEntry(parent, i-1))
	}
	ne := make([]byte, el)
	copy(ne[:8], ok)
	btSetPID(ne, rightPID)
	copy(btEntry(parent, pos), ne)
	for i := ci + 1; i < pos; i++ {
		copy(btEntry(parent, i)[:8], promoKey)
	}
	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)
	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, rn.entries[:8])
	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)
	}
}

// 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
}