B+树

B 树和 B+树的区别

• 存储不同：B+树存储有冗余。
  • B+树的所有数据分布在叶子节点上，非叶子节点只存储索引值。
  • B树的所有数据分布在非叶子或叶子节点上。
• 结构不同：B+树叶子结点通过指针连接成链表，能够实现范围查询；B树则没有
• 查询方式不同：B+树需要根据非叶子节点来定位到叶子结点上的完整数据；B树则不需要，查到直接返回，没查到就一直遍历。

B+树相比B树优点

• 非叶子节点相比B树，相同大小的前提下，数据量更多，一次IO可以更大概率的筛选到目标数据所在位置，IO次数要比B树少。
• 叶子节点构成了有序链表，范围查询更有优势

Mysql的innodb是以页为存储单位的，每个B+树的叶子节点都是一个页的大小的倍数，默认一页的大小是 16K