Mysql底层数据结构为什么选择B+树

索引底层采用什么数据结构，为什么使用B+树而不是其他数据结构：

（1）如果采用二叉树：使用递增字段作为索引时，二叉树会退化成链表，查找效率太低

（2）如果采用红黑树，虽然插入新元素的过程中会自我平衡，调整位置，但是红叉树终究还是二叉树，树的高度还是太高了，I/O操作太多，多路树B树和B+树具有更低的层高。

（3）如果采用哈希表：单次查询虽然哈希表确实快，但是范围查询，比如：select * from table1 where id

（4）

1.B树的非叶子节点和叶子节点之间没有重复,B+树的非叶子节点和叶子节点之间有重复，也就是B+树有冗余节点

2.B树的非叶子节点和叶子节点都既存储索引key，又存储数据data，B+树的非叶子节点只存储索引，不存储数据，叶子节点才是既存储索引，又存储数据

3.B树的叶子节点不会存储相邻节点在磁盘中的位置，B+树的叶子节点会存储相邻节点在磁盘中的位置，所以B+树支持范围查询

4.B树不用查到叶子节点就可能查到数据，B+树必须一路查到叶子节点才能查到数据