在树节点中存储子树的元素个数，以支持根据排名查找元素功能。
https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html
The change we introduce for a counted B-tree is simply this: alongside every link to a subtree, we store a count of the number of elements stored in that whole subtree. For example, this is what might happen to the tree shown above.
计数 B 树（Counted B-Trees） 是一种在传统 B 树（B-tree）基础上做了额外“元素计数”增强的变体。它通过在每条子树指针上存储子树所含元素总数，使得我们既能按键值（key）进行查找，也能按“元素所在的序号/位置”来快速地在树中定位元素。它在保持 B 树原有的 O(log N) 查找、插入、删除等性能的同时，还带来以下特点：
-
按序号（index）查找或删除
- 在每个节点里，对子树指针附带一个“该子树包含多少元素”的计数值。
- 当我们想获取“第 i 个”元素时，只需根据子树计数判定要进入哪个子树或返回哪个节点内的元素，从而把按序号查找的复杂度也保持在 O(log N)。
-
在排序树中获取“顺序统计信息”
- 如果该 B 树仍然按键值有序，则我们可以用计数信息来做“第 i 大元素”、中位数、百分位数等“顺序统计”的查找。
- 从而在动态插入、删除的场景中，仍可快速获取这些统计量。
-
作为“无排序”动态数组
- 如果不按键值排序，而是仅用序号（index）来插入和查找，就能把计数 B 树当作“支持高效插入/删除”的结构化数组：
- 插入新元素时指定它应该出现在“第 i 个位置”，树会自动把它放到对应序号处。
- 查找或删除也可以按照给定的序号来进行。
- 如果不按键值排序，而是仅用序号（index）来插入和查找，就能把计数 B 树当作“支持高效插入/删除”的结构化数组：
-
复杂度保持 O(log N)
- 在原有 B 树中插入、删除时，只需维护子树计数的更新（例如分裂节点、合并节点时重新统计两侧子树大小），并不会改变 B 树的时间复杂度。
-
编辑器缓冲区
- 可以将文本的每个字符或行作为元素，按序号存储在计数 B 树中。
- 支持 O(log N) 时间内在任意位置插入、删除，或移动光标到第 i 行等操作。
-
获取顺序统计
- 在数据库或数据分析场景，往往需要在不停变化的数据集中查询中位数、百分位数等顺序统计值。
- 有了计数功能，第 i 大元素的查找仍是 O(log N)。
-
查询规划
- 如果这是一个按键值排序的计数 B 树，可以先快速获取满足某一键条件的记录数量，以决定是否更优先走另一条查询路线，从而优化多条件查询。
-
在每个节点，记录每条子树指针的“子树大小”
- 例如，若某节点有指向 3 个子树
S0, S1, S2，则我们在对应链接旁存储C0, C1, C2表示每个子树里有多少元素。 - 节点自身也可能存放若干元素，与子树穿插存储：比如
(S0) E0 (S1) E1 (S2) ...。
- 例如，若某节点有指向 3 个子树
-
按序号查找
- 给定
i（想找树中的第 i 个元素，假设从 0 开始计），先看根节点：- 若
i < C0，则在第 0 号子树中继续查找； - 若
i == C0，则说明元素就在根节点里对应的第一个元素 E0； - 若
C0 < i < C0 + C1 + 1，则转到第 1 号子树并令i -= (C0 + 1)； - 以此类推。
- 若
- 给定
-
插入与删除
- 保持 B 树原本的分裂、合并等流程不变，只需在节点发生结构变动时，重新计算或更新子树计数。
- 插入时，如果想“按序号”插入到第 i 个位置，可以先通过上面查找逻辑定位到对应叶子位置，再执行插入。
-
时间复杂度
- 计数 B 树的所有操作仍是 O(log N)。
- 维护计数不会显著增加开销，只是节点分裂/合并时更新计数值。
计数 B 树在传统 B 树中增加了对子树大小的记录，使得我们既可以按键值搜索，也可以按元素序号搜索，并在插入/删除时依旧保持 O(log N) 的性能。它可用来实现灵活的编辑器缓冲区、支持顺序统计的有序存储、或纯基于序号的动态数组等多种场景，是对经典 B 树的一种实用增强。