TsDB2/DB/core/index_rebuild.go

package core

import (
	"bytes"
	"encoding/binary"
	"fmt"

	"git.ycl.pub/yl32940/TsDB2/DB/core/index"
	"git.ycl.pub/yl32940/TsDB2/DB/core/index/btree"
	"git.ycl.pub/yl32940/TsDB2/DB/core/page"
)

// buildSecondaryFromEntries 用"已按 secKey 排好序"的条目 [secKey + pkID(8B BE)] 构建一个二级索引。
//
// 页布局决定做法, 不能一律批量建树:
//   - B+ 树二级索引 (含 IndexTypeCompose —— ComposeChainHandler 底层即 SBT): 批量建树;
//   - 哈希二级索引: 页不是 B+ 节点, 必须走 handler.Insert
//     (详见 rebuildSecondaryViaHandler 注释)。
//
// 调用方负责 m.EntryPage 的旧根归还 (整表重建走 releaseOldTree); 新建索引回填时
// 旧根本就是 0, 无需归还。
func buildSecondaryFromEntries(handle page.HandleDb, m *IndexMeta, entries [][]byte) error {
	if isBTreePageIndex(m) {
		m.EntryPage = btree.SBTBuildFromSorted(entries, handle)
		return nil
	}
	return rebuildSecondaryViaHandler(handle, m, entries)
}

// releaseIndexPages 归还一棵已彻底不可达的索引结构 (内部节点 + 叶子 / 桶链) 的全部页。
//
// 这是 releaseOldTree 与 DROP INDEX 的共用实现: 两者都换掉/摘掉了根, 旧结构从此没人读,
// 必须把它的页还给空闲链, 否则文件只涨不缩。遍历方式按索引类型的页布局分流:
//   - B+ 树 (主键 / 二级 / 旧 Str): CollectAllPageIDs 按内部条目 BFS 下降;
//   - 哈希: 桶页 next 已统一到 PageHdr.NextPage, 一条链只登记一次, 提交后一次
//     FreeChain 还链 (O(1));
//   - 复合 / 时序: 扁平条目链, 走处理器自己的 PageCollector。
//
// 一定要在"新结构就位 (已 saveMeta)"之后调用, 否则归还的页会被 NewPage 立刻分给新结构,
// 而这里还要按旧结构遍历 —— 会取到半截结构。
func releaseIndexPages(table *Table, itype page.IndexType, rootPID uint32) {
	if rootPID == 0 {
		return
	}
	if isBTreePageType(itype) {
		for _, pid := range btree.CollectAllPageIDs(table.handle, rootPID) {
			table.deferFreePage(pid)
		}
		return
	}
	h, ok := index.Compose.GetHandler(itype)
	if !ok {
		return
	}
	// 整链延迟回收优先: 哈希索引的桶页 next 已统一到 PageHdr.NextPage, 且每条桶链的
	// (head, tail, count) 就持久化在目录槽里 —— 一条链只登记一次, 提交后一次 FreeChain
	// 还链 (O(1)), 不必逐页查询、逐页改写空闲链。
	if cc, ok := h.(index.ChainCollector); ok && table.handle.DeferFreeChain != nil {
		for _, ch := range cc.CollectChains(table.handle, rootPID) {
			if ch.Head == 0 || ch.Count == 0 {
				continue
			}
			if ch.Head == ch.Tail {
				table.deferFreePage(ch.Head) // 单页链 (例如元数据页)
				continue
			}
			table.handle.DeferFreeChain(ch.Head, ch.Tail, ch.Count)
		}
		return
	}
	pc, ok := h.(index.PageCollector)
	if !ok {
		return
	}
	for _, pid := range pc.CollectPageIDs(table.handle, rootPID) {
		table.deferFreePage(pid)
	}
}

// isBTreePageIndex 判断该索引的页是不是 B+ 节点页 (page.IndexHead + 内部条目结构)。
//
// 只有 B+ 树页能用 CollectAllPageIDs 安全遍历, 也只有它们能用
// BuildFromSorted / SBTBuildFromSorted 批量构建。其余类型的页布局都不同:
//   - HashHandler: 元数据页 + 目录页链 + 桶页链。按 IndexHead 解析会把
//     BucketID / NextPage 当成 EntryLen / IsLeaf, 遍历出一串垃圾页 ID, 进而把
//     不属于本索引的页归还掉 —— 那是数据损坏, 不是泄漏;
//   - TimeIndexHandler: 扁平条目链 + TimeDataPage, 没有内部节点。
//
// IndexTypeCompose 的处理器 (ComposeChainHandler) 底层就是 SBT 二级 B+ 树
// (Insert/Search/RangeScan 全部委托 btree.SBT*), 页即 B+ 节点页 —— 与 BTree 同列。
//
// 注意时序索引 (IndexTypeTime): 它同样是行存储索引, 但页是扁平链而非 B+ 树。
// 因此这里**不能**用 indexStoresRows 来判断 —— 那样会把时序索引当成 B+ 树, 既在
// 回收时漏收页链上的其余页, 又让重建拿 B+ 树页去覆盖它 (见 bulkRebuildSupported)。
func isBTreePageIndex(m *IndexMeta) bool {
	if m == nil {
		return false
	}
	return isBTreePageType(m.IndexType)
}

