B+树

1. 简介

B+树是B树的变体，常用于数据库和操作系统的文件系统中

• MySQL数据库的索引就是基于B+树实现的

B+树的特点

• 分为内部节点(非叶子)、叶子节点2种节点

  内部节点只存储key，不存储具体数据

  叶子节点存储key和具体数据

• 所有的叶子节点形成一条有序链表

• m阶B+树非根节点的元素数量X

  m/2 <= x <= m
  

2. MySQL

为了减少IO操作数量，一般把一个节点的大小设计成最小读写单位的大小

• MySQL的存储引擎InnoDB的最小读写单位是16K

相对于B树，B+树的优势是

• 每个节点存储的key数量更多，树的高度更低
• 所有的具体数据都存在叶子节点上，每次查询都要查到叶子节点，查询速度比较稳定
• 所有的叶子节点构成一个有序链表，做区间查询时更方便