yl32940
/
TsDB2


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206
							============================================================
  TsDB2 B+ 树独立验证 (内存页存储, 不涉及真实 DB 文件)
  页大小=16384  页头=32  填充因子=50%  分裂阈值=8192
============================================================

================ 主键 B+ 树 (BTreePKInsert / Search / Delete) ================
  [PASS] 插入 2500 个键

--- 阶段1: 全量插入后 ---
  [info] root=3 叶子数=4 条目数=2500 层数=2 逻辑存活=2500
  [PASS] 查找存活键: 2500/2500 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=2500 逻辑=2500)
  [PASS] 删除偶数键 (1250 个)

--- 阶段2: 删除偶数键后 ---
  [info] root=3 叶子数=2 条目数=1250 层数=2 逻辑存活=1250
  [PASS] 查找存活键: 1250/1250 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/1250
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=1250 逻辑=1250)
  [PASS] 逆序删除剩余 1250 个键

--- 阶段3: 全部删除后 ---
  [info] root=1 叶子数=1 条目数=0 层数=1 逻辑存活=0
  [PASS] 查找存活键: 0/0 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/2500
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=0 逻辑=0)

================ 二级 B+ 树 (SBTInsert / SBTSearch / SBTDelete) ================
  [PASS] 插入 2500 个条目

--- 阶段1: 全量插入后 ---
  [info] root=3 叶子数=9 条目数=2500 层数=2 逻辑存活=2500
  [PASS] 查找存活键: 2500/2500 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=2500 逻辑=2500)
  [PASS] 删除偶数键 (1250 个)

--- 阶段2: 删除偶数键后 ---
  [info] root=3 叶子数=3 条目数=1250 层数=2 逻辑存活=1250
  [PASS] 查找存活键: 1250/1250 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/1250
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=1250 逻辑=1250)
  [PASS] 逆序删除剩余 1250 个键

--- 阶段3: 全部删除后 ---
  [info] root=1 叶子数=1 条目数=0 层数=1 逻辑存活=0
  [PASS] 查找存活键: 0/0 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/2500
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=0 逻辑=0)

============ 二级 B+ 树 (keyLen=248, 强制内部节点分裂 => 3 层) ============
  [PASS] 插入 1500 个大键条目

--- 阶段1: 大键全量插入后(应为 3 层) ---
  [info] root=34 叶子数=93 条目数=1500 层数=3 逻辑存活=1500
  [PASS] 查找存活键: 1500/1500 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=1500 逻辑=1500)

========= 二级 B+ 树: SBTBuildFromSorted 批量建树 ===========

--- SBTBuildFromSorted 小键(2层) n=2000 ---
  [info] root=5 叶子数=4 条目数=2000 层数=2 逻辑存活=2000
  [PASS] 查找存活键: 2000/2000 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=2000 逻辑=2000)

--- SBTBuildFromSorted 大键(3层) n=1500 ---
  [info] root=52 叶子数=49 条目数=1500 层数=3 逻辑存活=1500
  [PASS] 查找存活键: 1500/1500 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=1500 逻辑=1500)

========= 深层树验证 (强制 4 层以上, 验证深度可无限分裂) ==========
  [PASS] keyLen=1000 逐条插入 4000 条
  [PASS] keyLen=1000 插入后树高=6 (要求 >=4: 已突破 3 层)

--- 深层树(keyLen=1000,n=4000) 全量校验 ---
  [info] root=683 叶子数=999 条目数=4000 层数=6 逻辑存活=4000
  [PASS] 查找存活键: 4000/4000 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=4000 逻辑=4000)
  [PASS] keyLen=1000 删除过程中(每500步采样)结构始终保持
  [PASS] keyLen=1000 逆序删除全部 4000 条

--- 深层树(keyLen=1000) 删除全部后 ---
  [info] root=1 叶子数=1 条目数=0 层数=1 逻辑存活=0
  [PASS] 查找存活键: 0/0 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/4000
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=0 逻辑=0)
  [PASS] keyLen=1000 批量建树树高=4 (要求 >=4)

