何为索引

索引其实就是一种优化查询的数据结构。比如mysql的索引就是使用B+树来实现的，而B+树就是一种数据结构，可以优化查询速度，所以可以利用索引来优化慢查询，索引的定义就是优化查询的数据结构。

有哪些可以优化查询的数据结构

优化查询的数据结构有哈希表，完全平衡二叉树，B树，B+树。其中Mysql使用最多的是B+树。

hash表

存储数据，需要先获取hashcode，再将数据存储到hashTable[hashcode],这种方式容易产生hash冲突，多个数据同时落到相同下标，可以采用hashTable[hashcode]存储的数据结构变化成链表，里面存储着这些公共hashcode的数据，这种方法叫做拉链法。实现过程
优点: 适合查询单一数据，速度快。
缺点：不适合查询范围数据，相当要遍历索引。

完全平衡二叉树

每个节点最多只能有左右两个子节点，左子树 < 节点 < 右子数，左右子数的层级不能超过 1 层。
实现过程
插入过程，判断当前数与根节点大小进行判断，如果小于根节点，向左子树继续寻找，否则向右子树继续寻找，直到叶子节点后，回溯判断，左右层级是否超过了1层，继续进行树的结构变化。
优点：支持范围查询，因为二叉树是有序的。而且也可以提高查询效率，还是因为它是有序的，而且高度相比其它二叉树更平衡，通过二分法查询。
缺点：二叉树这个定义的本身就限制了它，即一个节点只能有两个子节点，所以当插入的数据非常多时，树的深度就会非常高，树的深度非常高的话就会影响查询效率，所以没有使用二叉树来当索引的。

B树

简单介绍一下就是可以一个节点可以存储多个节点的搜索树。这样就没有了二叉树的两个节点的限制，同时带有有序的特点。所以图中有个参数：MAX.Degree,即一个节点存储的最大节点数，这里设置的是3，看得比较明显。这样的话一层就可以存储很多的数据了。
实现过程
优点：它有二分查找可以快速定位数据的所在位置，而且每层可以存放大量数据，所以树的高度低。感觉还是很不错的。
缺点：范围查询效率太低，因为比一个数据大的话，虽说肯定会在右子树，但是上层数据和其它子树的数据不好对比。

B+树

实现过程
我们对比一下B+树和B树，发现了什么？图中是有重复元素的，仔细一看，所有的非叶子节点都在叶子节点中出现了备份。也就是说，最下面的一层，也就是所有的叶子节点就包含了所有的数据。这就和前面的所有结构都不一样的地方了。然后，比起B树而言，叶子节点这层还有指向后面的指针，也就是多了指向。这就能很好地进行了范围查询，很好地解决了B树的问题。这样定位到数据后，直接在这层的指针遍历即可。
经过上述的讨论，我总结了一下，衡量一种mysql索引好不好有三个原则：
1.能不能快速定位到元素所在位置。
2.能不能较好的进行范围查询。
3.树的高度是低还是高。

局部性原理与磁盘预读

计算机科学中著名的局部性原理:当一个数据被用到时，其附近的数据也通常会马上被使用。

所以操作系统为了提高效率，读取数据时往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，操作系统也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这里的-定长度叫做页，也就是操作系统操作磁盘时的基本单位。一般操作系统中 一页的大小是4Kb。

从上面的原理我们也能知道，固态硬盘比机械硬盘快的最根本最简单的原因就是:固态硬盘使用的电路进行读写，而机械硬盘使用的机械运动。
其实不管是机械硬盘还是固态硬盘都是存储介质,真正控制读写的是操作系统。

这部分属于计算机原理和操作系统方面的知识，感觉理解一下还是很有必要的。

所以，回到我们的问题，B+树中一个节点到底存多少个元素合适?，其实也可以换个角度来思考B+树中一个节点到底多大合适?

答案是: B+树中一个节点为一页或页的倍数最为合适。因为如果一个节点的大小小于1页，那么读取这个节点的时候其实也会读出1页，造成资源的浪费;如果一个节点的大小大于1页，比如1.2页，那么读取这个节点的时候会读出2页，也会造成资源的浪费;所以为了不造成浪费，所以最后把一个节点的大小控制在1页、2页、3页、4页等倍数页大小最为合适。

那么，Mysql中B+树的一个节点大小为多大呢?
这个问题的答案是“1页"”，这里说的页"是Mysq自定义的单位(其实和操作系统类似)，Mysql的Innodb引擎中一页的默认大小是16k (如果操作系统中-页大小是4k，那么Mysql中1 页=操作系统中4页)，可以使用命令SHOW GLOBAL STATUS like 'Innodb_ page size';查看。 并且还可以告诉你的是，一个节点为1页就够了。

为什么一个节点为一页（16kb）就够了呢？

先来看看mylsam和innodb使用B+树的情况：

