一、缘起
在学习数据库时，尤其是工作中涉及到相关业务需要建表，索引是一个绕不过的话题，因此有了想要彻底理解索引的念头。一张设计合理的表，其索引的设计也应当是恰到好处的，不能没有，但也不会太多。
二、何为索引
索引，本质上来说，就是一种数据结构，至于是什么样的数据结构，后文会进行介绍。例如在MySQL中，InnoDB引擎下，索引采用的就是最经典的B+树数据结构。
索引，其存在目的就是为了提高查询速度。当执行一个查询时，如果没有任何索引，MySQL默认为根据查询条件执行全表扫描，如果有一千万条记录，那么最坏情况下，得扫描一千万条记录。而索引的存在，就是为了实现高效查找算法而维护的一套数据结构
索引，从原理上说，每当为某表的字段添加索引时，其实就是将这个字段按照特定顺序进行排列，且建立的索引也只对这个字段有用。比如有一个书架，上面的书籍是根据书名首字母进行排列，那相当于对书名建立了对应的索引，而此时如果想按照作者名称，如张三，来检索书籍，那么书名索引就失效了，只能按照全表扫描一本本来查询。
索引，凡事都具有两面性，索引的存在无疑在大多数场景下可以显著提高查询效率，但是，维护索引也需要额外的开销，
例如，在执行数据库的写操作（insert/update/delete）时，会导致原有索引失效，因此需要进行动态维护，而且数据量越大，维护时间越长。
例如，索引的创建需要占用物理空间，索引创建的越多，占用的物理空间也就越大。
所以，科学合理的设计并创建索引，是保证业务性能的关键之一。
三、索引演变史
MySQL中InnoDB所采用的B+树索引其实是经过不断改进的，所以要理解这种数据结构，还需要先从二叉树说起。
1 二叉查找树
二叉查找树，首先，具有二叉树的特点，即根节点下最多不超过两个叶子节点，且满足条件：左侧子树 节点值 < 根节点值 < 右节点值（简单理解一下，就是“左小右大”）
比如下图
其查找过程，跟二分查找如出一辙，通过不断递归来查找目标值。假设现在有表如下所示。
那么按照二叉查找树建立的索引应该如下所示。
此处的bid为主键，每个节点存储了主键的值和该条记录的内容。
如果我要查找bid为9的图书的信息，则先用6和根节点的主键值7比较发现比7大，
然后9再和7右边的节点8比较发现比8大找到8右边的节点9，找到了，取出9对应的记录行的值ff.
总共经历了3次比较，如果扫描全表需要经过6次比较。
但是这样的结构，也不见得就可以解决所有问题。比如假设本身数据的存储是有序的，那么构造出来的二叉查找树可能就是一个链表结构。
这样的话，性能就退化成全表扫描了，所以，二叉平衡树的出现就是为了改变这种状况。
2 二叉平衡树
二叉平衡树，首先它也是二叉查找树，只不过相对于二叉查找树，多了一个限制条件，左右子树高度差不能大于1，所以在查找效率上，二叉平衡树是要优于二叉查找树。
虽然二叉平衡树平衡了左右子树的高度，但是由于其天然结构的限制——子节点数量不能超过2，导致其在大数据量情况下，树的高度会很大，查询时，遍历次数不可避免会增多。而要想减少遍历次数，首先就得降低树的高度。
因此，为了克服二叉平衡树这一天然的缺陷，B-树便被设计出来。
3 B-树
可以看到，B树在整体上，节点数已经不再受限于只有2个，可以看到，这样的设计可以有效降低树的高度，使得整棵树看上去又矮又胖，而这样正好能够有效减少查询的次数。
而且可以看到，节点内部，其实由三部分组成：
1 键值，即表的主键
2 指针，存储子节点的物理地址信息
3 数据，表记录中除主键之外的其他数据
这三个部分可以视作为一种“元数据”，不可再分，B-树中每个节点内，都会含有大量的这种“元数据”。而每个节点也会占用一定的磁盘空间。
以上图根节点为例，键值为17和35，P1指针指向的子树的数据范围为小于17，P2指针指向的子树的数据范围为17~35，P3指针指向的子树的数据范围为大于35。
模拟查找关键字29的过程：
根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
比较关键字29在区间（17,35），找到磁盘块1的指针P2。
根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
比较关键字29在区间（26,30），找到磁盘块3的指针P2。
根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
在磁盘块8中的关键字列表中找到关键字29。
分析上面过程，发现需要3次磁盘I/O操作，和3次内存查找操作。由于内存中的键值是一个有序表结构，可以利用二分法查找提高效率。而3次磁盘I/O操作是影响整个B树查找效率的决定因素。
虽然B-树的出现，有效减少了磁盘I/O操作的次数，但是仍然可以进一步优化。
首先，由于B-树每个节点都存有数据，那么在查询过程中，相当于查询几次就会有几次磁盘I/O，而有时候很多磁盘I/O操作又是不必要的。
所以MySQL里InnoDB数据引擎采用的B+树索引，就进一步优化了B-树结构，从而产生了B+树索引。
4 B+树
在B-树中，节点由键值、指针、数据组成，而节点在实际物理磁盘内又会占用一部分空间，所以我们可以将节点内的“数据”部分统一移到树的叶子节点中。
这样一来，所有数据均只存在于叶子节点，而非叶节点只保留键值和指针。且叶子节点里的数据（即data部分）是按照键值进行排序的，这样进行键值的范围查找效率会非常高。
这样做，一个最明显的好处就是，非叶节点中，可以存储更多的键值和指针，能最大化的利用磁盘块空间，一个磁盘块也就能存更多的东西了。而B+树就是这么设计的。
假设在非叶子节点不存数据以后每个节点可以存储4个键值和指针，就变成了B+树。
B+树相对于B树有几点不同：
1 非叶子节点只存储键值和指针。
2 所有叶子节点之间都有一个链指针。
3 数据记录都存放在叶子节点中。
所以，从演变过程来看，索引的数据结构大体经历了
二叉查找树 ---》 二叉排序树 ---》 B-树 ---》 B+ 树这样的过程，当然，并非说B+树之前的数据结构就是不好的，只是说不同应用场景，会对应使用不同的数据结构，仅此而已。
