B+树非叶页设计规则及存储未出现在叶页数值的合法性问询

1. B+树中非叶页的相关设计规则是什么？ #

非叶页作为B+树的索引路由层，核心设计规则如下：

• 键值有序规则：单页内的所有索引键必须按固定排序规则（通常为升序）连续排列，支持单页内二分查找定位子页指针
• 范围划分规则：对升序排列的非叶页，第i个索引键对应的子树中，所有叶页的键值均小于等于该索引键，且大于第i-1个索引键；非叶页首个子树存储所有小于第一个索引键的键值
• 填充率约束：除根节点外，所有非叶页的已存储索引键数量不得低于页最大容量的1/2，避免树结构频繁失衡
• 路径等长规则：从任意非叶节点到其下属所有叶节点的路径长度完全一致，保证全树查询复杂度稳定为O(log n)
• 边界对齐规则：非叶页的索引键必须准确匹配下属子树的键值范围边界，上层非叶页的索引键可直接从下层节点的范围边界提取

2. B+树的非叶页中存储某一不存在于任何叶页的数值，该情况是否符合B+树的设计规范？ #

完全符合B+树的设计规范。

非叶页的核心作用是做路由范围划分，而非存储实际业务键值，仅需要保证索引键可以正确切分下属子树的键值范围即可，本身不需要存在于叶页中。

举个实际场景示例：假设B+树的两个相邻叶页分别存储键值范围[1,3,5,7]和[9,11,13,15]，上层非叶页的分隔索引键可以设为8，只要保证小于等于8的查询请求路由到第一个叶页、大于8的请求路由到第二个叶页即可，8本身不需要出现在任何叶页中，不会影响任何操作的正确性。
部分数据库实现会选择直接提取右叶子节点的首个键作为分隔键（比如上述场景选9作为分隔键），这只是实现层面的优化选择，并非B+树规范的强制要求。

内容的提问来源于stack exchange，提问作者Dano