为什么Mysql用B+树作为索引

首先，能作为索引的数据结构有很多，例如数组、链表、二叉树

数据和索引都是存储在磁盘里的。

我们通过索引来查询数据时，先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存。

要设计一个适合 MySQL 索引的数据结构，至少满足以下要求：

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

数组：

优点：用数组可以实现二分查找，时间复杂度从On降到Ologn

缺点：

• 每次查找都要不断计算中间的位置。
• 但是插入新元素的时候性能太低。（元素之后的所有元素后移一位）

二叉搜索树：

优点：（解决了数组的2个缺点）

• 每次查找只需要作比较即可
• 插入新元素时，可以任意位置插入，不需要将之后元素所有后移一位。

缺点：

• 当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)
• 每访问一次节点，都要与磁盘进行一次IO操作。而树的高度就时访问节点的次数，二叉树的高度太容易高了，所以增加了IO。

自平衡二叉树：

优点：

• 解决了二叉查找树就会退化成了一条链表的问题

缺点：

• 高度问题依旧存在

需要解决高度问题，首先想到将二叉树变为M叉树，由此想到了B树

B树：

优点：

• 解决了高度问题

缺点：

• 但是 B 树的每个节点都包含数据（索引+记录），而用户的记录数据的大小很有可能远远超过了索引数据，这就需要花费更多的磁盘 I/O 操作次数来读到「有用的索引数据」。

• 而且，在我们查询位于底层的某个节点（比如 A 记录）过程中，「非 A 记录节点」里的记录数据会从磁盘加载到内存，但是这些记录数据是没用的，我们只是想读取这些节点的索引数据来做比较查询，而「非 A 记录节点」里的记录数据对我们是没用的，这样不仅增多磁盘 I/O 操作次数，也占用内存资源。

• 如果使用 B 树来做范围查询的话，需要使用中序遍历，这会涉及多个节点的磁盘 I/O  问题，从而导致整体速度下降。

B+树：

优点：

• B+树的非叶子节点可以存放更多的索引，在数据量相同的情况下，B+树会比B树的高度更低。
• B+ 树有许多冗余节点，而B树没有，这就使得B+树的插入和删除效率更高
• B+ 树所有叶子节点间还有一个链表进行连接，可以据此进行范围的查询，不用像B树一样只能遍历查询