1.1 索引是什么
当一张表有 500 万条数据，在没有索引的 name 字段上执行一个查询
如果 name 字段上面有索引呢？
添加索引：
索引的创建是需要消耗时间的。
有索引的查询和没有索引的查询相比，效率相差几十倍。
索引到底是什么呢？为什么可以对我们的查询产生这么大的影响？创建索引的时候做了什么事情？
1.1.1.索引图解
数据是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。如果没有索引的话，我们要从 500 万行数据里面检索一条数据，只能依次遍历这张表的全部数据（循环调用存储引擎的读取下一行数据的接口），直到找到这条数据。
但是我们有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。
这个很容易理解，就像我们从一本 500 页的书里面去找特定的一小节的内容，肯定不可能从第一页开始翻。
这本书会有专门的目录，它可能只有几页的内容，它是按页码来组织的，可以根据拼音或者偏旁部首来查找，我们只要确定内容对应的页码，就能很快地找到我们想要的 内容。
1.1.2.索引类型
普通（Normal）：也叫非唯一索引，是最普通的索引，没有任何的限制。
唯一（Unique）：唯一索引要求键值不能重复。另外需要注意的是，主键索引是一种特殊的唯一索引，它还多了一个限制条件，要求键值不能为空。主键索引用 primay key创建。
全文（Fulltext）：针对比较大的数据，比如我们存放的是消息内容，有几 KB 的数据的这种情况，如果要解决 like 查询效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如 char、varchar、text。
在 5.6 的版本之后，MyISAM 和 InnoDB 都支持全文索引。但是 MySQL 自带的全文索引功能使用限制还是比较多，建议用其他的搜索引擎方案（比如ElasticSearch）。
我们说索引是一种数据结构，那么它到底应该选择一种什么数据结构，才能实现数据的高效检索呢？
2.1 二分查找
很火的猜数字游戏，猜现在是100以内的几，最后通过不断缩小范围，锁定数字
这个就是二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高
所以可以考虑用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变 index），所以只适合存储静态的数据。
为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。
所以，有没有可以使用二分查找的链表呢？
为了解决这个问题，BST（Binary Search Tree）也就是我们所说的二叉查找树诞生了
2.2 二叉查找树(BST Binary Search Tree)
2.3 平衡二叉树（AVL Tree）（左旋、右旋）
当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。
访问一个节点就要跟磁盘之间发生一次 I/O。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁
盘块），大小是 16K(16384 字节), 那么，一个树的节点就是 16K 的大小。
2.4. 多路平衡查找树（B Tree）（分裂、合并）
一个好玩的
比如 Max Degree（路数）是 3 的时候，我们插入数据 1、2、3，在插入 3 的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有 4 个指针， 子节点会变成 4 路，所以这个时候必须进行分裂（其实就是 B+Tree）。把中间的数据 2提上去，把 1 和 3 变成 2 的子节点。如果删除节点，会有相反的合并的操作。
2.5 B+树 （加强版多路平衡查找树）
InnoDB 中的 B+Tree 这种特点带来的优势：
1：它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
2：扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据）
3： B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
4：排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
5：效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）