B+Tree

B+Tree是从B-Tree演化而来的，是一种为磁盘或其他直接存取辅助设备而设计的一种平衡查找树。

B+树

B+Tree和B-Tree的区别

• B+树数据存储在叶子节点，非叶节点仅存储索引不存储数据。
• B+树叶子节点相邻节点之间通过双向指针进行连接。

为什么MySQL使用B+树实现索引

MySQL数据库有这样的场景：

• 等值查询；
• 范围查询；

对比其他的数据结构：Hash、B树。

• Hash能够提供O(1)时间复杂度的等值查询，但是无法支持范围查找和排序，适合Redis的底层Key存储，但是不适合用来实现InnoDB索引。
• B树在非叶子节点也存储数据，会导致非叶子节点中能保存的指针数量变少，进而增加树的高度，导致I/O操作变多，查询性能降低。
• B树在做范围查询时，访问效率特别低。
• B+树在叶子节点通过指针组织成双向链表，可以高效的做范围查询，时间复杂度O(logn)。