B树与B+树的结构构建机制及数据库索引实现细节问询

1. 创建索引：非空表与空表的两种场景 #

两种场景都被数据库支持，具体实现细节如下：

• 非空表批量建索引：
  首先会把整张表的**索引键（而非随机生成的索引）**按指定排序规则（默认升序）完成排序，然后按照B树/B+树的节点容量（由阶数决定，比如阶数m的节点最多存储m-1个键），将排序后的键分割为若干组，每组对应一个叶子节点。接着从叶子节点往上逐层构建非叶子节点：每个非叶子节点存储下层节点的分界键，以及指向对应下层节点的指针。当某个节点的键数量超过上限时，触发分裂操作——将节点拆分为两个，把中间键提升到父节点中。
  对于B+树，所有索引键最终都存储在叶子节点层，且叶子节点之间通过指针形成有序链表；非叶子节点仅存储叶子节点的分界键用于路由查询，不存在“复制节点”的操作，而是从叶子层提取分界键构建上层索引。
• 空表增量建索引：
  新增行时使用的是确定的索引键（比如自增主键、用户指定的唯一键等），而非随机索引。初始时根节点为空，插入第一个键直接存入根节点；后续插入键时，先在树中找到对应的叶子节点位置，若节点未达到最大容量，就插入并保持键的有序性；当节点键数量超过上限时，触发分裂：将节点拆分为两个，中间键提升到父节点（如果父节点也满了，就继续向上分裂，直到根节点分裂后生成新的根）。

2. 空表新增时的节点存储规则 #

你提到的“顶层12和30节点存在一起”属于逻辑结构的表现，核心原因是节点容量限制与分裂规则：
B树/B+树的每个节点有固定的容量上限（由数据库设定的页大小和阶数决定，比如InnoDB的页是16KB，对应B+树的阶数约为1000）。当下层节点分裂后，会将分界键向上传递到父节点，只要父节点的键数量还未达到上限，这些分界键就会被存放在同一个父节点中。比如12和30是下层两个节点的分界值，父节点当前还能容纳这两个键，就会将它们放在一起，分别指向对应的下层节点。
空表新增过程中主要是分裂操作，合并仅在删除键导致节点键数量低于下限（比如阶数m的节点至少存储ceil(m/2)-1个键）时才会触发。

3. 节点的实际存储形态 #

示意图展示的是逻辑结构，实际内存/磁盘中节点并非连续存储：
数据库中的B树/B+树节点通常对应一个独立的磁盘页（或内存页），每个页有自己的物理地址，节点之间通过页内部的指针字段（比如父节点指针、子节点指针、兄弟节点指针）建立关联。比如InnoDB的每个B+树节点就是一个16KB的页，页头里存储着指向父页、左兄弟页、右兄弟页的地址，页主体存储索引键和对应的指针。这些页在物理上可能分散在磁盘的不同位置，只是通过逻辑指针形成树状结构。

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