通常我们认为B+树的非叶子节点不存储数据，只有叶子节点才存储数据。而B树的非叶子节点和叶子节点都会存储数据，这会导致非叶子节点存储的索引值更少，树的高度相对会比B+树高，平均的io效率会比较低，所以使用B+树作为索引的数据结构，再加上B+树的叶子节点之间会有指针相连，便于范围查询。上图的data区域两个存储引擎会有所不同，也就是聚族和非聚族索引的区别。后面详细讲解。

（这里说一下我对这里的为啥B树的高度相对B+树高的理解：就如上图所见，一个节点指的是

这才是一个节点，而不是单纯的15，或者加上旁边的一个指针。这样的话，前面已知一个节点是16kb大小，那么在这固定大小中，B树的非叶子节点还要存储数据，而B+树只存储值和指针。具体一点就是，假设数据大小2kb，值大小1kb,指针大小1kb。那么B树里只能有4个值，而B+树里则有8个值，这样的话，整个索引存储相同数量的值的话，B+树明显就比B树低，这样就提高了磁盘的io效率）

前面我们提到数据区域存储的东西，现在来进行详细解释：

myisam中，叶子节点的数据区域存储的是数据记录的地址。这也叫非聚族索引。

下面是主键索引：

下面是辅助索引：

从图中看得出来，叶子节点中只存储着地址（也就是此值对应的记录的所在地址），找到对应的地址，然后去地址中取出数据。并且主键索引和辅助索引并没有太多区别。

然后再来看innodb中的B+树：

下面是主键索引：

下面是辅助索引：

innodb的主键索引和实际数据是绑定在一起的也就是说innodb的表一定要有一个主键索引，如果一个表没有手动创建一个主键索引，innodb会查看有没有唯一索引，如果有，则选用唯一索引作为主键，如果连唯一索引也没有，则会默认建立一个隐藏的主键索引（用户不可见）

另外，innodb的主键索引要比myisam的的主键索引查询效率较高（少一次磁盘io）,并且比辅助索引也要高很多。（这里不是很理解。。。。）

所以，我们在使用innodb作为存储引擎时，要注意：

1.手动建立一个主键索引

2.尽量利用主键索引进行查询

默默表示，看到这里对主键索引，辅助索引，聚族索引，非聚族索引有点理解不过来了。。。

后面慢慢缓冲。。

回到我们的问题:为什么一个节点为1页(16k) 就够了?

对着上面Mysql中Innodb中对B+树的实际应用(主要看主键索引)，我们可以发现，B+树中的一个节点存储的内容是:

非叶子节点 : 主键+指针

叶子节点 : 数据

那么，假设我们一行数据大小为1K,那么一页就能存16条数据，也就是一个叶子节点能存16条数据;

再看非叶子节点，假设主键ID为bigint类型, 那么长度为8B，指针大小在Innodb源码中为6B，-共就是14B,那么一页里就可以存储16K/14=1170个(主键+指针)，那么一颗高度 为2的B+树能存储的数据为:

117016=18720条，一 颗高度为3的B+树能存储的数据为: 11701170*16=21902400 (千万级条)。所以在InnoDB中B+树高度一般为1-3层， 它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO,所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。所以也就回答了我们的问题，1 页=16k这么设置是比较合适的，是适用大多数的企业的，当然这个值是可以修改的，所以也能根据业务的时间情况进行调整。

接着，我们来联系这次学到的索引底层原理再来看看我常常见到的最左前辍原则：

比如有下面这个B+树索引，我们建立了一个联合索引，顺序是emp_no,title,from_data.既然是联合索引，那么它们按理说应该是放在一起连续存放的。

我们判断一 个查询条件能不能用到索引,我们要分析这个查询条件能不能利用某个索引缩小查询范围

对于select * from employees.titles where emp_ no = 1是能用到索引的，因为它能利用上面的索引缩小所有查询范围，首先和第一个节点"4-r-01"比较，1<4, 所以可以直接确定结果在左子树，同理，依次按顺序进行比较，逐步可以缩小查询范围。

对于select * from employees. titles where title =‘1’是不能用到索引的，因为它不能用到上面的索引，和第一节点进行比较时，没有emp_ no这个字段的值，不能确定到底该去左子树还是右子树继续进行查询。

对于select * from employees.titles where title =‘1’and emp_ no = 1是能用到索引，按照我们的上面的分析,先用ttle='1 这个条件和第一个节点进行比较，是没有结果的，但是mysql会对这个sql进行优化，优化之后会将emp_ no=1这个条件放到第一位，从而可以利用索引。这里是使用了mysql的查询优化器。

Mysq总结

1. B+树可以更好的结合磁盘IO原理提高查询效率

2. Innodb一 定要有主键，没有主键会以唯一索引为主键， 否则会建立一个隐藏主键

3. Innodb的数据是和主键索引存在一起的(数据在叶子节点中，MyISAM中的叶子节点存储的数据地址)

4.建立索引时要考虑已有索引，一个SQL语句只会选择花费最低的一个索引执行

5.索引是一种有序的数据结构(B+树) ，一个节点可以存多个有序的元素，所以要利用好最左前缀原则
6.真实场景中一颗B+树的高度通常为3