深度讲解索引的数据结构：B+树
1.索引介绍
1.1 为什么使用索引
1.2 索引的优缺点
2.从零开始设计索引
2.1没有索引时怎么查询数据
2.2 基于页的目录项的简单索引
2.3 InnoDB索引设计方案
2.3.1 迭代1：目录项的数据页(目录页)
2.3.2 迭代2：多个目录页
2.3.3 迭代3：目录页的目录页
3.索引类型
3.1.聚簇索引
3.2 二级索引
3.3 联合索引
3.4.InnoDB的B+树注意事项
3.4.1 根页面位置万年不动
3.4.2 内节点中目录项记录具有唯一性
3.4.3 一个页面最少要存储两条记录
4.MyISam的索引方案
4.1 不同存储引擎索引的区别
4.2 MyISam索引的原理
4.3 MyISam与InnoDB索引方案的对比
4.4 索引方案与索引优化的关系
5.索引的代价
6.B+树与常见的查找数据结构对比
6.1 Hash结构
6.2 二叉搜索树
6.3 AVL树
6.4 B树
6.6 B+树
6.7 R树
1.索引介绍
1.1 为什么使用索引
索引是存储引擎中一种用于快速找到数据的存储结构，他就像《新华字典》的目录，可以使我们查每个字的速度大大提升。
下面将
结合计算机的存储带大家深入理解索引的优点。下图左边使一个磁盘，在这个磁盘中存放数据是随机的，如果要查找某条数据，需要在整个磁盘空间进行扫描，十分耗时。下图右边(表格部分)改进了这一做法，在磁盘中开辟了一块连续的存储空间，数据也是连续存储，如果我们需要找第六条数据，只需要进行顺序访问，时间复杂度是O(n).
还可以改进吗？当然可以，结合我们熟悉的二分查找算法，我们可以使用二叉搜索树来优化。如下图，只要构造一颗二叉树，让左子树的值比右子树的小即可。同样是要查找之前的第六条数据，也就是89，只需要查找2次就可以了。其时间复杂度为O(log2n)
实际上，MySQL数据库的索引就是建立了一棵B+树(其它存储引擎不一定)，比上面的二叉搜索树更加复杂一点。左图转为右图就与索引的创建过程类似，它的创建有利于减少查找数据时的磁盘I/O次数,提高查找速度。注意，这里提到的磁盘I/O其实是很耗时的。因此它的减少会大大提升我们的时间性能。
1.2 索引的优缺点
(1)优点
减少磁盘I/O,提升数据查找速度(主要原因)
创建数据的唯一约束，会自动创建该数据的唯一索引，保证数据库中每一行数据的唯一性
对有依赖关系的子表与父表进行联合查找时，可以加快表与表连接(通过主键关联)，提升查找速度(后面将讲解)
在建立分组(group by)与排序(order by)时，可以减少减少查询中分组与排序的时间，降低cpu的消耗
(2)缺点
创建与维护索引需要时间，并且随着索引中数据字段的增减，所耗费时间也会增加
索引需要占用磁盘空间进行存储
降低了更新数据表的速度(增、删、改都需要动态的维护索引)
注：在实际的生产中，如果需要批量的删除、增加、修改数据，可以先把索引删除，完成操作后再重新的建立索引。
2.从零开始设计索引
从Mysql5.5之后使用的存储引擎默认为InnoDB，因此我们以InnoDB为例，从0开始设计、迭代索引。
2.1没有索引时怎么查询数据
如果查询一条数据，我们可以使用如下查询语句： select [列名] from [表名] where [过滤条件]
(1)在同一个页进行查询
如果数据量不是很多，可以在一个页存储完(16kb)，查询有两种情况：
- 按照主键查找，因为主键是有序的，可以使用二分法查找，时间复杂度为O(log2n)
- 按照其它列查找，需要遍历单链表(数据库的元素实际上是单链表形式实现逻辑上连续的)，时间复杂度为O(n)
(2)在多个页存储
如果数据多到一个页存储不下了，需要在多个页中进行查询，需要
- 定位到数据所在的页
- 从所在的页中查找记录
因为数据页之间数据没有关联(并不是数据页2的数据的主键就比数据1中存储的数据主键大，数据页之间是相对对立的)，因此需要遍历数据页，然后在每个数据页再对数据进行查找。除了遍历数据页外，我们还需要把这些数据页从物理磁盘加载到内存中，这个过程也是十分消耗时间的。成百上千的页加载、遍历消耗的时间无法忍受，于是索引运势而生。
2.2 基于页的目录项的简单索引
建立一张表
CREATE TABLE index_demo( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY(c1) ) ROW_FORMAT= Compact;
compact是一种记录的存储格式，后面将详细介绍，这里简单介绍如下。
其中record_type表示 记录类型，0表示普通记录，2表示最小记录，3表示最大记录，1暂未使用。
一个基本的数据页模型就长这样。
假设每页可以存储三条记录(实际上远远不止)。在表中插入三条记录。
INSERT INTO index_demo VALUES (1,4,'u'),(3,9,'d'),(5,3,'y');
这样他们就串联成为如下图所示的单链表了。
此时我们再插入一条记录。
INSERT INTO index_demo VALUES (4,4,'a');
由于一个页只能存放三条数据，我们必须分配一个新的页(页28的28是随便写的，实际上应该是页地址)。
上图是不是合理的呢？似乎主键值为不是顺序递增了，我们下面将给主键建立索引。先把主键为5的记录与主键为4的记录交换下位置，这个过程称为记录移动。
在数据记录进行增删改时，我们必须通过记录移动保证记录的主键值始终保持递增排列，这个过程我们称之为页分裂。
在插入许多数据以后，数据存储可能是这样的。
由于数据页的编号并不是连续的，我们如果需要查询一个数据，我们需要依次在各个数据页中进行查找，这样老费劲了。因此，我们可以考虑开辟一个连续存储空间，用于存放一个给所有数据页建立的目录项。如下图，目录项中key为页的首个记录主键值，page_no为页号。
比如我们需要查找一个主键值为20的记录，目录项1的key为1，目录项的key为2，由此可知目录项1所在的page10肯定没有我们的目标记录。同样的道理，目录项2的页28，目录项4的page20都没有我们的记录，我们只需要在目录项3所在的page9使用二分法去查找就可以了。实际上，在对于目录项过滤时同样页可以用二分法，而不用逐个目录项进行比较、判断。
2.3 InnoDB索引设计方案
下面对于2.2中所提到的索引设计方案进行迭代，一步步解密InnoDB索引设计方案。
2.3.1 迭代1：目录项的数据页(目录页)
上面提到，如果目录项在存储空间是顺序存储的，我们可以可以使用二分法来判断目录项是否有我们需要查询的数据。实际上，这个方案存在许多问题，我们不妨思考以下几个问题。
如果目录项的数量特别多，我们还可以在物理存储空间中为它开辟这么一大块连续的存储空间来存储目录项吗？
如果需要删除中间某一个目录项的数据，其它目录项的位置都需要依次向前移动。
如果我们在中间插入了3个主键连续数据(与之前假定的每页记录数一样)，相当于在目录项中间新增了一个目录项，后面的目录项都需要移动位置。
我们于是考虑，不能使用顺序存储的方式来存储目录项，而应该使用单项链表形式来存储目录项，使他们在逻辑上连续。
因此我们就可以把目录项也放到一个数据页中，其record_type中为1，如下图所示。
目录项的数据页与普通数据页都会建立一个页目录，这样在查找记录时就可以使用二分法加快查询速度,这也解决了链表不能够二分查找的问题，后面我们将详细的介绍页目录的知识。
2.3.2 迭代2：多个目录页
试想下，如果数据页的数量较多，一个目录页不够用了，那怎么办呢？我们其实可以如法炮制：增加目录页。
这时候如果我们需要查询一个数据，就首先需要判断数据是在页30中还是在页32中了。是不是熟悉的配方，熟悉的味道。
2.3.3 迭代3：目录页的目录页
为了解决多个目录页需要遍历查找的问题，我们可以再套一层娃：给目录页增加一个目录页。
随着表中记录数的增加，层数可能还会增加。我们将上图简化如下。这其实就是传说中的B+树了。
实际上，一般实际开发中，B+树几乎不会出现超过四层的情况，因为我们知道，一个数据页有16KB，即使假设每个记录需要160字节，一个数据页页可以存放100条数据，而目录页需要存放的数据大小更小，假设一个目录页可以存放1000个数据。那么四层B+数可以存放的记录数就是：100 * 1000 * 1000 * 1000 = 1000，0000，0000 。1000亿条记录！！！这就意味着，我们查找一次数据，最多需要4次磁盘I/O操作(加载4个数据页)。
3.索引类型
3.1.聚簇索引
聚簇索引：基于主键构建的索引称之为聚簇索引。非聚簇索引:基于非主键构建的索引称之为非聚簇索引。
实际上，聚簇索引并不是一种单独的索引类型，而是一种数据的底层存储方式，它的叶子节点会存储完整的数据记录。数据即索引，索引即数据。前面我们创建的实际上就是聚簇索引(如下图)。而非聚簇索引的叶子节点中并不会存储我们完整的数据记录。
聚簇索引并不需要我们显示的用index去创建，mysql的InnoDB引擎会自动的帮我们创建聚簇索引。
它的优点有：
查询速度更快。聚簇索引把索引和数据保存在同一个B+树中，相比非聚簇索引查询速度更快。
聚簇索引对于主键的排序查找和范围查找很快。
降低了磁盘I/O操作的次数，提升了查找效率(索引的优点)