--- 深层批量建树(keyLen=1000,n=4000) ---
  [info] root=572 叶子数=500 条目数=4000 层数=4 逻辑存活=4000
  [PASS] 查找存活键: 4000/4000 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=4000 逻辑=4000)
  [PASS] keyLen=2000 逐条插入 1500 条
  [PASS] keyLen=2000 插入后树高=10 (要求 >=4: 已突破 3 层)

--- 深层树(keyLen=2000,n=1500) 全量校验 ---
  [info] root=1023 叶子数=749 条目数=1500 层数=10 逻辑存活=1500
  [PASS] 查找存活键: 1500/1500 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=1500 逻辑=1500)
  [PASS] keyLen=2000 删除过程中(每187步采样)结构始终保持
  [PASS] keyLen=2000 逆序删除全部 1500 条

--- 深层树(keyLen=2000) 删除全部后 ---
  [info] root=1 叶子数=1 条目数=0 层数=1 逻辑存活=0
  [PASS] 查找存活键: 0/0 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/1500
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=0 逻辑=0)
  [PASS] keyLen=2000 批量建树树高=6 (要求 >=4)

--- 深层批量建树(keyLen=2000,n=1500) ---
  [info] root=502 叶子数=375 条目数=1500 层数=6 逻辑存活=1500
  [PASS] 查找存活键: 1500/1500 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=1500 逻辑=1500)

========= 主键 B+ 树: 定向触发「从右兄弟借位」=========
  [info] 最左叶子 pid=1 含 680 个键
  [PASS] 主键树: 清空最左叶子 (680 个键, 失败 0)

--- 清空最左叶子后 ---
  [info] root=3 叶子数=30 条目数=19320 层数=2 逻辑存活=19320
  [PASS] 查找存活键: 19320/19320 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/680
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=19320 逻辑=19320)

========= 二级 B+ 树(大键,3层): 定向触发「从右兄弟借位」=========
  [info] 最左叶子 pid=1 含 16 个键
  [PASS] 二级树: 清空最左叶子 (16 个键, 失败 0)

--- 清空最左叶子后 ---
  [info] root=34 叶子数=186 条目数=2984 层数=3 逻辑存活=2984
  [PASS] 查找存活键: 2984/2984 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/16
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=2984 逻辑=2984)

--- 随机压测 主键树 (keySpace=3000, 120 轮 x 200 次) ---
  [PASS] 主键树 阶段A: 乱序全量插入 3000 个键
  [PASS] 主键树 阶段B: 随机增删 120 轮, 累计异常 0

--- 压测结束: 全量校验 ---
  [info] root=1 叶子数=1 条目数=675 层数=1 逻辑存活=675
  [PASS] 查找存活键: 675/675 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/2325
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=675 逻辑=675)

--- 随机压测 二级树(大键,3层) (keySpace=2000, 120 轮 x 120 次) ---
  [PASS] 二级树(大键,3层) 阶段A: 乱序全量插入 2000 个键
  [PASS] 二级树(大键,3层) 阶段B: 随机增删 120 轮, 累计异常 0

--- 压测结束: 全量校验 ---
  [info] root=34 叶子数=24 条目数=485 层数=3 逻辑存活=485
  [PASS] 查找存活键: 485/485 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/1515
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=485 逻辑=485)

--- 随机压测 二级树(深,keyLen=1000) (keySpace=2500, 80 轮 x 150 次) ---
  [PASS] 二级树(深,keyLen=1000) 阶段A: 乱序全量插入 2500 个键
  [PASS] 二级树(深,keyLen=1000) 阶段B: 随机增删 80 轮, 累计异常 0

--- 压测结束: 全量校验 ---
  [info] root=261 叶子数=107 条目数=569 层数=5 逻辑存活=569
  [PASS] 查找存活键: 569/569 命中, 缺失 0
  [PASS] 查找值正确性: 值错误 0
  [PASS] 已删除键不应被查到: 幽灵 0/1931
  [PASS] 结构校验: 问题 0 条
  [PASS] 叶子条目集合 == 逻辑存活集合 (叶子=569 逻辑=569)

============================================================
  结论: 全部检查通过 (未发现 B+ 树问题)
============================================================