详细的描述了MySQL中的索引的结构。

介绍

索引（index）是帮助MySQL高效获取数据的数据结构（有序）。在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

优缺点

优势	劣势
提高数据检索的效率，降低数据库的IO成本	索引列也会占用空间
通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。	索引大大提高了查询效率，同时却也降低更新表的速度，如对表进行INSERT、UPDATE、DELETE时,效率降低。

但是：

目前磁盘很便宜，无所谓占用空间

目前业务查询 SELECT 频次很高，INSERT、UPDATE、DELETE等操作频次较少

综上，使用索引是非常有必要的

结构

分类

索引结构	说明
B+Tree索引	最常见的索引类型，大部分引擎都支持B+树索引
Hash索引	底层数据结构是用哈希表实现的，只有精确匹配索引列的查询才有效不支持范围查询
R-tree（空间索引）	空间索引是MylSAM引擎的一个特殊索引类型，主要用于地理空间数据类型，使用较少
Full-text（全文索引）	是一种通过建立倒排索引,快速匹配文档的方式。类似于Lucene，Solr，ES

引擎对于索引的支持情况

索引	InnoDB	MyISAM	Memory
B+tree索引	支持	支持	支持
Hash索引	不支持	不支持	支持
R-tree索引	不支持	支持	不支持
Full-text	5.6版本之后支持	支持	不支持

具体结构可以点击以下链接进入页面进行模拟操作：

点击此处链接进行模拟数据结构

点击此处链接进行模拟B+树结构

具体数据结构在《数据结构》课中都有详细描述。

B树结构样例如下：

B+树结构样例如下：

B树与B+树的区别：

1.所有的数据都会出现在叶子节点

2.叶子节点形成了一个单向链表

3.MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能。即MySQL将单向链表优化为双向链表。

Hash索引

Hash通过hash算法将键值对映射到指定位置，出现碰撞（hash冲突）可以通过链表解决。

Hash索引特点
1.Hash索引只能用于对等比较(=，in)，不支持范围查询(between，>，<，….
2.无法利用索引完成排序操作
3.查询效率高，通常只需要一次检索就可以了，效率通常要高于B+tree索引

在MySQL中，支持hash索引的是Memory引擎，而InnoDB中具有自适应hash功能，hash索引是存储引擎根据B+Tree索引在指定条件下自动构建的。

为什么InnoDB存储引擎选择使用B+tree索引结构?

1.相对于二叉树，层级更少，搜索效率高;
2.对于B-tree，无论是叶子节点还是非叶子节点，都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的高度，导致性能降低;
3.相对Hash索引，B+tree支持范围匹配及排序操作;

索引分类

分类	含义	特点	关键字
主键索引	针对表中主键创建的索引	默认自动创建，只能有一个	PRIMARY
唯一索引	避免数据列重复	可以多个	UNIQUE
常规索引	快速查询	可以多个	-
全文索引	查找文本关键词，并非比较索引值	可以多个	FULLTEXT

InnoDB索引分类

分类	含义	特点
聚集索引(Clustered Index)	数据与索引放在一起，叶子节点保存了一行的数据	必须存在，且只有一个
二级索引(Secondary Index)	数据与索引分开存储，叶子节点存储对应主键	可以多个

聚集索引选取规则：
1.如果存在主键，主键索引就是聚集索引。
2.如果不存在主键，将使用第一含唯一（UNIQUE）索引作为聚集索引。
3.如果表没有主键，或没有合适的唯一索引，则InnoDB会自动生成一个rowid作为隐藏的聚集索引。

回表查询：

在二级索引中查询到主键，在聚集索引中根据主键查询到想要的数据

InnoDB主键索引的B+树高度为多高呢？

假设:
一行数据大小为1k，一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间，主键即使为bigint，占用字节数为8。
高度为2:
n 8 + (n + 1) 6 = 16 1024，算出n约为1170
1171 16=18736
高度为3:
1171 1171 16 = 21939856