为什么MySQL采用B+树作索引

能在尽可能少的磁盘的 I/O 操作中完成查询工作；
要能高效地查询某个记录，也要能高效地执行范围查找；

不管平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率。
B+ 树与 B 树差异的点，主要是以下这几点：

叶子节点才会存放实际数据（索引+记录），非叶子节点只会存放索引；
所有索引都会在叶子节点出现，叶子节点之间构成一个有序链表；
非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大（或最小）。
非叶子节点中有多少个子节点，就有多少个索引

Innodb使用的b加树有一些特别的点

B+树叶子节点之间用「双向链表」连接，好处是既能向右遍历也能向左遍历
B+树点节点内容是数据页，数据页里存了用户记录以及各种信息，每个数据页默认大小是16KB

二叉查找树特点

一个节点的左子树所有节点都小于这个节点，右子树所有节点都大于这个节点。当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成一条链表，查找数据的时间复杂度变成了O(n)

自平衡二叉树

二叉查找树基础上增加约束：每个节点左子树和右子树的高度差不能超过1