详细的描述了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+ 树的内部节点只用分隔键导航，全部键对应的记录都在叶子。下半图按 InnoDB 的形式画出双向叶链，便于说明范围扫描，不表示实际页容量或磁盘读取次数。
B+树结构样例如下：
说明：图中数字均为示例键值。根节点以 20、40 作为分隔键，通过子指针将查找路由到相应键区间；全部示例记录保存在叶节点中，分隔键对应的记录也在叶层。叶节点内部及节点之间按键有序，相邻叶节点用双向链连接，体现 InnoDB 叶层顺序访问的概念。例如查询 20 ≤ 键 ≤ 48 时，先从根节点定位到包含 20 的叶节点，再沿叶链向右读取至 48。图中的“记录”泛指叶子索引记录：InnoDB 聚集索引的叶子保存行记录，二级索引的叶子包含索引列与对应主键；此图不表示实际物理页中的键排列、页内记录组织或容量。
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