MySQL索引采用了B+树数据结构

常见的树相关的数据结构包括：

• 二叉树
• 红黑树
• B树
• B+树

区别：树的高度不同。树的高度越低，性能越高。这是因为每一个节点都是一次I/O

二叉树

有这样一张表

如果不给id字段添加索引，默认进行全表扫描，假设查询id=10的数据，那至少要进行10次磁盘IO。效率低。可以给id字段添加索引，假设该索引使用了二叉树这种数据结构，这个二叉树是这样的（推荐一个数据结构可视化网站Data Structure Visualizations，是旧金山大学（USFCA）的一个网站）：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

如果这个时候要找id=10的数据，需要的IO次数是？4次。效率显著提升了。
但是MySQL并没有直接使用这种普通的二叉树，这种普通二叉树在数据极端的情况下，效率较低。比如下面的数据：

如果给id字段添加索引，并且该索引底层使用了普通二叉树，这棵树会是这样的：

你虽然使用了二叉树，但这更像一个链表。查找效率等同于链表查询O(n)【查找算法的时间复杂度是线性的】。查找效率极低。
因此对于MySQL来说，它并没有选择这种数据结构作为索引。

红黑树（自平衡二叉树）

通过自旋平衡规则进行旋转，子节点会自动分叉为2个分支，从而减少树的高度，当数据有序插入时比二叉树数据检索性能更好。
例如有以下数据

给id字段添加索引，并且该索引使用了红黑树数据结构，那么会是这样：

如果查找id=10的数据，磁盘IO次数为：5次。效率比普通二叉树要高一些。

但是如果数据量庞大，例如500万条数据，也会导致树的高度很高，磁盘IO次数仍然很多，查询效率也会比较低。

因此MySQL并没有使用红黑树这种数据结构作为索引。

B Trees（B树）

B Trees首先是一个自平衡的。
B Trees每个节点下的子节点数量 > 2。
B Trees每个节点中也不是存储单个数据，可以存储多个数据。
B Trees又称为平衡多路查找树。

B Trees分支的数量不是2，是大于2，具体是多少个分支，由阶决定。例如：

• 3阶的B Trees，一个节点下最多有3个子节点，每个节点中最多有2个数据。
• 4阶的B Trees，一个节点下最多有4个子节点，每个节点中最多有3个数据。
• 5阶（5, 4）
• 6阶（6, 5）
• ....
• 16阶（16, 15）【MySQL采用了16阶】

采用B Trees，你会发现相同的数据量，B Tree 树的高度更低。磁盘IO次数更少。
3阶的B Trees：

假设id字段添加了索引，并且采用了B Trees数据结构，查找id=10的数据，只需要3次磁盘IO。
4阶的B Trees：

更加详细的存储是这样的，请看下图：


在B Trees中，每个节点不仅存储了索引值，还存储该索引值对应的数据行。
并且每个节点中的p1 p2 p3是指向下一个节点的指针。

B Trees数据结构存在的缺点是：不适合做区间查找，对于区间查找效率较低。假设要查id在[3~7]之间的，需要查找的是3,4,5,6,7。那么查这每个索引值都需要从头节点开始。
因此MySQL使用了B+ Trees解决了这个问题。

B+ Trees（B+ 树）

B+ Trees 相较于 B Trees改进了哪些？

• B+树将数据都存储在叶子节点中。并且叶子节点之间使用链表连接，这样很适合范围查询。
• B+树的非叶子节点上只有索引值，没有数据，所以非叶子节点可以存储更多的索引值，这样让B+树更矮更胖，提高检索效率。

假设有这样一张表：

B+ Trees方式存储的话如下图所示：

经典面试题：mysql为什么选择B+树作为索引的数据结构，而不是B树？

1. 非叶子节点上可以存储更多的键值，阶数可以更大，更矮更胖，磁盘IO次数少，数据查询效率高。
2. 所有数据都是有序存储在叶子节点上，让范围查找，分组查找效率更高。
3. 数据页之间、数据记录之间采用链表链接，让升序降序更加方便操作。

经典面试题：如果一张表没有主键索引，那还会创建B+树吗？
当一张表没有主键索引时，默认会使用一个隐藏的内置的聚集索引（clustered index）。这个聚集索引是基于表的物理存储顺序构建的，通常是使用B+树来实现的。