MySQL--索引底层数据结构详解

索引是什么？

索引是帮助MySQL高效获取数据的排好序的数据结构，因此可知索引是数据结构。
概念很抽象，但是类比生活中的例子就很容易理解，比如一本厚厚的书，我们想取找某一小节，我们可以根据目录去快速找到对应的章节，其实这个目录就可以叫这本书的索引，而数的目录又分为大章节小章节，如果倒着看是不是很像一棵树呢？

常见树的数据结构及特点：

二叉树：
二叉树是每个节点最多有两个子节点的树结构，通常有左子树和右子树，左右子树是有顺序的，左子树的值要小于父节点，右子树的值要大于父节点。

二叉树示意图：

极端情况下二插树可能没有左右子树，比如一组递增的数据，最终就形成了一个链表。

极端情况下二叉树示意图：

为了避免这种情况的发生，产生了平衡二叉树。

平衡二叉树（AVL Tree）：
平衡二叉树是一种特殊的二叉树，除了满足二叉树的特征之外，它还要求左右两颗子树的高度差的绝对值不能超过1，且左右两棵子树都是平衡二叉树。
平衡二叉树解决了极端情况下退化为链表的问题，但是平衡二叉树满足了每个节点最多两个子节点的特点，如果数据量比较大的情况下，二叉树的高度会非常，查询的时候会多次进行磁盘IO，查询的性能会比较差，因此诞生了B-Tree。

同样数据，使用平衡二叉树演示：

很明显同样数据AVL树没有出现二叉树的情况。

B-Tree的特点：

• 度（Degree）：节点存储数据的个数，B-Tree允许一个节点存储多个数据。
• 每个节点可以有M个子节点。
• 叶子节点具有相同的深度。
• 节点的数据从左到右顺序排列。
• 叶子节点指针为空。

同样数据，B-Tree演示：

B+Tree的特点：

• 非叶子节点不存储数据，只存储索引key，可以增加度（key占用的空间远小于data占用的空间）。
• 叶子节点存储了全部数据，且增加了顺序访问指针，提高了区间访问性能，支持范围查询。

InnoDB中存储引擎页大小是16KB，一个节点就是一页，而一个Long类型的主键id占用8个字节，故叶子节点如果只存储索引的话，一个节点就能存储大量的索引key，这样就大大减少了节点个数，同时也节省了存储空间。

同样数据，B+Tree演示：

很直观的看到，B+Tree叶子节点多了指针，且叶子节点有全部数据，数据从左到右依次增大。

好用的数据演示网站：

Hash索引的特点：

• hash索引不支持范围查找。
• hash存在哈希冲突问题。
• hash索引经过一次查询就可以定位到数据，查询效率比B+Tree高。

Full-text全文索引的特点：

仅可用于 MyISAM 存储引擎，用于检索文本信息的， 针对较大的数据，生成全文索引很耗时间及空间，在MySQL中一般不常用。

聚集索引和非聚集索引？

聚集索引和非聚集索引是按物理存储结构来划分的一个概念。

• 聚集索引也叫聚族索引，是以主键创建的索引，聚集索引叶子节点存储的是数据，一个表中只存在一个聚集索引，且只存在于InnoDB引擎中。
• 非聚集索引也叫辅助索引，索引和数据不在一起，非聚集索引叶子节点存储的是索引对应数据行的主键，通过索引行找到主键后，根据主键去找对应的数据。

MySQL InnoDB、MyISAM、Memory存储引擎对索引数据结构的支持：

数据类型	InnoDB	MyISAM	Memory
B+Tree	支持	支持	支持
Hash	不支持（用户无法手动创建Hash索引）	不支持	支持
Full-text	5.6版本后支持	支持	不支持

如有不正确的地方请各位指出纠正。