// isBTreePageType 仅按类型判断页布局是否为 B+ 节点页 (与 isBTreePageIndex 同源)。
func isBTreePageType(t page.IndexType) bool {
	switch t {
	case page.IndexTypePrimary, page.IndexTypeBTree:
		return true
	case page.IndexTypeStr:
		// IndexTypeStr 是 IndexTypeBTree 的旧值, 页格式相同。
		return true
	case page.IndexTypeCompose:
		// ComposeChainHandler 底层即 SBT 二级 B+ 树, 页格式与 BTree 相同。
		return true
	default:
		return false
	}
}

// bulkRebuildSupported 校验一个索引能否参与批量删除的"重建"流程。
//
// 批量删除统一采用「存活行写进全新 DataPage + 索引从零重建」, 因此要求每种索引
// 都具备从零批量构建的能力。页布局决定做法:
//   - 主键 B+ 树 / B+ 树二级索引 (含 IndexTypeCompose, 底层即 SBT): BuildFromSorted 批量建树
//   - 哈希二级索引: 清空根后走 handler.Insert 逐条重建
//
// 时序索引 (IndexTypeTime) 是"扁平链 + TimeDataPage": 行本身就住在按时间分段的
// TimeDataPage 里, 重建必须重新分段, 与本流程的模型完全不同 —— 明确拒绝。
// 旧实现没有这个校验, 会默默用 btree.BuildFromSorted 把时序索引整体改写成 B+ 树
// (元数据仍写着 IndexTypeTime, 页却成了 B+ 节点), 之后 Search / RangeScan 全部错乱。
func bulkRebuildSupported(m *IndexMeta) error {
	if m == nil {
		return nil
	}
	name := string(bytes.TrimRight(m.IndexName[:], "\x00"))
	if indexStoresRows(m) && m.IndexType != page.IndexTypePrimary {
		return fmt.Errorf(
			"批量删除不支持索引 %q (行存储索引类型 %d): 时序索引的行数据按时间分段存放, "+
				"批量重建需要重新分段, 请改用逐行删除", name, m.IndexType)
	}
	switch m.IndexType {
	case page.IndexTypePrimary, page.IndexTypeBTree, page.IndexTypeStr,
		page.IndexTypeCompose, page.IndexTypeHash:
		return nil
	default:
		return fmt.Errorf("批量删除不支持索引 %q 的类型 %d", name, m.IndexType)
	}
}

// rebuildSecondaryViaHandler 用索引自己的 Insert 从零重建哈希二级索引
// (目录 + 桶链 —— 唯一的非 B+ 树二级索引)。
//
// 为什么不能沿用 SBTBuildFromSorted: 它产出的页是 B+ 节点布局, 而哈希索引的页
// 是元数据页 + 目录页链 + 桶页链 —— 元数据仍写着 IndexTypeHash, 页却成了 B+ 树,
// readHashMeta 在 page.IndexHeadSize 处的魔数校验直接失败
// (errHashFormatIncompatible: 等值查找恒为 not found, 插入直接报错), 等于把索引写坏。
//
// 走 handler.Insert 的好处是正确性由正常写入路径背书: 目录扩容 / 桶分裂自动走通。
// 代价是这条路径为 O(n log n), 只影响哈希 —— B+ 树二级索引 (含复合索引) 仍走
// 批量建树, 性能没有回退。哈希不要求 entries 有序, 不受影响。
func rebuildSecondaryViaHandler(handle page.HandleDb, m *IndexMeta, entries [][]byte) error {
	name := string(bytes.TrimRight(m.IndexName[:], "\x00"))
	h, ok := index.Compose.GetHandler(m.IndexType)
	if !ok {
		return fmt.Errorf("重建索引 %q: 类型 %d 没有注册处理器", name, m.IndexType)
	}
	// 从空根开始重建; 旧结构由 releaseOldTree 按 PageCollector 单独归还。
	m.EntryPage = 0
	for _, e := range entries {
		if len(e) < 8 {
			continue
		}
		keyLen := len(e) - 8
		root, err := h.Insert(handle, &m.EntryPage, e[:keyLen],
			binary.BigEndian.Uint64(e[keyLen:]), nil, keyLen)
		if err != nil {
			return fmt.Errorf("重建索引 %q: %w", name, err)
		}
		m.EntryPage = root
	}
	return nil
}

// compareBytes 按字典序比较两个字节切片
func compareBytes(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
}