共计 2784 个字符，预计需要花费 7 分钟才能阅读完成。
一、何为索引？
1、索引是帮助数据库高效获取数据的 排好序 的数据结构。
2、索引存储在文件中。
3、索引建多了会影响增删改效率。
（下面这张图为计算机组成原理内容，每查询一次索引节点，都会进行一次磁盘 IO 读取，即要寻道和旋转）
二、MySQL 索引结构为什么是 B + 树？
MySQL 建索引可使用的数据结构有 B+ 树 和Hash两种，但是 Hash 用得很少，优点是可以快速定位到某一行，缺点是不能解决范围查询问题。
对于如果不需要使用范围查询、只需要精准查询的场景，可以使用 Hash 索引方法，比如查电话号码。
再说说主流的索引方法 B + 树，先说下为什么不用别的树结构，再说为什么用 B + 树。
1、为什么不用二叉树？
如果碰到下面这种单边增长的极端情况，查找节点 4 和顺序查找没区别。（这种特殊情况的二叉树等同于链表，时间复杂度为 O(n)）
2、为什么不用红黑树？
红黑树是一颗平衡二叉树，数据量大的时候，树的深度也很深，如果树的深度有 20 层，而查找的数据在叶子节点，就要进行 20 次 IO 操作，性能低。
3、为什么不用 B 树？
B 树的特点：
- 叶子节点具有相同的深度
- 叶子节点的指针为空
- 叶子节点中的数据 key 从左到右递增排列
其实 B 树就是在横向做了文章，一个节点可以存储更多数据（大节点包含很多小节点），这样相对来说，深度就会变浅。
提问：横向的节点怎么查，比如说查找上图中的节点 77？
从磁盘中把大节点查找出来，把这个大节点加载进内存中，节点 77 实际上是在内存中查找的，在内存中做的是随机访问，速度很快，跟磁盘的寻道和旋转相比的话，基本可以忽略不计。
提问：为什么不可以让 B 树横向的度无限增大，这样不就深度为 1，查找不就更快了？（度的含义：节点的数据存储个数）
本来是想通过一次 IO 操作把一个大节点加载进内存，如果一个大节点的数据量太大的话，则内存和硬盘一次交互没办法交换那么多数据，假设一次只能交换 1 页（4k）的数据（有上限，也有可能是几十页，和计算机硬件有关），意味着 CPU 去硬盘上做一次 IO 操作只能取 1 页的数据，那么当一个大节点的数据量太大时，仍要进行多次 IO 操作。因此，度是有上限的，MySQL 会根据计算机硬件自动进行度的优化，一个大节点通常为 1 页空间。
4、为什么使用 B + 树？（B+ 树是 B 树的变种，索引做了冗余，存了多份，但是没关系，索引只占很小空间，比如下图中的 15 节点）
B+ 树的特点：
- 非叶子节点不存储 data，只存储 key，可以增大度（相比 B 树，B+ 树的深度更浅）
- 叶子节点不存储指针
- 顺序访问指针，提高区间访问的性能（实际上是双向指针）
提问：为什么说 B + 树可以增大度？
因为非叶子节点只存储索引一个值，不存储 data（B 树会存储 data），而大节点大小是确定的，因此节点就可以存储更多的数据，即度可以变得更大。这样既保证度可以达到最大，又保证一个大节点通过一次 IO 操作可以加载进内存。（非叶子节点度更大，深度更浅，只有非叶子节点才影响查找次数，叶子节点是最后一次查找，对总的查找次数是没有影响的，因此把 data 全部移到了叶子节点）
提问：为什么叶子节点之间还需要用指针？（一个大节点的尾节点和下一个大节点的头节点之间的指针连接）
方便范围查询。比如查找上图中 key>18，如果没有指针会非常麻烦，必须从头开始查找，如果有指针，则可以直接遍历 key>18 的叶子节点（链表）。
B+ 树索引的性能分析：
- 一般使用磁盘 I / O 次数评价索引结构的优劣
- 预读：磁盘一般会顺序向后读取一定长度的数据（页的整数倍）放入内存
- 局部性原理：当一个数据被用到时，其附近的数据也通常会立马被使用
- B+ 树的大节点大小设为等于一个页，每次新建大节点直接申请一个页的空间，这能保证一个大节点物理上也存储在一个页里，大节点载入只需一次 IO 操作
- B+ 树的度 d 一般会超过 100，因此高度 h 非常小（一般为 3~5 之间）
三、MySQL 底层是怎么用 B + 树来存储数据的？
MySQL 有两种常见的存储引擎：InnoDB（默认）、MyISAM（用得少，在 MySQL8.0 中被废弃掉了），存储引擎范围是 表级别 的。
1、MyISAM 索引实现（非聚集）
- 索引文件和数据文件是分离的
- 索引结构的叶子节点 value 存储的是文件指针。
.frm 是表结构文件，.MYD 是数据文件（MyISAM Data），.MYI 是索引文件（MyISAM Index）。
MyISAM 主键索引查找流程：先通过.MYI 文件找到对应索引的文件指针，再根据文件指针去.MYD 文件中定位对应的那行数据。
MyISAM 普通索引查找流程：和主键索引查找流程一致。
2、InnoDB 索引实现（聚集）
- 数据文件本身就是索引文件
- 表数据文件本身就是按 B + 树组织的一个索引结构文件
- 聚集索引的叶子节点包含了完整的数据记录
- 表必须有主键，且推荐使用整型的自增主键
- 普通索引结构叶子节点存储的是主键值
.frm 是表结构文件，.ibd 是数据和索引文件（InnoDB Data）
InnoDB 主键索引查找流程：通过.ibd 文件找到对应的索引，索引的 value 即为那行对应的完整数据。
InnoDB 普通索引查找流程：通过.ibd 文件找到对应的索引，索引的 value 即为那行对应的主键的值，再根据主键值去主键索引树中找到对应的行数据。
提问：聚集索引和非聚集索引的区别？
聚集索引：表中那行数据的索引和数据都合并在一起了。
非聚集索引：表中那行数据的索引和数据是分开存储的。
提问：为什么 InnoDB 表必须有主键？
因为整个数据文件本身就是按照 B + 树组织的一个索引文件，所以必须要有主键（建 InnoDB 表时不指定主键，默认会从表字段中选一列作为唯一主键，如果不存在这种字段，则后台默认生成一个长整型主键字段，MyISAM 可以没有）。
提问：为什么推荐使用整型的自增主键？
提高查询性能。如果是使用 UUID 作为主键，第一，UUID 长度很长，会浪费存储空间，第二，UUID 是字符串类型，比较大小要查找 ASCII 码表，查找速度没有整型 int 查找速度快，第三，UUID 是随机生成无序的字符串，当数据插入时，有很大可能会导致节点位置移动，还可能造成很多其他节点位置移动，简单来说就是位置打乱了；如果使用整型的自增主键，新插入的数据都会连续的插入到磁盘的物理空间。
提问：为什么 InnoDB 普通索引结构叶子节点存储的是主键值？（一致性和节省存储空间）
如果普通索引的 value 也存数据，那么当往有主键索引和普通索引的表中插入数据时，索引结构中 key 对应的 value 要存储两份数据，增加维护成本。
单值索引：只有一个索引，如(id)，size=1
联合索引：多个索引合起来作为一个联合索引，如(id,name)，size>1（单值索引是联合索引 size= 1 的特例）
提问：联合索引的底层数据结构长什么样？
先比较 id，如果 id 相等，再比较 name，如果 name 也相等，则再比较 date。（索引最左前缀原理，后面索引优化随笔会讲解）
：
