B+树的结构

B+树由内部节点（非叶子节点）和叶子节点组成，所有叶子节点位于同一层，形成平衡结构

• 内部节点：
  • 功能：仅作为索引，存储键值（关键字）和指向子节点的指针，不保存实际数据
  • 指针与键值关系：若有k个键值，则对应k+1个子指针。键值为子节点中的最大值或区间分隔符
• 叶子节点：
  • 功能：存储全部数据或指向数据的指针，并通过链表按顺序连接，便于范围遍历
  • 链表结构：叶子节点间通过指针形成双向或单向有序链表，支持高效的范围查询和全表扫描

2. 阶数与节点容量

B+树的阶数m决定了节点的子节点数量和键值容量，通常与磁盘页大小对齐以优化I/O

• 非根节点：
  • 键值数范围：⌈m/2⌉−1≤k≤m−1⌈m/2⌉−1≤k≤m−1（如3阶B+树，非根节点最多2个键值）
• 根节点：
  • 初始可能仅有一个键值，随着数据插入逐步分裂，最终满足至少2个子节点的条件

3. 关键结构特性

• 数据与索引分离：
  • 内部节点仅存索引键，叶子节点存数据或指针，使得内部节点更紧凑，单个节点可容纳更多键值，降低树高度
• 高度平衡：
  • 所有叶子节点位于同一层级，查询路径长度一致，保证稳定的时间复杂度（O(log⁡n)O(logn)）
• 范围查询优化：
  • 叶子节点的链表结构允许直接遍历相邻节点，避免回溯至根节点，大幅减少范围查询的I/O次数

4. 与B树的区别

B+树在以下方面区别于B树

• 数据存储位置：B树内部节点存数据，B+树仅叶子节点存数据。
• 链表结构：B+树叶子节点通过链表连接，B树无此设计。
• 查询稳定性：B+树查询必须到叶子节点，路径固定；B树可能在内部节点提前终止查询。

5. 实际应用中的优势

• 减少磁盘I/O：更高的节点键值密度降低树高度，减少寻道次数
• 缓存友好：内部节点可全缓存于内存，仅需访问磁盘读取叶子节点
• 适合大规模数据：对数级时间复杂度使其在处理海量数据时仍保持高效

InnoDB一棵B+树可以存放多少行数据?

这个问题的简单回答是：约2千万行。

• 在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是512字节。
• 文件系统中，最小单位是块，一个块大小就是4k;
• InnoDB存储引擎最小储存单元是页，一页大小就是16k。

对于非叶子节点，如果key使用的是bigint，则为8字节，指针在mysql中为6字节，一共是14字节，则16k能存放 16 * 1024 / 14 = 1170 个索引指针。
对于叶子节点，如果一行数据大小为1k，那么一页就能存16条数据；

高度为2的B+树(18720 条数据)
根节点存储索引指针节点，那么它有1170个叶子节点存储数据，每个叶子节点可以存储16条数据，一共 1170 x 16 = 18720 条数据。
而对于高度为3的B+树(21902400 条数据)
就可以存放 1170 x 1170 x 16 = 21902400 条数据（两千多万条数据），也就是对于两千多万条的数据，

为什么索引结构默认使用B+树，而不是B-Tree，Hash哈希，二叉树，红黑树?

简单版回答如下：

• Hash哈希，只适合等值查询，不适合范围查询。
• 一般二叉树，可能会特殊化为一个链表，相当于全表扫描。
• 红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。
• B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。

结构示意图示例（以3阶B+树为例）：

[内部节点: 10, 20] / | \ [叶子: 5→9] → [叶子:10→19] → [叶子:20→25] （链表连接）

说明：内部节点键值为子节点的最大值，叶子节点通过指针顺序连接。

通过以上结构设计，B+树在数据库索引中实现了高效的查找、插入、删除及范围查询操作，成为主流存储引擎（如MySQL InnoDB）的核心数据结构